c++刷leetcode(861. 翻转矩阵后的得分)【贪心算法】

糖逗

题目描述：

1. 有一个二维矩阵 A 其中每个元素的值为 0 或 1 。
   
2. 
   
3. 移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
   
4. 
   
5. 在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
   
6. 
   
7. 返回尽可能高的分数。
   
8. 
   
9. 
   
10. 
    
11. 示例：
    
12. 
    
13. 输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
    
14. 输出：39
    
15. 解释：
    
16. 转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
    
17. 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
    
18. 
    
19. 
    
20. 提示：
    
21. 
    
22. 1 <= A.length <= 20
    
23. 1 <= A[0].length <= 20
    
24. A[i][j] 是 0 或 1

复制代码

1. class Solution {
   
2. public:
   
3.     int matrixScore(vector<vector<int>>& A) {
   
4.         //将第一列非0全部交换成1
   
5.         int len1 = A.size(), len2 = A[0].size();
   
6.         for(int i = 0 ; i < len1; i++){
   
7.             if(A[i][0] == 0){
   
8.                 for(int j = 0; j < len2; j++){
   
9.                     A[i][j] = A[i][j] == 0 ? 1 : 0;
   
10.                 }
    
11.             }
    
12.         }
    
13.         //竖列变换保证1比0多
    
14.         for(int j = 1; j < len2; j++){
    
15.             int temp = 0;
    
16.             for(int i = 0; i < len1; i++){
    
17.                 if(A[i][j] == 1) temp++;
    
18.             }
    
19.             if(temp <= len1/2){
    
20.                 for(int i = 0; i < len1; i++){
    
21.                     A[i][j] = A[i][j] == 0 ? 1 : 0;
    
22.                 }
    
23.             }
    
24.             
    
25.         }
    
26.         //计算每行结果
    
27.         int res = 0;
    
28.         for(int i = 0; i < len1; i++){
    
29.             int temp = 0;
    
30.             for(int j = 0; j < len2; j++){
    
31.                 if(A[i][j]==1)temp += pow(2, len2-j-1);
    
32.             }
    
33.             res += temp;
    
34.         }
    
35.         return res;
    
36.     }
    
37. };

复制代码