【算法】二维前缀和 python
前置知识一维前缀和先容：可以点此进入相识
引入
给你一个由 0 和 1 构成的二维数组 ，n行m列，请你找出界限全部由 1 构成的最大正方形。
思绪分析：
要找最大的，就得罗列全部的正方形：
时间复杂度O(n * m * min(n,m) )
怎么明白这个时间复杂度？
任选一个点为左上角：0~m*n；任选边长：0 ~ min(n,m)
仅仅是罗列就必要这么大的复杂度了。
假如再暴力遍历是否为1，效果肯定得超时。怎么办？
预处理惩罚得到二维前缀和数组
为什么必要二维前缀和算法
目标是预处理惩罚出一个二维前缀和数组，以后每次查询二维数组任何范围上的累加和都是O(1)的操纵
初始化二维前缀和数组
先预处理惩罚得到二维前缀和数组：
s [ i+1 ] [ j+1 ] ：代表左上角(0,0)到右下角(i,j)这个范围的累加和
公式：s [ i+1 ] [ j+1 ] = s [ i + 1 ] [ j ] + s [ i ] [ j + 1 ] - s [ i ] [ j ] + a[ i ] [ j ] （自身+左+上-左上）
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNzExODhlZTU1OTU2NGQzY2I2YmFhMWJmODVlNjlkNjgucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNTRhZmM5OWRjN2ZmNDUzOTllMzliM2Q4NzdlOTgyMjkucG5n
举个实例：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMWM1ZGU4ZjJkZThkNDczMjk5ZjJkYmUzN2E5MmU5OWEucG5n
求恣意子矩阵元素和
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvY2UyMGRhZjg0MzkzNDBiYWJlYzJkNzVkOTRjNTU3MzAucG5n
求玄色矩形的面积：即赤色部分+上面的黄色部分+下面的黄色部分+玄色部分-上面的黄色部分-赤色部分-下面的黄色部分-赤色部分+赤色部分 （整个-左-上+左上）
如下：盘算一个子矩阵的元素和：
设子矩阵左上角为（x1，y1） 右下角为（x2，y2）
sum=sum(x2+1,y2+1) - sum(x1,y2+1) - sum(x2+1,y1) + sum(x1,y1)
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvOGFiYzczMzdkNmIzNGEyZDkwNzg2NGFkYzU3YmZkOTcucG5n
办理题目
回到引入的的题目上来
怎么确定一个正方形（只有0和1）界限是否全为1呢？
查抄其界限的和是不是便是周长即可，很好明白。
怎么得到最表面的界限的和呢？
对整个n*m矩阵做前缀和，
再对小一圈的 n-1 * m-1矩阵做前缀和
两者一减，即得。
最大的以1为界限的正方形 https://leetcode.cn/problems/largest-1-bordered-square/description/
题解code：
class Solution:
def largest1BorderedSquare(self, grid: List]) -> int:
n, m = len(grid), len(grid)# 得到行数和列数
s = [ * (m + 1) for _ in range(n + 1)]# 初始化二维前缀和数组
# 得到二维前缀和数组
for i in range(1, n + 1):
for j in range(1, m + 1):
s = (
s + s - s + grid
)
# 返回子矩阵元素和
def get_sum(x1, y1, x2, y2):
return s - s - s + s
for d in range(min(n, m), 1, -1):
for i in range(1, n - d + 2):
for j in range(1, m - d + 2):
x2 = i + d - 1
y2 = j + d - 1
if get_sum(i, j, x2, y2) - get_sum(i + 1, j + 1, x2 - 1, y2 - 1) == 4 * (d - 1):
return d**2
if s:
return 1
return 0
实战演练
二维区间和检索-矩阵不可变 https://leetcode.cn/problems/range-sum-query-2d-immutable/description/
不绕任何弯子，把前面所学本身用代码实现一下即可
示例code：
class NumMatrix:
def __init__(self, matrix: List]):
m, n = len(matrix), len(matrix)# 得到行数和列数
s = [ * (n + 1) for _ in range(m + 1)]# 初始化二维前缀和数组
# 得到二维前缀和数组
for i, row in enumerate(matrix):
for j, x in enumerate(row):
s = s + s - s + x
# i + 1, j + 1,可以避免边界讨论
self.s = s
# 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和
def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
return (
self.s
- self.s
- self.s
+ self.s
)
# 计算一个子矩阵元素和的公式
涉及的enumerate方法可点此进入检察详细解说
总结
二维前缀和通过预盘算一个累积和矩阵来加快求和操纵，特别实用于必要频仍查询子矩阵（图中恣意矩形地域）内元素总和的场景。
假如有更多题目或必要进一步的资助，可以在批评区留言讨论哦！
假如喜好的话，请给博主点个关注 谢谢
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]