图解矩阵区域和

兜兜转转

发布于 2023-03-08 13:22:25

3700

发布于 2023-03-08 13:22:25

文章被收录于专栏：CodeTimeCodeTime

问题

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

.tg {border-collapse:collapse;border-spacing:0;} .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg .tg-yj5y{background-color:#efefef;border-color:inherit;text-align:center;vertical-align:top} .tg .tg-9wq8{border-color:inherit;text-align:center;vertical-align:middle} .tg .tg-vndr{background-color:red;border-color:inherit;text-align:center;vertical-align:middle} .tg .tg-kndx{background-color:#34ff34;border-color:inherit;text-align:center;vertical-align:top} .tg .tg-c3ow{border-color:inherit;text-align:center;vertical-align:top} .tg .tg-zk7v{background-color:#34ff34;border-color:inherit;text-align:center;vertical-align:middle} .tg .tg-lxrp{background-color:#f8ff00;border-color:inherit;text-align:center;vertical-align:middle} .tg .tg-eix7{background-color:#f8ff00;border-color:inherit;text-align:center;vertical-align:top} .tg .tg-usjd{background-color:#3531ff;color:#ffffff;border-color:inherit;text-align:center;vertical-align:top}

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在原矩阵上扩展了一行和一列，待计算完毕后再恢复回来

123456789	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)

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

123456789	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次相交部分。