$\textrm{Problem Description : }$$\href{https://leetcode-cn.com/problems/score-after-flipping-matrix/}{\textrm{LeetCode861—Score After Flipping Matrix}}$

$\textrm{Language: C++,Python3}$

$\textrm{Label: Greedy}$

$\textrm{Solution:}$

首先给出结论:对于每一行/每一列，至多进行一次翻转。下面给出证明:

我们假设矩阵的规模是$\textrm{n*m}$，并设置$\textrm{line[n]}$,$\textrm{row[m] }$两个数组来表示翻转的次数。其中$\textrm{line[i] = x}$表示第$\textrm{i}$行翻转了$\textrm{x}$次，而$\textrm{raw[j] = y}$则表示第$\textrm{j}$列翻转了$\textrm{y}$次 。于是在完成翻转之后，$\textrm{A[i][j]}$实际翻转的次数就是$\textrm{(x+y)&1}$次，也就是说我们希望在$\textrm{line[n]}$与$\textrm{row[m]}$中的值可以尽可能的翻转出更多的$\textrm{1}$。显然$\textrm{line[n]}$与$\textrm{row[m]}$中的取值其实只分为奇数和偶数，也就是$\textrm{1}$和$\textrm{0}$，所以尽管主观上可能认为存在某种变换，不停地反转行与列，而得出一个最佳的效果，但是事实上任意行与列至多只需进行一次变换，往后的都是冗余的操作。

既然行列最多只能变换一次，那么我们希望$\textrm{1}$更多的出现在高位上，所以对于行的变换取值，是显而易见的$\textrm{:}$若$\textrm{A[i][0] == 0}$，则进行翻转，否则无需翻转。然后考虑从第$\textrm{2}$列开始的每一列，计算这一列的$\textrm{1}$的个数 ，若过半则无需操作，否则进行翻转。实际计算的过程中是可以省去翻转的操作的，只需要通过行首的值来判断这一行是否翻转了，而无需操作元素本身。对于计算部分，则可以采用位运算来直接求值。

时间复杂度: $O(nm)$

空间复杂度: $O(1)$

$\textrm{C}$++ $\textrm{Source Code}$

class Solution {
public:
    int matrixScore(vector<vector<int>>& A) 
    {
        int n = A.size(), m = A[0].size();
        int ans = n*(1<<(m-1)); //每一行行首都是1的值
        for (int j = 1; j < m; j++) //从第二列开始枚举
        { 
            int count = 0;  //1的个数
            for (int i = 0; i < n; i++) 
            {
                //根据行首来判断这一行是否翻转过
                if (A[i][0] == 1) count += A[i][j];
                else count += A[i][j]^1; 
            }
            //count表示不翻转的1的个数, n-count表示翻转后的1的个数，取最大值
            ans += max(count,n-count) * (1 << (m - j - 1));
        }
        return ans;
    }
};

$\textrm{Python Source Code}$

class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        n = len(A)
        m = len(A[0])
        ans = n*(1<<(m-1))    #每一行行首都是1情况下的值
        for j in range(1,m):  #枚举第二列开始的每一列
            count = 0         #这一列1的个数
            for i in range(n): 
                if A[i][0]:   #根据行首来判断这一行是否翻转过
                    count += A[i][j]
                else:
                    count += A[i][j]^1
            #count表示不翻转的1的个数, n-count表示翻转后的1的个数，取最大值
            ans += max(count,n-count)*(1<<(m-j-1))
        return ans

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2020-12-07 01:19}$