前缀和&差分

前缀和

一个只用初始化一次，但是却要反复检索计算多次，需要在最开始做预处理。

for (int i = 0; i < nums.length; i++) {
      presum[i+1] = nums[i] + presum[i];
 }

作者：chefyuan
链接：https://leetcode-cn.com/problems/continuous-subarray-sum/solution/de-liao-wo-ba-qian-zhui-he-miao-de-gan-g-c8kp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

=======================

将matrix[][]的前缀和数组定义为prefix[][],定义prefix[i][j]表示从[0, 0]位置到[i, j]位置的子矩阵所有元素的和。

S(O,D)=S(O,C)+S(O,B)−S(O,A)+D

如果求 preSum[i][j]preSum[i][j] 表示的话，对应了以下的递推公式：

preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i][j]

根据preSum求子矩形面积：

S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G)

如果要求 [row1, col1][row1,col1] 到 [row2, col2][row2,col2] 的子矩形的面积的话，用 preSum 对应了以下的递推公式：

preSum[row2][col2] - preSum[row2][col1 - 1] - preSum[row1 - 1][col2] + preSum[row1 - 1][col1 - 1]

===================================

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/ru-he-qiu-er-wei-de-qian-zhui-he-yi-ji-y-6c21/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

所以以上方法用java代码表示就是如下所示：

    private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        if (matrix.length > 0) {
            preSum = new int[matrix.length + 1][matrix[0].length + 1];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j]
                                       - preSum[i][j] + matrix[i][j];
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2 + 1][col2 + 1] 
               - preSum[row2 + 1][col1] - preSum[row1][col2 + 1]
               + preSum[row1][col1];
    }

leetcode304

这道题可以借鉴在matrix中选择一块小矩阵，计算其中矩阵的元素和

class NumMatrix {
    int[][] sums;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }
}

如果针对一个矩阵，要找到这个矩阵中固定大小子矩阵的和，可以借鉴前缀和：

    int[][] sums;
    public int countMatrixPrefix(int[][] matrix, int cnt) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
        PriorityQueue queue = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < matrix.length - cnt + 1; i++) {
            for (int j = 0; j < matrix[0].length - cnt + 1; j++) {
                queue.add(sumRegion(i, j, i + cnt - 1, j + cnt - 1));
            }
        }
        return queue.poll();
    }

    private int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }

前缀和

leetcode528

    // 前缀和数组
    int[] pre;
    // 权重和
    int total;

    public WeightRandomChoice(int[] w) {
        pre = new int[w.length];
        pre[0] = w[0];
        for (int i = 0; i < w.length; i++) {
            pre[i] = pre[i - 1] + w[i];
        }
        total = Arrays.stream(w).sum();
    }

    public int pickIndex() {
        int x = (int)(Math.random() * total) + 1;
        return binarySearch(x);
    }

    private int binarySearch(int x) {
        int low = 0;
        int high = pre.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (pre[mid] < x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

差分题

差分原理：

leetcode1109 航班预定系统

    public int[] corpFlightBookings(int[][] bookings, int n) {
        
        int[] difference = new int[n];
        for (int[] booking : bookings) {
            difference[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                difference[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            difference[i] += difference[i - 1];
        }
        return difference;
    }

leetcode1094. 拼车字少的题题狠话不多

    public boolean carPooling(int[][] trips, int capacity) {
        int max = 0;
        // for循环找到最大的下车地点
        for (int[] trip : trips) {
            if (max < trip[2]) {
                max = trip[2];
            }
        }
        int[] place = new int[max + 1]; // 地点数组，i位置有place[i]人上车
        for (int[] trip : trips) {
            place[trip[1]] += trip[0];
            place[trip[2]] -= trip[0];
        }

        int count = 0; // 记录乘客数量
        for (int i = 0; i < place.length; i++) {
            count += place[i];
            if (count > capacity) {
                return false;
            }
        }
        return true;
    }

前缀和&差分

Java相关栏目本月热门文章