1072. 按列翻转失去最大值等行数
关键词：哈希表、数组
题目起源：1072. 按列翻转失去最大值等行数 – 力扣（Leetcode）
题目形容
T 哈希表
T 数组 给定 m x n 矩阵 matrix。
你能够从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0。）
返回 通过一些翻转后，行与行之间所有值都相等的最大行数。
输出：matrix = [[0,1],[1,1]]
输入：1
解释：不进行翻转，有 1 行所有值都相等。 输出：matrix = [[0,1],[1,0]]
输入：2
解释：翻转第一列的值之后，这两行都由相等的值组成。 输出：matrix = [[0,0,0],[0,0,1],[1,1,0]]
输入：2
解释：翻转前两列的值之后，后两行由相等的值组成。问题剖析
论断：最初由雷同元素形成的行必然雷同或相同。
这个论断显然成立，最初由雷同元素形成的行要么全是 0，要么全是 1。
推论：最初由雷同元素形成的行在最后也是雷同或相同。
这个论断也很好证实，设 a 和 b 为最初由雷同元素组成的两行，若最初 a[i]=b[i]，因为每次操作会施加在同一列上，所以，对 a[i] 和 b[i] 施加的操作雷同，所以最后也有 a[i]=b[i]；若最初 a[i]!=b[i]，也即二者相同，同理，因为对二者施加的操作雷同，所以最后也有 a[i]!=b[i]。
由此，可将最后雷同或相同的行归为一类，于是，可将初始矩阵的行分为若干类，最初由雷同元素形成的行必然属于同一类，且该类只含这些行。故，要求最大行数，等价于求找到含有行数最多的类，该类含有的行数即为最大行数。
因为同一类的行雷同或相同，而属于该类的行要么以 0 结尾要么以 1 结尾，无妨将以 0 结尾的行作为该类的 key，对于以 1 结尾的行，将整行取反便失去其所属类的 key。由上，可失去每行的 key，从而统计出每类含有的行数，最初找到含有最多行数的类所含有的行数。
代码实现
int maxEqualRowsAfterFlips(vector<vector<int>> &matrix) {int n = matrix[0].size();
unordered_map<string, int> mp;
for (const auto &row: matrix) {string s(n, '0');
for (int j = 0; j < n; j++)
s[j] += row[j] ^ row[0]; // row[0] 为 1 则取反
mp[s]++;
}
// 找到蕴含行数最多的类别蕴含的行数
int res = 0;
for (auto &[k, v]: mp)
res = max(res, v);
return res;
}工夫复杂度：O(mn)
空间复杂度：O(m)