861. Score After Flipping Matrix -----------M

A: 

就是看矩阵，找出 规律，首先行变换，把每行的首字母都变成1.

然后列变换，让每一列都是1比0 多。

Intuition

Notice that a 1 in the $i$th column from the right, contributes $2^i$ to the score.

Since $2^n > 2^{n-1} + 2^{n-2} + \cdots + 2^0$, maximizing the left-most digit is more important than any other digit. Thus, the rows should be toggled such that the left-most column is either all 0 or all 1 (so that after toggling the left-most column [if necessary], the left column is all 1.)

Algorithm

If we toggle rows by the first column (A[r][c] ^= A[r][0]), then the first column will be all 0.

Afterwards, the base score is max(col, R - col) where col is the column sum; and (1 << (C-1-c)) is the power of 2 that each 1 in that column contributes to the score.

class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int m = A.size();
        if(m==0)
            return 0;
        int n = A[0].size();
        //first make first item of every row be positive
        for(int i =0;i<m;i++){
            if(A[i][0] == 1)
                continue;
            for(int j = 0;j<n;j++)
                A[i][j] = 1 - A[i][j];
        }
        // now check every column, if more zero than one, then flip
        for(int j = 1; j <n; j++){
            int count1 =0;
            for(int i = 0;i<m;i++)
                count1 += A[i][j];
            if(count1 < m - count1){
                // flip 
                for(int i = 0;i<m;i++)
                    A[i][j] = 1- A[i][j];
            }
        }
        int res = 0;
        for(int i = 0;i<m;i++)
            res += getValue(A[i]);
        return res;
    }
private:
    int getValue(vector<int> & row){
        int res = 0;
        for(auto v : row)
            res = res * 2 + v;        
        return res;
    }
};

------------------上面的思路时清晰的， 然和人， 之beat  了  9.82%的。 

优化一下： 在过程中就算结果

class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int m = A.size();
        if(m==0)
            return 0;
        int n = A[0].size();
        //first make first item of every row be positive
        for(int i =0;i<m;i++){
            if(A[i][0] == 1)
                continue;
            for(int j = 1;j<n;j++)
                A[i][j] = 1 - A[i][j];
        }
        int res = m;
        // now check every column, if more zero than one, then flip
        for(int j = 1; j <n; j++){
            int count1 =0;
            for(int i = 0;i<m;i++)
                count1 += A[i][j];
            res = res * 2 + max(count1, m - count1);
        }
        return res;
    }
};

继续优化： 直接不修改,反而在column 检查的时候， 和行首字母对比

class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int m = A.size(), n = A[0].size();
        int res = m;        
        for(int j = 1; j <n; j++){
            int count1 =0;
            for(int i = 0;i<m;i++)
                count1 += (A[i][j] ^ A[i][0]);
            res = (res << 1) + max(count1, m - count1);
        }
        return res;
    }
};