跳转至

861. 翻转矩阵后的得分#

问题描述#

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。

返回尽可能高的分数。

 

示例：

输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：
转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

 

提示：

  1. 1 <= A.length <= 20
  2. 1 <= A[0].length <= 20
  3. A[i][j] 是 0 或 1

解题思路#

贪心。

首先将第 0 列为 0 的 行 全部改变。

然后从第 1 列起，如果该列中 1 的数字小于行数的一半，则将该 列 全部改变。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])
        s = [int("".join(map(str, x)), 2) for x in A]
        mask = (1 << n) - 1
        for i, x in enumerate(s):
            if (1 << (n - 1)) & x == 0:
                s[i] = mask & (~x)
        for i in range(n - 1, 0, -1):
            t = 0
            for x in s:
                if (1 << (i - 1)) & x:
                    t += 1
            if t < (m + 1) // 2:
                for j, _ in enumerate(s):
                    s[j] ^= 1 << (i - 1)
        return sum(s)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])
        for i in range(m):
            if A[i][0] == 0:
                for j in range(n):
                    A[i][j] ^= 1
        return sum(
            max(sum(x), m - sum(x)) << (n - 1 - i)
            for i, x in enumerate(zip(*A))
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])
        ans = m
        for j in range(1, n):
            ans <<= 1
            cnt = 0
            for i in range(m):
                cnt += A[i][j] ^ A[i][0]
            ans += max(cnt, m - cnt)
        return ans
返回顶部

在手机上阅读