php做网站后台有哪些框架,海外做淘宝网站,青岛网站开发费用,技校网站建设与维护课程教学总结LeetCode 221. 最大正方形
题目描述
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内#xff0c;找到只包含 ‘1’ 的最大正方形#xff0c;并返回其面积。
思路
思路#xff1a;动态规划。初始化时#xff0c;第0列和第0行#xff0c;若nums[i][j]1则dp[i][j]初始化为1找到只包含 ‘1’ 的最大正方形并返回其面积。
思路
思路动态规划。初始化时第0列和第0行若nums[i][j]1则dp[i][j]初始化为1否则初始化为0。规划方程 dp[i][j]Math.min(Math.min(nums[i-1][j], nums[i-1][j-1]), nums[i][j-1])1 再用一个maxSide变量来存储最大正方形边长在求解dp数组过程中不断更新maxSide变量的值
代码
class Solution {public int maximalSquare(char[][] matrix) {// 动态数组初始化int maxSide 0;int[][] dp new int[matrix.length][matrix[0].length];for (int i 0; i matrix.length; i){if (matrix[i][0] ! 0) {dp[i][0] 1;maxSide 1;}}for (int j 0; j matrix[0].length; j){if (matrix[0][j] ! 0) {dp[0][j] 1;maxSide 1;}}for (int i 1; i matrix.length; i) {for (int j 1; j matrix[0].length; j) {if (matrix[i][j] 1){dp[i][j] Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1;}maxSide Math.max(maxSide, dp[i][j]);}}return maxSide * maxSide;}
}
