LeetCode 第二十八天

1. 公交站间的距离

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 start 到目的地 destination 之间的最短距离。

分析：

根据start和destination的大小对数组进行遍历，求出最短距离。

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int min = 0;
        if (start == destination) return 0;
        if (start<destination){
            int count1 = 0;
            int count2 = 0;
            for (int i = start; i < destination; i++) {
                count1 += distance[i];
            }
            for (int i = 0; i < start; i++) {
                count2 += distance[i];
            }
            for (int i = destination; i < distance.length; i++) {
                count2 += distance[i];
            }
            min = Math.min(count1, count2);
        }
        else {
            int count1 = 0;
            int count2 = 0;
            for (int i = destination; i < start; i++) {
                count1 += distance[i];
            }
            for (int i = 0; i < destination; i++) {
                count2 += distance[i];
            }
            for (int i = start; i < distance.length; i++) {
                count2 += distance[i];
            }
            min = Math.min(count1, count2);
        }
        return min;
    }
}

2. 0和1个数相同的子数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

分析：

利用前缀和。定义一个变量pre记录遍历到nums数组每个位置时的前缀和，pre初始化为0，如果nums[i]=1， pre += 1，如果nums[i]=0，pre -= 1. 如果pre=0则表示[0，i]之间含有相同数量的0和1.
使用一个哈希表来记录不为0时每个数出现的最早的位置，pre的值在哈希表中存在的话则求出其相隔的距离。

class Solution {
    public int findMaxLength(int[] nums) {
        int len = 0, pre = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,0);
        for (int i = 1; i <= nums.length; i++) {
            if (nums[i-1] == 1) pre += 1;
            if (nums[i-1] == 0) pre -= 1;
            if (map.containsKey(pre)){
                len = Math.max(len, i-map.get(pre));
            }else{
                map.put(pre, i);
            }

        }
        return len;
    }
}

3. 左右两边子数组的和相等

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

分析：

定义两个变量before和after分别表示当前位置的左侧数之和and右侧数之和。初始值分别为0和整个数组数字之和。开始遍历数组的每一个数，不断地更新before和after，当出现before=after时直接返回当前下标。

class Solution {
    public int pivotIndex(int[] nums) {
        int before = 0, after = 0;
        for (int i = 0; i < nums.length; i++) {
            after += nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            after -= nums[i];
            if (before == after) return i;
            before += nums[i];
        }
        return -1;
    }

4. 二维子矩阵的和

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1,int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2)
  的子矩阵的元素总和。

分析：

利用List存储二维矩阵，然后遍历求和。这个方法差点超时。。。。。就这样吧

class NumMatrix {
    List<int[]> list;
    public NumMatrix(int[][] matrix) {
        list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            list.add(matrix[i]);
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            int[] num = list.get(i);
            for (int j = col1; j <= col2; j++) {
                sum += num[j];
            }
        }
        return sum;
    }
}