資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中統計全為 1 的正方形子矩陣
假設我們有一個大小為 m x n 的二進位制矩陣。我們需要統計所有元素都為 1 的正方形子矩陣的數量。例如，如果矩陣如下所示：
| 0 | 1 | 1 | 1 |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
那麼將有 15 個正方形。10 個單個元素的正方形，4 個包含四個元素的正方形，以及 1 個包含九個元素的正方形。
為了解決這個問題，我們將遵循以下步驟：
- 設定 ans := 0，n := 行數，m := 列數
- 對於 i 的範圍從 0 到 m – 1
- ans := ans + matrix[n – 1, i]
- 對於 i 的範圍從 0 到 n – 1
- ans := ans + matrix[i, m – 1]
- ans := ans – matrix[n – 1, m - 1]
- 對於 i 的範圍從 n – 2 逆序到 0
- 對於 j 的範圍從 m – 2 逆序到 0
- 如果 matrix[i, j] = 1，則
- matrix[i, j] := 1 + min(matrix[i + 1, j + 1], matrix[i, j + 1], matrix[i + 1, j])
- 否則 matrix[i,j] := 0
- ans := ans + matrix[i, j]
- 如果 matrix[i, j] = 1，則
- 對於 j 的範圍從 m – 2 逆序到 0
- 返回 ans
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int ans = 0;
int n = matrix.size();
int m = matrix[0].size();
for(int i = 0; i < m; i++)ans += matrix[n-1][i];
for(int i = 0; i < n; i++)ans += matrix[i][m-1];
ans -= matrix[n-1][m-1];
for(int i = n - 2;i >= 0; i--){
for(int j = m-2 ;j >= 0; j--){
matrix[i][j] = matrix[i][j] == 1? 1 + min({matrix[i+1][j+1],matrix[i] [j+1],matrix[i+1][j]}) : 0;
ans += matrix[i][j];
}
}
return ans;
}
};
main(){
vector<vector<int>> v = {{0,1,1,1},{1,1,1,1},{0,1,1,1}};
Solution ob;
cout << (ob.countSquares(v));
}輸入
[[0,1,1,1], [1,1,1,1], [0,1,1,1]]
輸出
15
更新於: 2020年5月2日
137 次瀏覽
廣告