【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分

题目描述

有一个二维矩阵 A 其中每个元素的值为 01

移动是指选择任一行或列,并转换该行或列中的每一个值:将所有 0 都更改为 1,将所有 1 都更改为 0

在做出任意次数的移动后,将该矩阵的每一行都按照二进制数来解释,矩阵的得分就是这些数字的总和。

返回尽可能高的分数。

示例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

      

提示

  • 01

题解

首先我们要明确一个显而易见的事实:

  • 每一行、每一列要么不翻转,要么翻转一次,再多是等价的,没有意义。

二进制枚举

因为行列数最多 20 ,所以我们可以枚举每一行的翻转状态(0:不翻转,1:翻转)。

然后对于每一列,我们只需要看不翻转的 1 多,还是翻转后 1 多就行了。

这样的时间复杂度是 ,极限情况下是 左右,还是可能会超时的。

贪心

再仔细观察,我们可以发现要想最终和最大,第一列必须全为 1

证明很简单,对于任意一行,如果它的第一位是 1 ,那么这一位的二进制数值就是 。反之如果这一位是 0 ,那么即使后面所有位全为 1 ,总数值也只能达到 。所以第一位是一定要为 1 的。

这样就很简单了,每一行的翻转情况其实是确定的。如果第一位是 1 ,就不翻转,否则就翻转。

然后每一列还是看不翻转的 1 多,还是翻转后 1 多。

这样的时间复杂度只有 O(RC)

那么可能有人会问:为啥不把每行第一位全翻转为 0 ,然后翻转第一列使得每行第一位全 1 呢?其实这样是等价的,完全就相当于将之前的方法倒转过来(翻转不翻转操作颠倒)。

代码

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带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

京东 京东零售 总包63w
起床了的佳佳:要是我看前面就直接决定了, 你还分析,羡慕死了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务