力扣练习——27 翻转矩阵后的得分

27 翻转矩阵后的得分

1.问题描述
有一个二维矩阵 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]]

0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

2.输入说明
首先输入矩阵的行数m、列数n，

然后输入m行，每行n个数字，每个数字都是0或1。

1 <= m <= 20

1 <= n <= 20
3.输出说明
输出一个整数
4.范例
输入
3 4
0 0 1 1
1 0 1 0
1 1 0 0
输出
39
5.代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
using namespace std;

int traverse_score(vector<vector<int>>&nums)
{
    
	//思想：给定一个翻转方案，则它们之间任意交换顺序后，得到的结果保持不变。因此，我们总可以先考虑所有的行翻转，再考虑所有的列翻转。
	//行翻转：为了得到最高的分数，矩阵的每一行的最左边的数都必须为 1，因此可以将每一行的最左边的数为0的都翻转为1
	//列翻转：当将每一行的最左边的数都变为 1 之后，就只能进行列翻转了 ；扫描第一列后的所有列，要让每个列中 1的数目尽可能多
	//扫描除了最左边的列以外的每一列，如果该列 0 的数目多于 1 的数目，就翻转该列，其他的列则保持不变。

	//计算每一列对元素的贡献值 ， 共m行 n列 ，第一列全为1时 ，贡献值为m*2^(n-1)
	//第j列 ，元素1的个数为k , 贡献值为 k*2^(n-j-1) 

	int m = nums.size();//行数
	int n = nums[0].size();//列数
	//行翻转得到的贡献值
	//int res = m * (1<<(n - 1)); //int res=m*(1<<(n-1)); 1<<代表二进制数1左移一位变成10（2）
	int res = m * pow(2, n - 1);
	//int res=m*(2^(n-1)); 这个输出来是错误的 ，写成 int res=m*pow(2,n-1);
	
	for (int j = 1; j < n; j++)//对第一列后的其他列进行遍历
	{
    
		int s = 0;//计算第一列后的每列的贡献值 ，如果该列 0 的数目多于 1 的数目，就翻转该列，其他的列则保持不变。
		for (int i = 0; i < m; i++)//先确保每一行的第一列元素都为1
		{
    
			if (nums[i][0] == 1)//第i行第一列元素为1
			{
    
				s += nums[i][j];//计算该行的贡献值 【1的个数】
			}
			else
				s += (1 - nums[i][j]);//该行进行反转，所以结果为1-nums[i][j] 
	    }  
		int k = max(s, m - s);//用s统计1的个数，m-s统计0的个数 ，理解下这里为什么是取max？ 当0的个数比1的个数时，翻转 ；否则不变，因此取max
		res += k * (1<<(n - j - 1));
	}
	return res;
}
 
int main()
{
    
	int n,m,tmp; 
	cin >> n>>m;//n代表行数， m代表列数
	vector<vector<int>>nums;
	vector<int> temp;
	for (int i = 0; i < n; i++)
	{
    
		temp.clear();
		for (int j = 0; j < m; j++)
		{
    
            cin >> tmp;
			temp.push_back(tmp);
		}
		
		nums.push_back(temp);
	}
	int res = traverse_score(nums);
	cout << res<<endl;
	
	return 0;
}