Score-After-Flipping-Matrix

发表于 | 更新于：

题目地址

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:

1
2
3
4
5
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.

解题思路

  贪心算法，我们知道二进制串中越高位的占的比重越大，所以我们可以直接从高到底来判断是否进行 toggling 操作。

  首先为行，行中每个数字的权重不一样，从高往低，所以在行中我们只需要对第一位进行判断（即数组第一个数字），当他为0的时候我们要将他变为1 就需要 toggling ，这样可以使这一行数字的二进制串最大。

  列中每一列的权重一样，所以我们需要判断这一列中1的个数和0的个数，当0的个数大于1的个数时我们进行 toggling 操作。

解题代码

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
class Solution {
public:
    int matrixScore(vector<vector<int>> &A) {
        if (A.empty()) return 0;
        for (int i = 0; i < A.size(); ++i) {
            int flag = 0;
            for (int j = 0; j < A[i].size(); ++j) {
                if (A[i][0] == 0 || flag) {
                    A[i][j] = A[i][j] == 1 ? 0 : 1;
                    flag = 1;
                }
            }
        }

        for (int i = 1; i < A[0].size(); ++i) {
            int sum = 0;
            for (int j = 0; j < A.size(); ++j) {
                sum += A[j][i];
            }
            if (sum * 2 < A.size()) {
                for (int j = 0; j < A.size(); ++j) {
                    A[j][i] = A[j][i] == 1 ? 0 : 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < A[i].size(); ++j) {
                ret += A[i][j] * pow(2, A[i].size() - 1 - j);
            }
        }
        return ret;
    }
};
0%