首页 > 代码库 > LintCode刷题笔记-- Maximal Square
LintCode刷题笔记-- Maximal Square
题目描述：
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest square containing all 1‘s and return its area.
Example
For example, given the following matrix:
1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0Return 4.
解题思路：
1.这一题明显使用动态规划来解题，开始想法使用动态规划的方法来记录所有1连在一起的面积，之后记录该面积右下角的坐标，之后通过遍历一个方向的坐标来得到一条边长，之后使用面积来相除，得到一条短边的长度，即可求出正方形面积。但是这么做存在一个问题，即，面积所得出的结果是两边相乘的结果，如果体现在一个数值上，是无法应用到下一子状态的：比如，2*6=12 先前子状态最大面积为12，然而在下一子状态中是无法确定12是从何而来，可能是3*4，可能是2*6。无法使用一个数值来记录两个变量。
2. 随即求助于其他解法，如果一个点是一个正方形的右下角，那么它的左上，上方和左方一定存在着至少存在一个正方形，最优情况是三个正方形的边长是相同的，这样直接在边长上加上1就会构成一个新的正方形，然而如果三个方向的正方形不等的话如果选择最大的边长，就会在某个方向上缺失一角。所以正确的方式是找出最小的一个正方形之后加上1，构成新的正方形。
3.如果matrix的位置上为0，则之前所积累的正方形边长将会中断，所有在为0的dp[i][j]上的位置为0
参考代码：
public int maxSquare(int[][] matrix) { // write your code here int row = matrix.length; int colum = matrix[0].length; int[][] dp = new int[row][colum]; int max = 0; dp[0][0] = matrix[0][0]; for(int i=1; i<row; i++){ dp[i][0] = matrix[i][0]; max = Math.max(dp[i][0], max); } for(int j=1; j<colum; j++){ dp[0][j] = matrix[0][j]; max = Math.max(dp[0][j],max); } for(int i=1; i<row; i++){ for(int j=1; j<colum; j++){ 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; max = Math.max(max, dp[i][j]); } } return max*max; }
LintCode刷题笔记-- Maximal Square
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。