Given a m * n
matrix mat
and an integer K
, return a matrix answer
where each answer[i][j]
is the sum of all elements mat[r][c]
for i - K <= r <= i + K, j - K <= c <= j + K
, and (r, c)
is a valid position in the matrix.
class Solution:
def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
if not mat:
return mat
iMax = len(mat) - 1
jMax = len(mat[0]) - 1
prifix = [ [ 0 for _ in range(jMax + 1) ] for _ in range(iMax + 1)]
for i, row in enumerate(prifix):
for j, _ in enumerate(row):
if not i and not j:
prifix[i][j] = mat[i][j]
elif not i:
prifix[i][j] = prifix[i][j-1] + mat[i][j]
elif not j:
prifix[i][j] = prifix[i-1][j] + mat[i][j]
else:
prifix[i][j] = prifix[i-1][j] + prifix[i][j-1] - prifix[i-1][j-1] + mat[i][j]
for i, row in enumerate(mat):
for j, _ in enumerate(row):
rMin, rMax = max(i - K, 0), min(i + K, iMax)
cMin, cMax = max(j - K, 0), min(j + K, jMax)
tmp1 = prifix[rMin-1][cMin-1] if rMin and cMin else 0
tmp2 = prifix[rMin-1][cMax] if rMin else 0
tmp3 = prifix[rMax][cMin-1] if cMin else 0
mat[i][j] = prifix[rMax][cMax] + tmp1 - tmp2 - tmp3
return mat
全部评论 (暂无评论)
info 还没有任何评论,你来说两句呐!