一轮秋影转金波，飞镜又重磨。把酒问姮娥：被白发，欺人奈何？
乘风好去，长空万里，直下看山河。斫去桂婆娑，人道是，清光更多。

辛弃疾《太常引·建康中秋夜为吕叔潜赋》

题目描述

leetcode链接: https://leetcode-cn.com/problems/matrix-block-sum/

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

  • i−k≤r≤i+ki - k \leq r \leq i + k,
  • j−k≤c≤j+kj - k \leq c \leq j + k 且
  • (r,c)(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.lengthm == mat.length
  • n==mat[i].lengthn == mat[i].length
  • 1≤m,n,k≤1001 \leq m, n, k \leq 100
  • 1≤mat[i][j]≤1001 \leq mat[i][j] \leq 100

具体实现

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
36
37
38
39
40
41
42
43
44
impl Solution {
    pub fn matrix_block_sum(mat: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
        let mut mat = mat;

        for i in 1..mat[0].len() {
            mat[0][i] += mat[0][i-1];
        }
        for i in 1..mat.len() {
            mat[i][0] += mat[i-1][0];
        }

        for i in 1..mat.len() {
            for j in 1..mat[i].len() {
                mat[i][j] = mat[i-1][j] + mat[i][j-1] + mat[i][j] - mat[i-1][j-1];
            }
        }
        let k = k as usize;
        let mut ret = mat.clone();
        for i in 0..ret.len() {
            for j in 0..ret[i].len() {
                let l = if j >= k {j-k} else {0};
                let r = if j+k < ret[i].len() { j+k } else { ret[i].len() - 1 };
                let u = if i >= k { i - k } else { 0 };
                let d = if i+k < ret.len() { i+k } else { ret.len() - 1 };

                if l == 0 && u == 0 {
                    ret[i][j] = mat[d][r];
                }
                else if l == 0 {
                    ret[i][j] = mat[d][r] - mat[u-1][r];
                }
                else if u == 0 {
                    ret[i][j] = mat[d][r] - mat[d][l-1];
                }
                else {
                    ret[i][j] = mat[d][r] - mat[u-1][r] - mat[d][l-1] + mat[u-1][l-1];
                }
            }
        }
        ret
    }
    
}

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
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        for(int i=1; i<mat[0].size(); i++) {
            mat[0][i] += mat[0][i-1];
        }

        for(int i=1; i<mat.size(); i++) {
            mat[i][0] += mat[i-1][0];
        }

        for(int i=1; i<mat.size(); i++) {
            for(int j=1; j<mat[i].size(); j++) {
                mat[i][j] = mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1] + mat[i][j];
            }
        }
        vector<vector<int>> ret = mat;

        for(int i=0; i<ret.size(); i++) {
            for(int j=0; j<ret[i].size(); j++ ) {
                int l = j - k >= 0 ? j-k : 0;
                int r = j + k < ret[i].size() ? j + k : ret[i].size() - 1;
                int u = i - k >= 0 ? i - k : 0;
                int d = i + k < ret.size() ? i + k : ret.size()-1;

                if(l == 0 && u == 0) {
                    ret[i][j] = mat[d][r];
                }

                else if( l == 0 ) {
                    ret[i][j] = mat[d][r] - mat[u-1][r];
                }
                else if(u == 0) {
                    ret[i][j] = mat[d][r] - mat[d][l-1];
                }
                else {
                    ret[i][j] = mat[d][r] - mat[u-1][r] - mat[d][l-1] + mat[u-1][l-1];
                }
            }
        }

        return ret;
    }
};