题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个二维数组和一个数字 k，现在对于二维数组上的每个值，请求其为中心向周围延伸 k 个格子的正方形的区域和。

思路分享

  • 本质上就是变形了的二维前缀和，只不过这次边界的需要自己计算和规范化，比如下面参考题解中写的 max，min 就是如此，对于超过了数组的值，尽量大或者尽量小就行。重点还是在于自己分辨清楚，边界的下标是否需要加一，由于初始化的矩阵左上多垫了一行和一列，所以计算右下坐标时也需要加一，而左上角本来需要减一，现在就不用变了。

    https://leetcode.cn/problems/matrix-block-sum/solutions/101300/ju-zhen-qu-yu-he-by-leetcode-solution/

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        f = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                f[i+1][j+1] = f[i][j+1] + f[i+1][j] - f[i][j] + mat[i][j]
        for i in range(m):
            for j in range(n):
                mat[i][j] = f[min(m, i+k+1)][min(n, j+k+1)] - f[max(0, i-k)][min(n, j+k+1)] - f[min(m, i+k+1)][max(0, j-k)] + f[max(0, i-k)][max(0, j-k)]
        # print(mat)
        return mat