[LintCode/LeetCode] Maximal Square

Drinkey 发布于2019-08-14 15:14 / 3094人阅读

摘要：类似这种需要遍历矩阵或数组来判断，或者计算最优解最短步数，最大距离，的题目，都可以使用递归。

Problem

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:

Note

类似这种需要遍历矩阵或数组来判断True or False，或者计算最优解（最短步数，最大距离，etc）的题目，都可以使用递归。
所以，找矩阵内存在的最大正方形，需要：

构造传递方程：用dpi存储以当前点matrixi作为正方形右下角顶点，所存在的最大正方形的边长，由matrixi左、上、左上三点的dp值共同判定；

初始化边界：matrix的第一列和第一行；

自顶向下递推dp并更新max，找到max的最大值求平方得最优解。

Corresponding dp matrix:

0 0 0 0 0 0 
0 1 0 1 0 0
0 1 0 1 1 1
0 1 1 1 2 2
0 1 0 0 1 0

mLen = 2, the maximum dp[i] = 2 appeared twice, indicating that there are two maximal squares.

Solution

public class Solution {
    public int maxSquare(int[][] matrix) {
        int mLen = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i-1][j-1] == 1) {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                    mLen = Math.max(mLen, dp[i][j]);
                }
            }
        }
        return mLen * mLen;
    }
}

GPU云服务器云服务器 Maximal Square

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65472.html

[LintCode/LeetCode] Perfect Squares

摘要：动态规划法建立空数组从到每个数包含最少平方数情况，先所有值为将到范围内所有平方数的值赋两次循环更新，当它本身为平方数时，简化动态规划法四平方和定理法 Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) whi...

sydMobile 2019-08-14 16:23 评论0 收藏0
221. Maximal Square

摘要：题目解答第一眼看这道题以为是个搜索问题，所以用解了一下发现边界并没有办法很好地限定成一个，所以就放弃了这个解法。题目：Given a 2D binary matrix filled with 0s and 1s, find the largest square containing all 1s and return its area. For example, given the ...

lanffy 2019-08-14 14:06 评论0 收藏0
[Leetcode] Maximal Square 最大正方形

摘要：但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，这时候只能取那三个正方形中最小的正方形的边长加了。假设表示以为右下角的正方形的最大边长，则有当然，如果这个点在原矩阵中本身就是的话，那肯定就是了。 Maximal Square Given a 2D binary matrix filled with 0s and 1s, find the larges...

xiaowugui666 2019-08-14 12:28 评论0 收藏0
221. Maximal Square

1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 return 4 // O(mn) space public class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0) return 0; ...

freewolf 2019-08-16 10:36 评论0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 评论0 收藏0