网站制作长春,今天重大新闻头条新闻国际新闻,喀什网站建设百度推广,河津网站建设网站建设解法都在代码里#xff0c;不懂就留言或者私信
class Solution {/**本题一看就是典型的动态规划#xff0c;要找以每个点为右下角的正方形的面积#xff0c;然后取最大的这个题要注意找规律#xff0c;我找到的规律如下#xff1a;1.以第一行为右下角的#xff0c;因为正… 解法都在代码里不懂就留言或者私信
class Solution {/**本题一看就是典型的动态规划要找以每个点为右下角的正方形的面积然后取最大的这个题要注意找规律我找到的规律如下1.以第一行为右下角的因为正方形是边长相同的所以第一行为右下角最大正方形只能是自己自己是1就是1不是1就是02. 以第一列为右下角的也是一样。3. 以普通位置为右下角的最大正方形首先看自己是不是1如果自己不是1那就肯定是0如果自己是1取它的左上、左、上三个点的最小面积,加1就是它的解自己可以多画几个二维矩阵找找规律*/public int maximalSquare(char[][] matrix) {/**空矩阵的校验健壮性校验 */if(matrix null || matrix.length 0 || matrix[0].length 0) {return 0;}/**如果矩阵只有一个数字那就是0最大面积就是0是1最大面积就是1*/if(matrix.length 1 matrix[0].length 1) {return matrix[0][0] 1? 1 : 0;}/**其他的不过多枚举了直接动态规划解吧dp[i][j]代表以(i,j)为右下角的最大正方形的边长*/int[][] dp new int[matrix.length][matrix[0].length];/**定义最大值变量 */int maxArea 0;/**初始化第一行和第一列*/for(int j 0; j dp[0].length; j) {dp[0][j] matrix[0][j] 1? 1 : 0;/**这里其实是dp[0][j]* dp[0][j]反正最大就是1懒得写了 */maxArea Math.max(maxArea, dp[0][j]);}for(int i 1; i dp.length; i) {dp[i][0] matrix[i][0] 1? 1 : 0;/**这里其实是dp[i][0]* dp[i][0]反正最大就是1懒得写了 */maxArea Math.max(maxArea, dp[i][0]);}/**初始化普通位置 */for(int i 1; i dp.length; i) {for(int j 1; j dp[i].length; j) {if(matrix[i][j] 1) {dp[i][j] matrix[i][j] 1? Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) 1 : 0;maxArea Math.max(maxArea, dp[i][j]*dp[i][j]);}}}return maxArea;}
} 相信我这就是最优解矩阵就是m*n你不过完能知道答案吗
