随心情不定时更新,什么都可能写一点的技术博客

0%

图解矩阵区域和

问题

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

题解

如果采用暴力法,每个格子直接计算,会发现存在大量的重复计算,可先构造一个矩阵dp,原矩阵是mat,dp[i,j]表示从矩阵左上角mat[0,0]到右下角mat[i,j]这个范围构成的矩阵所有元素之和。
该矩阵可看作是一个左上角是(0,0),右下角是(i,j)围成的矩形的面积,得到该矩阵后,就可以采用面积差来计算任意矩形的面积。
比如下图求左上角(2,1)和右下角(4,3)构成的蓝色部分,可通过由(0,0)到(4,3)的面积减去绿色部分(0,0)到(1,3),减去黄色部分(0,0)到(4,0),当然红色部分(0,0)到(1,0)是2个矩形相交的部分,会被减去2次,所以还得增加1次。而这几部分矩形都是从(0,0)作为左上角的,面积都是已知的存储在dp中。

1
(0,0)
2
(0,1)
3
(0,2)
4
(0,3)
5
(0,4)
6
(1,0)
7
(1,1)
8
(1,2)
9
(1,3)
0
(1,4)
1
(2,0)
2
(2,1)
3
(2,2)
4
(2,3)
5
(2,4)
6
(3,0)
7
(3,1)
8
(3,2)
9
(3,3)
0
(3,4)
1
(4,0)
2
(4,1)
3
(4,2)
4
(4,3)
5
(4,4)

用动态规划法求dp

每个dp都可以看作是上边的dp加上左边的dp,减去相交的部分,同时还要加上这个dp本身在矩阵中的值
dp[i][j]=mat[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

原矩阵
1
(0,0)
2
(0,1)
3
(0,2)
4
(1,0)
5
(1,1)
6
(1,2)
7
(2,0)
8
(2,1)
9
(2,2)
dp矩阵
1
(0,0)
3
(0,1)
6
(0,2)
5
(1,0)
12
(1,1)
?
(i,j)
?
(2,0)
?
(2,1)
?
(2,2)

我这里为了避免边界检查,将dp在原矩阵上扩展了一行和一列,待计算完毕后再恢复回来

1
2
3
4
5
6
7
8
9
r=len(mat)
c=len(mat[0])
dp=[[0 for _ in range(c+1)] for _ in range(r+1)]
for i in range(1,r+1):
for j in range(1,c+1):
dp[i][j]=mat[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
dp.pop(0)
for d in dp:
d.pop(0)

当然你也可以先特殊处理第一行和第一列,再执行同样的计算。

1
2
3
4
5
6
7
8
9
dp=[[0 for _ in range(c)] for _ in range(r)]
dp[0][0] = mat[0][0]
for j in range(1,c): #处理第一行
dp[0][j]=mat[0][j]+dp[0][j-1]
for i in range(1,r): #处理第一列
dp[i][0]=mat[i][0]+dp[i-1][0]
for i in range(1,r):
for j in range(1,c):
dp[i][j]=mat[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

根据dp求每个格子的值

以每个格子作为中心点,根据半径可求得矩形的左上角start和右下角end,根据这2个点就可以得到上面说的4个矩形的面积了,当然还需要作边界检查,还有只有当start点既不在第一行也不在第一列时才会产生2个需要减去的矩形,换句话说,当start点在第一行或者第一列时,只会产生一个矩形或者没有。只有当出现2个矩形的时候,才会出现相交,同时这个相交部分会被减去2次,所以还得增加1次相交部分。

1
2
3
4
5
6
7
res=[[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
for j in range(c):
start=(max(i-K,0),max(j-K,0))
end=(min(i+K,r-1),min(j+K,c-1))
res[i][j]=dp[end[0]][end[1]] - (0 if start[0]==0 else dp[start[0]-1][end[1]]) - (0 if start[1]==0 else dp[end[0]][start[1]-1])+ (0 if start[0]==0 or start[1]==0 else dp[start[0]-1][start[1]-1])
return res

时间复杂度$ O(MN) $