题目描述
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 0
s to 1
s, and all 1
s to 0
s.
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:
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]
is0
or1
.
题意:有一个二维矩阵 A 其中每个元素的值为 0 或 1 。移动是指选择任一行或列,并转换该行或列中的每一个值:将所有 0 都更改为 1,将所有 1 都更改为 0。在做出任意次数的移动后,将该矩阵的每一行都按照二进制数来解释,矩阵的得分就是这些数字的总和。返回尽可能高的分数。
算法1
(贪心) $O(n^2)$
题解:假设矩阵的长度是n * m
的,那么对于每一行来说,最左边的数字为1的贡献值是2^(m - 1)
的,所有首位为1的数字肯定大于任何首位为0的数字,所以我们第一步是通过按行反转把每一行的第一个数字变成1。之后,我们便可以执行按列反转,我们可以发现每一列对最终答案的贡献值和这一列中1的位置无关,只和1出现的次数有关。因此如果每一列中1的个数大于0的个数,那么我们就不反转,如果1的个数小于0的个数,那么我们就反转这一列。按照上述规则反转后的矩阵就是最优解。我们使用一个辅助数组统计将执行完按行反转后每一列中1出现的个数。
int matrixScore(vector<vector<int>>& A) {
int n = A.size(),m = A[0].size();
vector<int> cnt_of_one(m,0);
for(int i = 0 ; i < n ; i ++)
{
if(A[i][0] == 0)
for(int j = 0 ; j < m ; j ++)
cnt_of_one[j] += (1 - A[i][j]);
else
for(int j = 0 ; j < m ; j ++)
cnt_of_one[j] += A[i][j];
}
int res = 0,base = 1;
for(int i = m - 1 ; i >= 0 ; i --)
{
res += base * max(cnt_of_one[i], n - cnt_of_one[i]);
base = base * 2;
}
return res;
}