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

简介: . 翻转矩阵后的得分

题目描述



image.png

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

提示


image.png

题解


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

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

二进制枚举


image.png

贪心



image.png

image.png


c++

classSolution {
public:   
intmatrixScore(vector<vector<int>>&A) {   
intn=A.size(), m=A[0].size();  
for (inti=0; i<n; ++i) {     
if (A[i][0]) continue;    
for (intj=0; j<m; ++j) {    
A[i][j] ^=1;     
            }     
        }    
intres= (1<<(m-1)) *n;  
for (intj=1; j<m; ++j) 
        {            intcnt=0;  
for (inti=0; i<n; ++i)
         {                cnt+=A[i][j];   
         }        
cnt=max(cnt, n-cnt);     
res+= (1<<(m-1-j)) *cnt;    
        }        
returnres;  
    }
};

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


相关文章
|
22天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
3月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
9天前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
17 2
|
15天前
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
15 4
|
19天前
【LeetCode】整数翻转
【LeetCode】整数翻转
13 1
|
13天前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
56 0
|
17天前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
14 0
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
46 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
47 1