資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中翻轉矩陣後的得分
假設我們有一個二維矩陣A，其中每個值都是0或1。這裡的一次移動包括選擇任何一行或一列，並切換該行或列中的每個值：將所有0更改為1，將所有1更改為0。現在，在進行任意次數的移動後，將此矩陣的每一行解釋為二進位制數，矩陣的分數是這些數字的總和。因此，我們的任務是找到可能獲得的最高分數。如果輸入如下：
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
輸出將是39，因為在切換後，矩陣將變為：
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
所以數字是 15 + 9 + 15 = 39
為了解決這個問題，我們將遵循以下步驟：
n := 行數，m := 列數
ret := n x (2^(m – 1))
對於 j 從 1 到 m – 1
cnt := 0
對於 i 從 0 到 n – 1
cnt := cnt + A[i, j] == A[i, 0]
temp := 2^(m – j – 1) * max(cnt, n – cnt)
ret := ret + temp
返回 ret
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int matrixScore(vector<vector<int>>& A) {
int n = A.size();
int m = A[0].size();
int ret = (1 << (m - 1)) * n;
for(int j = 1; j < m; j++){
int cnt = 0;
for(int i = 0; i < n; i++){
cnt += (A[i][j] == A[i][0]);
}
int temp = ((1 << (m - (j + 1))) * max(cnt, n - cnt));
ret += temp;
}
return ret;
}
};
main(){
vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
Solution ob;
cout << (ob.matrixScore(v));
}輸入
[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
輸出
39
更新於：2020年4月30日
瀏覽量：119
廣告