アルゴリズム

LeetCode-221。最大の正方形（1つすべての最大の正方形を参照）



Leetcode 221 Maximal Square



LeetCode-221。最大の正方形（1つすべての最大の正方形を参照）

  • 暴力O(N^5)）
  • 動的計画を改善する（O(N^３)）
  • 動的計画法を最適化する（O(N^2)）

トピックリンク

トピック

画像

暴力O(N^5)）

暴力O(N) * O(M) * O(min(N ， M)) * O(N) * O(M)それはO(N^5)しかし、通過することもできます...



  • enumerate 0 ~ n with 0 ~ m次に、この範囲内のすべての正方形を列挙します。ここでの時間計算量はO(N) * O(M) * O(min(N, M))；
  • 次に、列挙される各正方形は、すべての正方形が内側にあるかどうかを判断する必要があります。1、時間計算量O(N * M );

画像

class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0 int n = matrix.length int m = matrix[0].length int res = 0 for(int x = 0 x < n x++){ // Enumerate the upper left corner of x for(int y = 0 y < m y++){ // enumerate the y in the upper left corner for(int size = Math.min(n-x, m-y) size >= 1 size--){ // Enumerate [1, min(n-x, m-y)] so many squares (size indicates square matrix size) if(check(matrix, x, y, size)){ / / Check if this square is all 1 res = Math.max(res, size*size) break / / Because the size is from large -> small, so you can break } } } } return res } private boolean check(char[][] matrix, int x, int y, int size){ for(int i = x i < x+size i++){ for(int j = y j < y+size j++){ if(matrix[i][j] - '0' == 0) return false } } return true } }

動的計画を改善する（O(N^３)）

上記check()この関数には、大きな正方形を判断するときに実際に多くのサブ問題が含まれています。

上記の方法で改善できますcheck()複雑さを最適化するプロセス：

  • Will check()前処理、このプロセスには動的な計画が必要です
  • この動的計画では、2次元sums配列、Sum[x][y] (or sums[i][j])を使用します。表現(0, 0) ~ (x, y)この行列の合計

下の写真を見てsum( 0~x, 0~y )法を求めて：

青い部分のうち2つは、緑の部分が重なっているので、もう1つ引きます。
画像

上記のsums配列が見つかった場合、次のようになりますO(1)この列挙の2乗がすべて時間内にあるかどうかを確認します1次に、列挙された合計が二乗はsize * sizeに等しいと判断できます。

現在どのように取得されていますか？sums配列は現在の列挙の2乗の合計を取得しますか？

可能性がありますsum配列は現在になります(x, y)左上の頂点の二乗の合計、一般的なフレームは次のとおりです。

画像

ただし、ここでは、コードの処理に注意を払う必要があります。

we sums配列の開始1, 1最初の処理が簡単になります。そうしないと、境界を判断するのが難しくなるため、ループの3番目の層がチェックされます。size = Math.min(n-x+1, m-y+1)また、最初に注意を払う必要があります。

class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0 int n = matrix.length int m = matrix[0].length / / Preprocess the sum of the numbers inside the (0, 0) ~ (x, y) matrix int[][] sums = new int[n+1][m+1] for(int x = 1 x <= n x++){ // Recursive from [0,0] to [x,y] for(int y = 1 y <= m y++){ sums[x][y] = sums[x][y-1] + sums[x-1][y] - sums[x-1][y-1] + matrix[x-1][y-1]-'0' } } int res = 0 for(int x = 1 x <= n x++){ // Enumerate the upper left corner of x for(int y = 1 y <= m y++){ // enumerate the y in the upper left corner for(int size = Math.min(n-x+1, m-y+1) size >= 1 size--){ // Enumerate [1, min(n-x, m-y)] so many squares (size indicates square matrix size) int sum = sums[x+size-1][y+size-1] - sums[x+size-1][y-1] - sums[x-1][y+size-1] + sums[x-1][y-1] if(sum == size*size){ res = Math.max(res, size*size) break } } } } return res } }

動的計画法を最適化する（O(N^2)）

この方法は、この問題の最適な解決策です。

それらの中でdp[i][j]から表現(0, 0)現在まで(x, y)構築できる最大の正方形size（辺のサイズ）。

その後：

  • 現在の場合matrix[i][j] == 0、その後dp[i][j] = 0；
  • 他の一般的な状況、下の写真を参照してください、あなたは得ることができますdp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1；

画像

class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0 int n = matrix.length int m = matrix[0].length int[][] dp = new int[n][m] int res = 0 for(int i = 0 i < n i++){ dp[i][0] = matrix[i][0] - '0' res = Math.max(res, dp[i][0]) } for(int j = 0 j < m j++){ dp[0][j] = matrix[0][j] - '0' res = Math.max(res, dp[0][j]) } for(int i = 1 i < n i++){ for(int j = 1 j < m j++){ if(matrix[i][j] - '0' == 0) continue dp[i][j] = 1 + Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1])) res = Math.max(res, dp[i][j]) } } return res * res } }