数据结构
网络
关系型数据库管理系统 (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
广告