資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的最大正方形
假設我們有一個用 0 和 1 填充的 2D 二進位制矩陣。我們必須找到僅包含 1 的最大正方形並返回其面積。因此，如果矩陣如下所示 −
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
那麼輸出將為 4
為解決此問題，我們將按照以下步驟操作 −
ans := 0, n := 行數，c := 行數
如果 n 為 0，則返回 0
建立另一個 (n x c) 階矩陣
對於 i 的範圍從 0 到 n – 1
對於 j 的範圍從 0 到 c – 1
m[i, j] := matrix[i, j]
ans := m[i, j] 和 ans 的最大值
對於 j 的範圍從 0 到 c – 1
如果不為 0，則 m[i, j]，那麼
m[i, j] := 1 + m[i + 1, j]、m[i, j-1]、m[i + 1, j-1] 中的最小值，
ans := m[i, j] 和 ans 的最大值
返回 ans*ans
讓我們看看以下實現以獲得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int ans = 0;
int n = matrix.size();
if(!n)return 0;
int c = matrix[0].size();
vector<vector<int>> m(n, vector <int> (c));
for(int i =0;i<n;i++){
for(int j = 0; j<c;j++){
m[i][j] = matrix[i][j] - '0';
ans = max(m[i][j],ans);
}
}
for(int i =n-2;i>=0;i--){
for(int j =1;j<c;j++){
if(m[i][j]){
m[i][j] = 1 + min({m[i+1][j],m[i][j-1],m[i+1][j-1]});
}
ans = max(ans,m[i][j]);
}
}
return ans*ans;
}
};
main(){
vector<vector<char>> v = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'}, {'1','0','0','1','0'}};
Solution ob;
cout << ((ob.maximalSquare(v)));
}輸入
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出
4
更新於: 2020 年 4 月 30 日
313 次檢視
廣告資訊