資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 翻轉矩陣前傳
假設我們有一個二進位制矩陣。如果我們翻轉一行然後翻轉一列，我們需要找到可以獲得的最大 1 的數量。
因此，如果輸入類似於
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
則輸出將為 8
為了解決這個問題，我們將遵循以下步驟：
n := 矩陣中行的數量
m := 矩陣中列的數量
ret := 0
定義一個大小為 n 的陣列 row
定義一個大小為 n 的陣列 col
total := 0
對於初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
對於初始化 j := 0，當 j < m 時，更新（j 增加 1），執行：
row[i] := row[i] + matrix[i, j]
col[j] := col[j] + matrix[i, j]
total := total + matrix[i, j]
對於初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
對於初始化 j := 0，當 j < m 時，更新（j 增加 1），執行：
cand := total - row[i] - col[j] + ((m - row[i]) + (n - col[j]))
如果 matrix[i, j] 不為零，則：
cand := cand + 2
否則
cand := cand - 2
ret := ret 和 cand 的最大值
返回 ret
讓我們看看以下實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>> &matrix) {
int n = matrix.size();
int m = matrix[0].size();
int ret = 0;
vector<int> row(n);
vector<int> col(m);
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
row[i] += matrix[i][j];
col[j] += matrix[i][j];
total += matrix[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cand = total - row[i] - col[j] + (m - row[i]) + (n -
col[j]);
if (matrix[i][j]) {
cand += 2;
}else {
cand -= 2;
}
ret = max(ret, cand);
}
}
return ret;
}
};
main() {
Solution ob;
vector<vector<int>> v = {{1,0,1},{0,1,0},{1,0,0}};
cout << (ob.solve(v));
}輸入
{{1,0,1},{0,1,0},{1,0,0}}輸出
8
更新於: 2020年9月2日
225 次檢視
廣告