没有输出的输入是不完整的

0%

leetcode-861-ScoreAfterFlippingMatrix

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

本题目和之前的kickstart的G轮的第二题有一点类似。
为了保证最后的数值最大，在保证最高位是1的基础上，保证之后的每一列尽可能有更多的1，非常巧妙也非常实用。

题目描述

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
2
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 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j] is 0 or 1.

解题思路

贪心算法

详细解释

我们会发现，在二进制串中，即使从次高位到最低位全部都是1也比最高位是1要小，所以为了保证最后形成的二进制串最大，必然每一行的第一位一定是1，然后对于从第二列开始之后的每一列，要尽可能有更多的1。

巧妙之处

  1. 为了保证最后形成的二进制的数字最大，我们要保证最高位是1，
  2. 非常巧妙的用了移位来进行二进制的乘法运算，比如说
1
1<<2

实际上就变成了0b100(二进制的100)，也就是从1变成了4，相当于乘上了2的2次方。

  1. 在统计每一列0和1数目的时候也没有真的将数字进行一一遍历进行计算，而是通过是否和第一位数字相同来进行判断，原因是进行行变化之后，其实每个数字和本行的第一个数字的相同与否并没有发生变化，而我们为了让最终数值最大所以保证了每行的第一个数字都必须是1，从而通过与1的相同与否我们判定出每一列的0和1的个数，进而让多的数是1可以保证本列最后的数值也会是最大的。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int m = A.size();
        int n = A[0].size();
        int res = m*(1<<(n-1));
        int cnt = 0;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m;j++){
                 cnt += (A[j][0]==A[j][i]);
            }
            res += max(cnt,m-cnt)*(1<<(n-1-i));
            cnt = 0;
        }
        return res;
    }
};

以上，本题结束！