网站开发空间小,广州百度网站推广,Wordpress官网网址,有源码如何做网站题目
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内#xff0c;找到只包含 ‘1’ 的最大正方形#xff0c;并返回其面积。
示例
输入#xff1a;matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“…题目
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内找到只包含 ‘1’ 的最大正方形并返回其面积。
示例
输入matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出4
解析
题外话首先注意下函数签名func maximalSquare(matrix [][]byte) int {} 这道题还是用动规五部曲来处理下 1.dp数组及其含义 dp[i][j]:代码下标为i-1j-1位置为右下角的正方形最大面积为dp[i][j]。这个dp公式的定义很重要首先是定义成了右下角其次还用到了之前-1的这种方法写代码会简单些 2.递推公式 if matrix[i-1][j-1] ‘1’ { dp[i][j] min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) 1 } 大致的思路是首先要右下角的这个位置是1否则就没啥用了肯定不满足在是1的前提下类似木桶原理右下角位置的最长边长取决于另外三个位置的最小距离然后1 3.初始化 使用了-1的策略后就是不需要特别的初始化了默认是0
func maximalSquare(matrix [][]byte) int {if len(matrix) 0 || len(matrix[0]) 0 {return 0}m : len(matrix)n : len(matrix[0])maxSide : 0dp : make([][]int, m1)for i : 0; i m; i {dp[i] make([]int, n1)}for i : 1; i m; i {for j : 1; j n; j {if matrix[i-1][j-1] 1 {dp[i][j] min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) 1maxSide max(maxSide, dp[i][j])}}}return maxSide * maxSide
}func min(a, b int) int {if a b {return b}return a
}func max(a, b int) int {if a b {return a}return b
}1277 统计全为1的正方形子矩阵
题目
给你一个 m * n 的矩阵矩阵中的元素不是 0 就是 1请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例
输入matrix [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出15 解释 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 10 4 1 15.
解析
这道题和上面那道基本一样的思路记住递推公式把
func countSquares(matrix [][]int) int {if len(matrix) 0 || len(matrix[0]) 0 {return 0}m : len(matrix)n : len(matrix[0])dp : make([][]int, m1)for i : 0; i m; i {dp[i] make([]int, n1)}res : 0for i : 1; i m; i {for j : 1; j n; j {if matrix[i-1][j-1] 1 {dp[i][j] min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) 1res dp[i][j]}}}return res
}func min(a, b int) int {if a b {return b}return a
}
