问题
给你一个 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次相交部分。
1234567 | 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)
