LeetCode周赛的一道题。。

Question

在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;
}
};

Answer 1

liuyubobobo 2019-06-02 16:17:53

就是要找到矩阵中有多少行是“模式一致”的。在这里，对“模式一致”的定义是：两行或者完全相同，或者正好相反。

比如：

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，找频率最大的那个频率值，就是结果：）

继续加油！：）

• 提问者 慕桂英雄 #1

  感谢bobo老师的分析，现在思路清晰了，意思就是只要模式相同的话，需要若干次列变换，那些模式相同的行就会行内每个元素相同。模式不同的行怎么变也没用。。。
  而即使模式相同也有开头是0或者1的两种表示。。所以要先统一一下表示方式，然后做简单的频率统计返回最多的个数。

• 提问者 慕桂英雄 #2

  非常感谢！