【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用

港控/mmm° 2022-10-16 15:20 156阅读 0赞

## 【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用 ##

### 文章目录 ###

*   *  【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用
     *   *  在区间范围内统计奇数数目★
         *  区域和检索 - 数组不可变★★
         *  子数组异或查询★★
         *  定长子串中元音的最大数目★★
         *  生存人数★★
         *  二维区域和检索 - 矩阵不可变★★
         *  矩阵区域和★★
         *  矩形区域不超过 K 的最大数值和★★★

### 在区间范围内统计奇数数目★ ###

[1523. 在区间范围内统计奇数数目][1523.]

【**题目**】给你两个非负整数 `low` 和 `high` 。请你返回 `low` 和 `high` 之间（包括二者）奇数的数目。

【**示例**】

输入：low = 3, high = 7
    输出：3
    解释：3 到 7 之间奇数数字为 [3,5,7] 。

【**解题思路**】

利用前缀和思想，`high`之前的奇数数目减去`low`之前的奇数数目

class Solution {
        
        public int countOdds(int low, int high) {
        
            return ((high + 1) >> 1) - (low >> 1);
        }
    }

--------------------

### 区域和检索 - 数组不可变★★ ###

[303. 区域和检索 - 数组不可变][303. _ -]

【**题目**】给定一个整数数组 `nums`，求出数组从索引 `i`到 `j（i ≤ j）`范围内元素的总和，包含`i、j` 两点。

实现 `NumArray` 类：

*  `NumArray(int[] nums)`使用数组`nums`初始化对象
 *  `int sumRange(int i, int j)` 返回数组`nums`从索引`i`到 `j（i ≤ j）`范围内元素的总和，包含 `i、j` 两点（也就是 `sum(nums[i], nums[i + 1], ... , nums[j])`）

提示：

*  `0 <= nums.length <= 104`
 *  `-105 <= nums[i] <= 105`
 *  `0 <= i <= j < nums.length`
 *  最多调用 104 次 `sumRange`方法

【**示例**】

输入：
    ["NumArray", "sumRange", "sumRange", "sumRange"]
    [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
    输出：
    [null, 1, -1, -3]
    解释：
    NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
    numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
    numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
    numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

【**解题思路**】

class NumArray {
        
        int[] pre;
    
        public NumArray(int[] nums) {
        
            int n = nums.length;
            pre = new int[n + 1];
            for (int i = 0; i < n; i++) {
        
                pre[i + 1] = pre[i] + nums[i];
            }
        }
        
        public int sumRange(int left, int right) {
        
            return pre[right + 1] - pre[left];
        }
    }

--------------------

### 子数组异或查询★★ ###

[1310. 子数组异或查询][1310.]

【**题目**】有一个正整数数组 `arr`，现给你一个对应的查询数组 `queries`，其中 `queries[i] = [Li, Ri]`。

对于每个查询 `i`，请你计算从 `Li` 到 `Ri` 的 `XOR`值（即 `arr[Li] xor arr[Li+1] xor ... xor arr[Ri]`）作为本次查询的结果。

并返回一个包含给定查询 `queries` 所有结果的数组。

**提示**：

*  `1 <= arr.length <= 3 * 10^4`
 *  `1 <= arr[i] <= 10^9`
 *  `1 <= queries.length <= 3 * 10^4`
 *  `queries[i].length == 2`
 *  `0 <= queries[i][0] <= queries[i][1] < arr.length`

【**示例**】

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
    输出：[2,7,14,8] 
    解释：
    数组中元素的二进制表示形式是：
    1 = 0001 
    3 = 0011 
    4 = 0100 
    8 = 1000 
    查询的 XOR 值为：
    [0,1] = 1 xor 3 = 2 
    [1,2] = 3 xor 4 = 7 
    [0,3] = 1 xor 3 xor 4 xor 8 = 14 
    [3,3] = 8

【**解题思路**】

可以利用前缀和的前提是异或运算的特点

*  `x ^ 0 = x`
 *  `x ^ x = 0`

class Solution {
        
        public int[] xorQueries(int[] arr, int[][] queries) {
        
            int n = arr.length;
            int[] pre = new int[n + 1];
            for (int i = 0; i < n; i++) {
        
                pre[i + 1] = pre[i] ^ arr[i];
            }
    
            int m = queries.length;
            int[] res = new int[m];
            for (int i = 0; i < m; i++) {
        
                res[i] = pre[queries[i][0]] ^ pre[queries[i][1] + 1];
            }
            
            return res;
        }
    }

--------------------

### 定长子串中元音的最大数目★★ ###

[1456. 定长子串中元音的最大数目][1456.]

【**题目**】给你字符串 `s`和整数`k`。

请返回字符串 `s` 中长度为 `k`的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（`a, e, i, o, u`）。

**提示：**

*  `1 <= s.length <= 10^5`
 *  `s` 由小写英文字母组成
 *  `1 <= k <= s.length`

【**示例**】

输入：s = "leetcode", k = 3
    输出：2
    解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
    --------------------------------------------
    输入：s = "abciiidef", k = 3
    输出：3
    解释：子字符串 "iii" 包含 3 个元音字母。

【**解题思路**】

方法一：滑动窗口

class Solution {
        
        public int maxVowels(String s, int k) {
        
            int le = 0, ri = 0;
            int cur = 0, res = 0;
            while (ri < s.length()) {
        
                cur += check(s.charAt(ri));
                if (le + k - 1 == ri) {
        
                    res = Math.max(res, cur);
                    cur -= check(s.charAt(le));
                    le++;
                }
                ri++;
            }
            return res;
        }
    
        private int check(char c) {
        
            char[] chars = {
        'a', 'e', 'i', 'o', 'u'};
            for (char ch : chars) {
        
                if (ch == c) {
        
                    return 1;
                }
            }
            return 0;
        }
    }

方法二：前缀和数组

class Solution {
        
        public int maxVowels(String s, int k) {
        
            int n = s.length();
            int[] pre = new int[n + 1];
            for (int i = 0; i < s.length(); i++) {
        
                pre[i + 1] = pre[i];
                pre[i + 1] += check(s.charAt(i));
            }
    
            int res = 0;
            for (int i = k; i <= n; i++) {
        
                res = Math.max(res, pre[i] - pre[i - k]);
            }
            return res;
        }
    
        private int check(char c) {
        
            char[] chars = {
        'a', 'e', 'i', 'o', 'u'};
            for (char ch : chars) {
        
                if (ch == c) {
        
                    return 1;
                }
            }
            return 0;
        }
    }

--------------------

### 生存人数★★ ###

[面试题 16.10. 生存人数][16.10.]

【**题目**】给定 `N`个人的出生年份和死亡年份，第`i`个人的出生年份为 `birth[i]`，死亡年份为 `death[i]`，实现一个方法以计算生存人数最多的年份。

你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。

如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。

**提示：**

*  `0 < birth.length == death.length <= 10000`
 *  `birth[i] <= death[i]`

【**示例**】

输入：
    birth = {
        1900, 1901, 1950}
    death = {
        1948, 1951, 2000}
    输出： 1901

【**解题思路**】

使用前缀和数组，频次统计出生年份`+1`，死亡年份的后一年`-1`，之后求前缀和，取存活人数最多的第一个年份即可；

class Solution {
        
        public int maxAliveYear(int[] birth, int[] death) {
        
            int[] pre = new int[102];
            for (int i = 0; i < birth.length; i++) {
        
                pre[birth[i] - 1900]++;
                pre[death[i] - 1900  + 1]--;
            }
    
            int maxNum = pre[0];
            for (int i = 1; i < 102; i++) {
        
                pre[i] += pre[i - 1];
                maxNum = Math.max(maxNum, pre[i]);
            }
    
            int maxYear = 0;
            for (int i = 0; i < 102; i++) {
        
                if (pre[i] == maxNum) {
        
                    maxYear = 1900 + i;
                    break;
                }
            }
            
            return maxYear;
        }
    }

--------------------

### 二维区域和检索 - 矩阵不可变★★ ###

[304. 二维区域和检索 - 矩阵不可变][304. _ -]

【题目】给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 `(row1, col1)`，右下角为 `(row2, col2)`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

上图子矩阵左上角`(row1, col1) = (2, 1)` ，右下角`(row2, col2) = (4, 3)`，该子矩形内元素的总和为 `8`。

**提示：**

*  你可以假设矩阵不可变。
 *  会多次调用 `sumRegion` 方法\*。\*
 *  你可以假设 `row1 ≤ row2` 且 `col1 ≤ col2` 。

【示例】

给定 matrix = [
      [3, 0, 1, 4, 2],
      [5, 6, 3, 2, 1],
      [1, 2, 0, 1, 5],
      [4, 1, 0, 1, 7],
      [1, 0, 3, 0, 5]
    ]
    
    sumRegion(2, 1, 4, 3) -> 8
    sumRegion(1, 1, 2, 2) -> 11
    sumRegion(1, 2, 2, 4) -> 12

【解题思路】

二维前缀和图解如下，类似集合的并交补思想

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

查询区域和时只需在前缀和数组上采用同样的思路  
 区 间 和 = 右 下 区 间 和 − 左 端 区 间 和 − 上 端 区 间 和 + 左 上 区 间 和 区间和= 右下区间和-左端区间和-上端区间和+左上区间和 区间和=右下区间和−左端区间和−上端区间和\+左上区间和

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

--------------------

### 矩阵区域和★★ ###

[1314. 矩阵区域和][1314.]

【**题目**】给你一个 `m * n` 的矩阵 `mat`和一个整数 `K`，请你返回一个矩阵 `answer`，其中每个`answer[i][j]`是所有满足下述条件的元素 `mat[r][c]`的和：

*  `i - K <= r <= i + K, j - K <= c <= j + K`
 *  `(r, c)`在矩阵内。

**提示**：

*  `m == mat.length`
 *  `n == mat[i].length`
 *  `1 <= m, n, K <= 100`
 *  `1 <= mat[i][j] <= 100`

【**示例**】

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
    输出：[[45,45,45],[45,45,45],[45,45,45]]

【**解题思路**】

同二维区域和检索一样，但要注意查询区间的边界

class Solution {
        
        public int[][] matrixBlockSum(int[][] mat, int k) {
        
            int r = mat.length, c = mat[0].length;
            int[][] pre = new int[r + 1][c + 1];
            for (int i = 0; i < r; i++) {
        
                for (int j = 0; j < c; j++) {
        
                    pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + mat[i][j];
                }
            }
            
            int[][] res = new int[r][c];
            for (int i = 0; i < r; i++) {
        
                for (int j = 0; j < c; j++) {
        
                    int to = Math.max(0, i - k);
                    int bo = Math.min(r - 1, i + k) + 1;
                    int le = Math.max(0, j - k);
                    int ri = Math.min(c - 1, j + k) + 1;
                    res[i][j] = pre[bo][ri] - pre[bo][le] - pre[to][ri] + pre[to][le];
                }
            }
            
            return res;
        }
    }

--------------------

### 矩形区域不超过 K 的最大数值和★★★ ###

[363. 矩形区域不超过 K 的最大数值和][363. _ K]

【**题目**】给你一个 `m x n`的矩阵 `matrix` 和一个整数`k`，找出并返回矩阵内部矩形区域的不超过 `k`的最大数值和。

题目数据保证总会存在一个数值和不超过 `k` 的矩形区域。

**提示**：

*  `m == matrix.length`
 *  `n == matrix[i].length`
 *  `1 <= m, n <= 100`
 *  `-100 <= matrix[i][j] <= 100`
 *  `-105 <= k <= 105`

【**示例**】

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
    输出：2
    解释：矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

【**解题思路**】

前缀和数组+暴力查询

class Solution {
        
        public int maxSumSubmatrix(int[][] matrix, int k) {
        
            int m = matrix.length, n = matrix[0].length;
            int[][] sum = new int[m + 1][n + 1];
            
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }
    
            int res = Integer.MIN_VALUE;
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    for (int p = i; p <= m; p++) {
        
                        for (int q = j; q <= n; q++) {
        
                            int cur = sum[p][q] - sum[i - 1][q] - sum[p][j - 1] + sum[i - 1][j - 1];
                            if (cur <= k) {
        
                                res = Math.max(cur, res);
                            }
                        }
                    }
                }
            }
    
            return res;
    
        }
    }

其它解法见[宫水三叶题解【宫水三叶】优化枚举的基本思路 & 将二维抽象成一维 & 最大化「二分」效益 & 空间优化][_ _ _ _ _]

--------------------

[1523.]: https://leetcode-cn.com/problems/count-odd-numbers-in-an-interval-range/
[303. _ -]: https://leetcode-cn.com/problems/range-sum-query-immutable/
[1310.]: https://leetcode-cn.com/problems/xor-queries-of-a-subarray/
[1456.]: https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/
[16.10.]: https://leetcode-cn.com/problems/living-people-lcci/
[304. _ -]: https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/0c01374fdd4749cc966823f0ca934fb4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221014/205f0aa96b4449a9874c2fe077725d17.png
[1314.]: https://leetcode-cn.com/problems/matrix-block-sum/
[363. _ K]: https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
[_ _ _ _ _]: https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/gong-shui-san-xie-you-hua-mei-ju-de-ji-b-dh8s/