找实习之从0开始的后端学习日记【9.17】

动规专题地址

1314. 矩阵区域和

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

i - k <= r <= i + k,
j - k <= c <= j + k 且
(r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：

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

提示：

m == mat.length
n == mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100

思路

使用二维前缀和

（为了节省空间，后续还在mat上写了答案）

class Solution {
    public int n;
    public int m;
    public int[][] p;
    public int getSum(int r,int c,int k){
        int A = p[Math.min(m-1,r+k)][Math.min(n-1,c+k)];
        int B = c-k-1<0?0:p[Math.min(m-1,r+k)][c-k-1];
        int C = r-k-1<0?0:p[r-k-1][Math.min(n-1,c+k)];
        int D = c-k-1<0||r-k-1<0?0:p[r-k-1][c-k-1];
        return A-B-C+D;
    }
    public int[][] matrixBlockSum(int[][] mat, int k) {
        this.m=mat.length;
        this.n=mat[0].length;
        // int[][] result = new int[m][n];
        p = new int[m][n];
        p[0][0]=mat[0][0];
        for(int j = 1;j<n;j++){
            p[0][j] = p[0][j-1]+mat[0][j];        
            }
        for(int i = 1;i<m;i++){
            p[i][0]=p[i-1][0]+mat[i][0];
            for(int j = 1;j<n;j++){
                p[i][j]=p[i][j-1]+mat[i][j]+p[i-1][j]-p[i-1][j-1];                
            }
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                mat[i][j] = getSum(i,j,k);
            }
        }
        return mat;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

我这个边界处理的还是太拉了~0的那边如果再扩充一行一列会更方便

官解就十分优雅

class Solution {
public:
    int get(const vector<vector<int>>& pre, int m, int n, int x, int y) {
        x = max(min(x, m), 0);
        y = max(min(y, n), 0);
        return pre[x][y];
    }
    
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> P(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[i][j] = get(P, m, n, i + K + 1, j + K + 1) - get(P, m, n, i - K, j + K + 1) - get(P, m, n, i + K + 1, j - K) + get(P, m, n, i - K, j - K);
            }
        }
        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/matrix-block-sum/solution/ju-zhen-qu-yu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

学习学习~

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

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

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

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

示例 1：

输入:
[“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法

思路

比上面的更简单化，用了二维前缀和~，学习了上面题解的边界条件

class NumMatrix {
    public int[][] p;
    public NumMatrix(int[][] matrix) {
        int  m = matrix.length;
        int n = matrix[0].length;
        p = new int[m+1][n+1];
        for(int i = 1;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                //p的index全部往右移1
                p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return p[row2+1][col2+1]-p[row1][col2+1]-p[row2+1][col1]+p[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24