LeetCode周赛的一道题。。
来源：11-1 结语
慕桂英雄
2019-06-02
在leetcode上刷了接近100题了吧，参加了139周赛。。
然而第二题就卡住了。。一开始想着用动态规划，但是越想越复杂。。除了暴力解没有其他有效的方法能说服自己。
https://leetcode-cn.com/contest/weekly-contest-139/problems/flip-columns-for-maximum-number-of-equal-rows/
5077. 按列翻转得到最大值等行数 显示英文描述 我的提交返回竞赛
题目难度 Medium
给定由若干 0 和 1 组成的矩阵 matrix，从中选出任意数量的列并翻转其上的 每个 单元格。翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。
返回经过一些翻转后，行上所有值都相等的最大行数。
其中一个大神的代码是这样的，但是没理解为什么能这么处理。。
class Solution {
public:
int maxEqualRowsAfterFlips(vector<vector>& a) {
int n = a.size();
int m = a[0].size();
map<vector, int> F;
for (int i = 0; i < n; ++ i)
{
if (a[i][0] == 1)
{
for (int j = 0; j < m; ++ j)
a[i][j] ^= 1;
}
F[a[i]] ++;
}
int ans = 0;
for (auto p : F)
ans = max(ans, p.second);
return ans;
}
};
1回答
-
就是要找到矩阵中有多少行是“模式一致”的。在这里，对“模式一致”的定义是：两行或者完全相同，或者正好相反。
比如：
0, 0 , 1, 1, 1 和 0, 0 , 1, 1, 1 是模式一致的，肯定没问题；
0, 0 , 1, 1, 1 和 1, 1, 0, 0, 0 也是模式一致的。因为对这两行来说，我们同时翻转0，1列或者同时翻转2，3，4列，都能得到两个元素全相同的行，所以，这两行也是模式一致的。
可以看出来，模式一致的行，我们只需要翻转相同的列，就好了。问题变成了寻找，哪个模式，属于这个模式一致的行最多？
由于每一行，都对应了两个模式，我们把首个元素为1的行，修改为对应的，首个元素为0的模式。
所以，1, 1, 0, 0, 0这样的行，我们说它的模式是0, 0, 1, 1, 1
第一个for循环就在做这件事。然后，a里存的就是每一行的“模式数组”，放进了F中计数。
最后，遍历一遍F，找频率最大的那个频率值，就是结果：）
继续加油！：）
022019-06-16
相似问题