leecode-861.翻转矩阵后的得分

题目

翻转矩阵后的得分

思路分析

因为本题是按照行或者列进行翻转，所以我们先分析行。

• 对于行的数据来说，为了使得最后的结果最大，那么我们得保证高位的数据尽可能多的是1.也就是，如果发现某一行开头不是1的时候，就先翻转此行。
• 对于列来说，因为对于第j列来说，其对结果的贡献值是非零值的个数*（1<<(col-1-j)）。

代码

class Solution {
public:
    int maxSum;
    //获取每一行数据代表的数值
    inline int getSum(vector<int>& A){
        int n = A.size(), ans = 0;
        //是否进行翻转
        bool flag = (A[0] == 0) ? true : false;
        for(int i = 0; i < n;i++){
            if(flag) A[i] = !A[i];
            if(A[i] == 1)
                ans += (1 << (n - 1 - i));
        }
        return ans;
    }
    int matrixScore(vector<vector<int>>& A) {
        int r = A.size(), c = A[0].size(), ans = 0;
        maxSum = (1 << r) - 1;
        for(int i = 0; i < r;i++)   ans += getSum(A[i]);
        for(int j = 0;j < c;j++){
            int s = 0;
            for(int i = 0;i < r;i++) s += A[i][j];
            //如果此时的0的数值多余1的数值，进行翻转
            if(2 * s < r) ans +=  (r - 2 * s) * (1 << (c - 1 - j));
        }
        return ans;
    }
};