Leetcode 861 Score After Flipping Matrix

发表于 |

We have a two dimensional matrix A where each value is 0 or 1.
A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.
After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.
Return the highest possible score.

Example 1:
Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Note:

  1. 1 <= A.length <= 20
  2. 1 <= A[0].length <= 20
  3. A[i][j] is 0 or 1.

分析：

  1. 一个二维矩阵A，我们对其进行两种操作，一种是将某一列中的0，1全部反转，一种是将某一行的0，1全部反转
  2. 进行若干次操作后按照每一行的数将其变为二进制数，使得所有行求和最大
  3. 如果我们单分析一行，如例子中第一行，0011，我们知道在四位二进制数中后三位的和为7，第一位就有8，所以可以断定在最优情况下，首位数字必要变成1，所有行同理（贪心）。
  4. 当第一位全为1后，根据贪心我们想使第二位尽量多1，此时只能改列（改行可能使首位数字变动），也就是对于第二列，如果1的数量比0少，那么我们就进行一次列反转，反之就不进行操作，之后每一列以此类推！

按照上述操作后我们观察示例中矩阵A中元素变换过程，首先先将首位全部变为1，然后：
1 1 0 0 — — — — — — — — > 1 1 0 0 — — — — — — — — > 1 1 1 0 — — — — — — — — > 1 1 1 1
1 0 1 0 — —第二列1多— — —> 1 0 1 0 — —第三列0多— — —> 1 0 0 0 — —第四列0多— — —> 1 0 0 1
1 1 0 0 — — — — — — — — > 1 1 0 0 — — — — — — — — > 1 1 1 0 — — — — — — — — > 1 1 1 1

思路：

  1. 先判断每行第一个元素是否为0，若为0则进行一次行变换
  2. 然后对每一列进行0，1数量的判断，若0多，则进行一次列变换，也就是将1，0的个数对调
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def matrixScore(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        m,n = len(A),len(A[0])
        # 行变换
        for i in range(m):
            if A[i][0] == 1: continue
            for j in range(n):
                A[i][j] = 1 - A[i][j]

        # 列变换
        res = 0
        for rows in zip(*A):
        	# 始终使1的个数是更大的
            cnt1 = max(rows.count(1), rows.count(0))
            res += cnt1 * 2**(n-1)
            n -= 1
        return res

O(m*n) time, O(m*n) space (because of zip(*A))
80 / 80 test cases passed.
diffculty: medium
Runtime: 37 ms