$\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}$
退出登录?