Leetcode 1504. Count Submatrices With All Ones (python)

题目

解法1：

枚举上下边界，将二维问题转化为1维vector的情况来做

class Solution:def numSubmat(self, mat: List[List[int]]) -> int:m,n = len(mat),len(mat[0])partial_sum = [[0]*n for _ in range(m+1)]for i in range(n):tmp = 0for j in range(1,m+1):if mat[j-1][i] == 1:tmp += 1partial_sum[j][i] = tmpdef cal(row):i = 0count = 0total_count = 0for num in row:if num==1:count += 1else:if count==1:total_count += 1if count>1:total_count += (count+1)*count/2count = 0if count:if count==1:total_count += 1else:total_count += (count+1)*count/2return int(total_count)count = 0for top in range(m):for bottom in range(top+1,m+1):tmp_row = [0]*nfor k in range(n):#print(bottom,top,k)if partial_sum[bottom][k]-partial_sum[top][k] == bottom-top:tmp_row[k] = 1count += cal(tmp_row)return count

解法2

见代码comment，核心思想是，对于固定的左右及下边界来说，通过观察边界内高度的变化，可以数出以固定的左边界，右边界和下边界来说，不同高度的子矩阵有多少个。这样的枚举方式的话，每个形状的子矩阵都只会被count一次

class Solution:def numSubmat(self, mat: List[List[int]]) -> int:m,n = len(mat),len(mat[0])partial_sum = [[0]*n for _ in range(m+1)]for i in range(n):tmp = 0for j in range(1,m+1):if mat[j-1][i] == 1:tmp += 1partial_sum[j][i] = tmpdef cal(row):i = 0count = 0total_count = 0for num in row:if num==1:count += 1else:if count==1:total_count += 1if count>1:total_count += (count+1)*count/2count = 0if count:if count==1:total_count += 1else:total_count += (count+1)*count/2return int(total_count)count = 0for top in range(m):for bottom in range(top+1,m+1):tmp_row = [0]*nfor k in range(n):#print(bottom,top,k)if partial_sum[bottom][k]-partial_sum[top][k] == bottom-top:tmp_row[k] = 1count += cal(tmp_row)return count