[LintCode/LeetCode] Maximal Square

Drinkey 發(fā)布于2019-08-14 15:14 / 3262人閱讀

摘要：類似這種需要遍歷矩陣或數組來判斷，或者計算最優(yōu)解最短步數，最大距離，的題目，都可以使用遞歸。

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，或者計算最優(yōu)解（最短步數，最大距離，etc）的題目，都可以使用遞歸。
所以，找矩陣內存在的最大正方形，需要：

構造傳遞方程：用dpi存儲以當前點matrixi作為正方形右下角頂點，所存在的最大正方形的邊長，由matrixi左、上、左上三點的dp值共同判定；

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

自頂向下遞推dp并更新max，找到max的最大值求平方得最優(yōu)解。

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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.hztianpu.com/yun/65472.html

[LintCode/LeetCode] Perfect Squares

摘要：動態(tài)規(guī)劃法建立空數組從到每個數包含最少平方數情況，先所有值為將到范圍內所有平方數的值賦兩次循環(huán)更新，當它本身為平方數時，簡化動態(tài)規(guī)劃法四平方和定理法 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

摘要：題目解答第一眼看這道題以為是個搜索問題，所以用解了一下發(fā)現邊界并沒有辦法很好地限定成一個，所以就放棄了這個解法。題目：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