翻转矩阵后的得分

发表于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

LeetCode每日一题，861. Score After Flipping Matrix

先看题目描述

Dv0kGj.png

算法和思路

贪心算法

算法分三步走

  • 遍历每一行进行判断，判断该行是否需要翻转，若该行的第一个元素为 0， 则进行翻转，因为最优的情况下首列元素一定全为 1
  • 遍历每一列进行判断，判断该列是否需要翻转，若该列中 0 的个数多于 1 的个数，则进行翻转，保证取 1 的数量尽可能多
  • 计算结果并返回

算法源码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public int matrixScore(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            if (A[i][0] == 0) {
                changeRow(A, i);
            }
        }
        for (int j = 1; j < n; j++) {
            if (hasMore0(A, j)) {
                changeCol(A, j);
            }
        }
        for (int[] cur : A) {
            int temp = 0;
            for (int num : cur) {
                temp = (temp << 1) + num;
            }
            res += temp;
        }
        return res;
    }

    private void changeRow(int[][] A, int row) {
        for (int i = 0; i < A[row].length; i++) {
            A[row][i] = 1 - A[row][i];
        }
    }

    private void changeCol(int[][] A, int col) {
        for (int i = 0; i < A.length; i++) {
            A[i][col] = 1 - A[i][col];
        }
    }

    private boolean hasMore0(int[][] A, int col) {
        int m = A.length;
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (A[i][col] == 0) {
                cnt++;
            }
        }
        return cnt > m - cnt;
    }
}

注意：由于移位运算的优先级低于加法运算，所以 temp = (temp << 1) + num 这的括号一定得加上，否则结果会出错

下面是官方题解的代码，整体思路其实是一致的，但具体到实现上和我写的代码差别挺大，官方题解的思路和代码如下所示

  • 对于最左边的列而言，由于最优情况下，它们的取值都为 1，因此每个元素对分数的贡献都为 $2^{n-1}$，总贡献为 $m×2^{n-1}$
  • 对于第 j 列（j > 0，此处规定最左边的列是第 0 列）而言，我们统计这一列 0,1 的数量，令其中的最大值为 k，则 k 是列翻转后的 1 的数量，该列的总贡献为 $k×2^{n-j-1}$，需要注意的是，在统计 0,1 的数量的时候，要考虑最初进行的行反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int matrixScore(int[][] A) {
        int m = A.length, n = A[0].length;
        int ret = m * (1 << (n - 1));

        for (int j = 1; j < n; j++) {
            int nOnes = 0;
            for (int i = 0; i < m; i++) {
                if (A[i][0] == 1) {
                    nOnes += A[i][j];
                } else {
                    nOnes += (1 - A[i][j]); // 如果这一行进行了行反转，则该元素的实际取值为 1 - A[i][j]
                }
            }
            int k = Math.max(nOnes, m - nOnes);
            ret += k * (1 << (n - j - 1));
        }
        return ret;
    }
}