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> &matrix) {
int n = matrix[0].size();
unordered_map mp;
for (const auto &row: matrix) {
string s(n, '0');
for (int j = 0; j 时间复杂度：O(mn)
空间复杂度：O(m)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
