【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
题目描述
有一个二维矩阵 其中每个元素的值为
或
。
移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 都更改为
，将所有
都更改为
。
在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
返回尽可能高的分数。
示例1
输入：
[[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
提示
-
-
是
或
题解
首先我们要明确一个显而易见的事实：
- 每一行、每一列要么不翻转，要么翻转一次，再多是等价的，没有意义。
二进制枚举
因为行列数最多 ，所以我们可以枚举每一行的翻转状态（
：不翻转，
：翻转）。
然后对于每一列，我们只需要看不翻转的 多，还是翻转后
多就行了。
这样的时间复杂度是 ，极限情况下是
左右，还是可能会超时的。
贪心
再仔细观察，我们可以发现要想最终和最大，第一列必须全为 。
证明很简单，对于任意一行，如果它的第一位是 ，那么这一位的二进制数值就是
。反之如果这一位是
，那么即使后面所有位全为
，总数值也只能达到
。所以第一位是一定要为
的。
这样就很简单了，每一行的翻转情况其实是确定的。如果第一位是 ，就不翻转，否则就翻转。
然后每一列还是看不翻转的 多，还是翻转后
多。
这样的时间复杂度只有 。
那么可能有人会问：为啥不把每行第一位全翻转为 ，然后翻转第一列使得每行第一位全
呢？其实这样是等价的，完全就相当于将之前的方法倒转过来（翻转不翻转操作颠倒）。
代码
c++
class Solution {
public:
int matrixScore(vector<vector<int>>& A) {
int n = A.size(), m = A[0].size();
for (int i = 0; i < n; ++i) {
if (A[i][0]) continue;
for (int j = 0; j < m; ++j) {
A[i][j] ^= 1;
}
}
int res = (1<<(m-1)) * n;
for (int j = 1; j < m; ++j) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += A[i][j];
}
cnt = max(cnt, n-cnt);
res += (1<<(m-1-j)) * cnt;
}
return res;
}
};
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
百度成长空间 412人发布
