【Leetcode】861.翻转矩阵后的得分

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

方法（贪心算法）

因为我们想要让数字总和最大，那么就需要让每一行的所代表的数字尽可能大。又因为矩阵中的第一列是每一行代表数字的最高位。

因此第一步：我们先遍历第一列的各个行，如果发现有元素为0，将该行进行转换。（让最高位尽可能大）

第一步结束后，每一行的最高位就都为1了。而对于之后的每一列，我们统计列中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
//贪心策略：
//第一步：遍历第一列的各行，如果发现有0的，将此行转换
//第二步：从第二列起遍历各列，如果一列中0的个数高于1的个数，将该列转换
private int[][] A;
public int matrixScore(int[][] A) {
    this.A = A;
    for(int i = 0; i < A.length; i++){
        if(A[i][0] == 0)
            reverseRow(i);
    }
    for(int j = 1; j < A[0].length; j++){
        int count0 = 0;
        for(int i = 0; i < A.length; i++){
            if(A[i][j] == 0)
                count0++;
            if(count0 > A.length / 2){
                reverseCol(j);
                break;
            }
        }
    }
    int res = 0;
    for(int i = 0; i < A.length; i++){
        int num = 0;
        for(int j = 0; j < A[0].length; j++){
            num = (num << 1) + A[i][j];
        }
        res += num;
    }
    return res;
}

public void reverseRow(int i){
    for(int j = 0; j < A[0].length; j++){
        A[i][j] = A[i][j] == 0 ? 1 : 0;
    }
}

public void reverseCol(int j){
    for(int i = 0; i < A.length; i++){
        A[i][j] = A[i][j] == 0 ? 1 : 0;
    }
}

方法改进

在上述方法第二步中，我们真的需要对列进行转换吗？

实则不然。考虑在二进制的表示中，一个位数上的1对结果的贡献其实是相同的。就比如：1100和1111，这两个二进制表示中次高位的1对结果的贡献都为4。

而A中的同一列又代表着相同的位数。因此我们只需要统计该列中0的数量和1的数量即可：

  • 如果一列中0的数量大于1的数量，则该列将被反转（并不实际需要反转操作），反转前的count0就是反转后的1的数量，于是用count0对结果进行更新
  • 如果一列中1的数量大于0的数量，则该列不需要反转，直接用count1对结果进行更新
    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
    private int[][] A;
    public int matrixScore(int[][] A) {
        this.A = A;
        int res = 0;
        for(int i = 0; i < A.length; i++){
            //如果当前位置为0，那么它之后要转换成为1
            //所有行在第0列（最高位）的1对结果的贡献都是一样的，因此再这里直接对res进行更新
            if(A[i][0] == 0){
                reverseRow(i);
            }
            res += (1 << (A[0].length - 1));
        }
        for(int j = 1; j < A[0].length; j++){
            int count0 = 0;
            int count1 = 0;
            for(int i = 0; i < A.length; i++){
                if(A[i][j] == 0)
                    count0++;
                else
                    count1++;
            }
            if(count0 > count1)
                res += count0 * (1 << (A[0].length - j - 1));
            else
                res += count1 * (1 << (A[0].length - j - 1));
        }
        return res;
    }

    //转换A的第i行
    public void reverseRow(int i){
        for(int j = 0; j < A[0].length; j++){
            A[i][j] = A[i][j] == 0 ? 1 : 0;
        }
    }