leetcode-1314. 矩阵区域和

本文主要是介绍leetcode-1314. 矩阵区域和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你一个 m * 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

解题思路

【暴力版】对于每个位置，都考虑以其为中心的k*k矩阵，求该矩阵内的和即可。时间、空间复杂度是 $o (m * n * k)$

【二维前缀和】保存二维矩阵的前缀和，则最终返回的矩阵，应该是sum[i + k][j + k] + sum[i - k][j - k] - sum[i + k][j - k] - sum[i - k][j + k]
注意一些细节：

保存二维矩阵的前缀和矩阵时，可以多增加左上一圈0的行，以避免超出矩阵范围的麻烦
下标注意一下细节即可

时间复杂度和空间复杂度都是 $o (m * n)$

代码

【暴力版】

class Solution:def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:rows, cols = len(mat), len(mat[0])ret_matirx = [[0] * cols for _ in range(rows)]for each_row in range(rows):row_left, row_right = max(0, each_row - K), min(rows - 1, each_row + K)for each_col in range(cols):col_left, col_right = max(0, each_col - K), min(cols - 1, each_col + K)ret_matirx[each_row][each_col] = sum(sum(row[col_left: col_right + 1]) for row in mat[row_left: row_right + 1])return ret_matirx

【二维矩阵前缀和】

class Solution:def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:rows, cols = len(mat), len(mat[0])sum_matrix = [[0] * (cols + 1) for _ in range(rows + 1)]sum_matrix[1][1] = mat[0][0]for each_row in range(1, rows + 1):for each_col in range(1, cols + 1):sum_matrix[each_row][each_col] = sum_matrix[each_row - 1][each_col] + sum_matrix[each_row][each_col - 1] - sum_matrix[each_row - 1][each_col - 1] + mat[each_row - 1][each_col - 1]ret_matrix = [[0] * cols for _ in range(rows)]for each_row in range(rows):for each_col in range(cols):right_down_row, right_down_col = min(each_row + K + 1, rows), min(each_col + K + 1, cols)left_up_row, left_up_col = max(each_row - K, 0), max(each_col - K, 0)ret_matrix[each_row][each_col] = sum_matrix[right_down_row][right_down_col] + sum_matrix[left_up_row][left_up_col] - sum_matrix[right_down_row][left_up_col] - sum_matrix[left_up_row][right_down_col]return ret_matrix