文章目录
-
求解全1矩形和求解全1正方形是两个十分类似，但是处理细节与想法又有所不同的两个算法题目 -
一开始，本博主在看到这两类题目的时候，以为它们的方法是通用的，然后想通过其中的一个方法拓展到另一个题型的时候，发现在实际的实现的过程中，发现了拓展的难度以及发现了两类题目的一些处理细节的差异所带来的方法的局限性
-
话不多说，先自己体验一下两个题目
1277.统计全为1的正方形子矩阵
1504.统计全1子矩形
- 好的，首先来分析这个全为1的正方形的题目，矩形矩形，我们可以很快想到可以考虑使用这个
二维前缀和进行思考，只要这个子正方形的面积等于对应的区间和，那么就可以ans+=1 - 实现的细节：我们通过外层的两层循环来枚举
子正方形的右下角的坐标(i,j),内层循环再进行枚举子正方形的边长l,然后我们就可以计算出这个子正方形的左上角的坐标(x1,y1),然后就可以通过二维差分就可以得出该正方形区间的和
class Solution:def countSquares(self, matrix: List[List[int]]) -> int:# 前缀和进行求解m,n = len(matrix),len(matrix[0])# 解法1 使用前缀和pre = [[0]*(n+1) for _ in range(m+1)]for i in range(m):for j in range(n):pre[i+1][j+1] = pre[i+1][j] + pre[i][j+1] - pre[i][j] + matrix[i][j]ans = 0for i in range(m):for j in range(n):# 现在求解以(i,j)为右下角的正方形长度为l的矩阵的区域内的区间和，是否等于l*l# 枚举长度for l in range(1,min(m,n)+1):x1,y1 = i-l+1,j-l+1if x1 < 0 or y1 <0:break# 坐标(i,j) 与 (x1,y1)所围成的矩形的面积tmp = pre[i+1][j+1] - pre[x1][j+1] - pre[i+1][y1] + pre[x1][y1]if tmp == l*l:ans += 1else:breakreturn ans- 好啦，接下来看看下面的这个
统计全1子矩形的问题
- 首先，想一想是否可以也使用这个
二维前缀和的思路？求解二维前缀和比较好算，但是在你实现的过程中，会发现你要划分四层循环去实现整个算法，内层循环要使用两层循环来枚举子矩形的左上角的坐标，区别于子张方形，子正方形由于边长相等，所以只用一层内循环即可找到左上角的坐标，那么就不可以用二维前缀和求解这个题目了 - 那么我们应该怎么做？
- 考虑引入
left[i][j]表示原来的(i,j)向左延伸的连续的1的长度，得到这个left数组之后，我们只需在每个位置的(i,j)向上枚举这个子矩形的高，逐个更新这个向左的left,保留较小值，如果不为0，就可以更新，否则直接退出
class Solution:def numSubmat(self, mat: List[List[int]]) -> int:m = len(mat)n = len(mat[0])# left[i][j]表示以(i,j)向左延伸的连续的1的个数left = [[0]*n for _ in range(m)]for i in range(m):for j in range(n):# 特别处理这个第一列的情况，预防出界if j == 0:left[i][j] = mat[i][j]else:left[i][j] = 0 if mat[i][j] == 0 else left[i][j-1] + 1# 现在对于每一个位置(i,y)进行找到矩形的情况ans = 0for i in range(m):for j in range(n):tmp = float("inf")for z in range(i,-1,-1):tmp = min(tmp,left[z][j])if tmp == 0 :breakelse:ans += tmpreturn ans额外思考，这个子矩形的方法可以用到这个left方法吗？
答：也不可以，因为你无法兼顾整个正方形的情况
# 解法2 使用更加一般的方法# 定义left[i][j]为(i,j)的左边连续1的长度left = [[0]*n for _ in range(m)]for i in range(m):for j in range(n):if j == 0:left[i][j] = matrix[i][j]else:left[i][j] = 0 if matrix[i][j] == 0 else left[i][j-1]+1# 直接开始统计ans = 0for i in range(m):for j in range(n):# 直接对这个边长枚举h = left[i][j]if h == 0:continuefor k in range(h):if i-k <0 :break# 判断逻辑有问题，后面并不能确保现在的也是大于的if left[i-k][j] >= k+1:ans +=1breakelse:breakreturn ans
该代码是错误的，因为
if left[i-k][j] >= k+1:这个没有正确判断整个正方形的情况，因为你只是判断这个边长是否满足，但是内部的边长并没有成功判断，所以整体的来说，正方形还是得使用二维前缀和
