题目分析

小伙伴们看一看如何做到得分最高吧，没有思路的童鞋可以先模拟一下找规律。

贪心

题目是比较简单的，我们要想让得分最高，因此我们要满足高位一定是1，要将高位都变成1，可以先按照行来翻转，这里将高位都翻转为1，或者将高位都翻转为0再翻转高位这一列都是可以的。为了代码的简洁，就直接将高位按行翻转为1。

然后下面只能按列进行翻转了，因为再按行翻转会影响到高位，分数一定不是最高的。因此我们统计第k列中1的个数和0的个数，如果0的个数多，我们就翻转该列即可，这样1的个数就多了。

算法的**时间复杂度为$O(mn)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int row = A.size(), col = A[0].size();
        int bit = 1 << (col - 1), res = 0;
        for (int i = 0; i < row; i++) {
            if (!A[i][0]) {
                for (int j = 0; j < col; j++) {
                    A[i][j] = 1 - A[i][j];
                }
            }
        }
        for (int j = 0; j < col; j++) {
            int cnt = 0;
            for (int i = 0; i < row; i++) {
                cnt += A[i][j];
            }
            res += max(cnt, row - cnt) * bit;
            bit >>= 1;
        }
        return res;
    }
};

刷题总结

做这个题目的时候，我想了几分钟，发现将最高位都变为1和最高位都变为0然后翻转列是等价的，第一种方法次高位0的数量等于第二种方法次高位1的数量，因为在计算次高位值得时候，要取0和1的最大值，因此不会影响到次高位的结果。这一点是非常非常重要的，否则这个题就无法用贪心求解。