Leetcode_20 天编程能力基础_day13

Posted on | In ,
| 3.1k | 25 mins.

不知道写什么好了...😁

304. Range Sum Query 2D - Immutable

Analysis

这是个前缀和的题，而且是二维数组的前缀和。

Code

method 1

这种题如果知道推导的公式的话，就很简单了。不过，还是自己先做一下。
因为知道了是前缀和的题，所以先按照一维前缀和的思路来处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumMatrix {
public:
    vector<vector<int>> prefixsum = vector<vector<int>>(205, vector<int>(205));
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                prefixsum[i][j + 1] = prefixsum[i][j] + matrix[i][j];
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        while(row1 <= row2) {
            sum += prefixsum[row1][col2 + 1] - prefixsum[row1][col1];
            row1++;
        }
        return sum;
    }
};

em，一维前缀和的思路，勉强通过了。

method 2

再回头考虑二维前缀和的思路，首先应该明确的二维前缀和中的和，是以当前坐标的元素为右下角（也就是最后一个）元素的矩阵的元素之和。按照推导公式（具体怎么推导不讨论了）可以知道：

1
2
3
prefixsum[i + 1][j + 1] 
= prefixsum[i - 1][j] + prefixsum[i][j - 1] - prefixsum[i - 1][j - 1]
 + matrix[i][j]

之所以要写成 i + 1 与 j + 1 的形式，是为了避免当 row = 0，col = 0 时的特殊判断，这点与一维前缀和的思路是一致的。
对应的：

1
2
3
sumRegion(row1, col1, row2, col2)
= prefixsum[row2 + 1][col2 - 1] - prefixsum[row1][col2 + 1] 
 - prefixsum[row2 + 1][col1] + prefixsum[row1][col1]

就可以得到下面的代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumMatrix {
public:
    vector<vector<int>> prefixsum = vector<vector<int>>(205, vector<int>(205));
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m > 0) {
            int n = matrix[0].size();
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    prefixsum[i + 1][j + 1] = prefixsum[i][j + 1] 
                        + prefixsum[i + 1][j] - prefixsum[i][j] + matrix[i][j];
                }
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixsum[row2 + 1][col2 + 1] - prefixsum[row1][col2 + 1] 
                - prefixsum[row2 + 1][col1] + prefixsum[row1][col1];
    }
};

PS：画一个矩形，用求矩形小块面积的思路来理解二维前缀和比较直观，看公式容易看晕。

910. Smallest Range II

Analysis

这个题是 908. Smallest Range I 的加强版，差别在于这个题既可以对数组元素加 k，也可以对数组元素减 k。所以，为了保持操作结束后的数组的最值差最小，就得让数组中大的数减 k，小的数加 k。但难点在于，该如何界定这里提到的大和小呢？

Code

虽然，这个题的标签是贪心、排序和数学，但个人感觉是个抖机灵题目。
这个人的题解写的很清楚：太难了，只能画图凭直觉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int mymin, mymax, size = nums.size();
        int ans = nums[size - 1] - nums[0];
        for(int i = 0; i < size - 1; i++) {
            mymin = min(nums[0] + k, nums[i + 1] - k);
            mymax = max(nums[size - 1] - k, nums[i] + k);
            ans = min(ans, mymax - mymin);
        }
        return ans;
    }
};

Summary

前缀和的题目挺常规，第二个题有点奇怪~
顺路再把一维前缀和的题目给做了：303. Range Sum Query - Immutable。

Buy me a coffee ? :)
0%