问题描述
$\textrm{LeetCode861—Score After Flipping Matrix}$
解法
首先给出结论:对于每一行/每一列，至多进行一次翻转。下面给出证明:
我们假设矩阵的规模是$\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}$的个数 ，若过半则无需操作，否则进行翻转。实际计算的过程中是可以省去翻转的操作的，只需要通过行首的值来判断这一行是否翻转了，而无需操作元素本身。对于计算部分，则可以采用位运算来直接求值。
cpp 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;
}
};
时间复杂度: $O(nm)$
空间复杂度: $O(1)$
Author@Kuroko
GitHub@SuperKuroko
LeetCode@kuroko177
Last Modified: 2020-12-07 01:19
