# 哈希表

$dp[j]$ : 第 $j$ 列的最大行数的集合

当前 $j$ 列可以翻与不翻，更 $dp[j - 1]$ 中每个元素比较，选择最大行数的集合作为 $dp[j]$

上述有问题：因为有可能「最大行数相同需要都要比较」，导致不断地 $2$ 倍增加

只需要找互补数目，只有互补无论怎么翻不翻转，最终都是一样的

例如： $101\\010$ $000\\111$

而： $100\\001$ 却不行，需要每一位都互补

统计每个数目对应的「互补 / 相同数目的数量」，最后比较个数

	class Solution {
	public int maxEqualRowsAfterFlips(int[][] matrix) {
	// 0 0 0
	// 0 0 1
	// 1 1 0
	// 不行，因为有可能最大行数相同需要都要比较，导致不断地 2 倍增加
	//dp [j]: 第 j 列的最大行数的集合
	// 当前 j 列可以翻与不翻，更 dp [j - 1] 中元素比较

	// 找互补数目，只有互补无论怎么翻不翻转，最终都是一样的
	// 101; 000
	// 010; 111
	// 100, 001 不行
	// 要互补，例如：101 去寻找 010
	// 统计每个数目对应的互补 / 相同数目的数量，最后比较个数
	Map<String, Integer> map = new HashMap<>();
	for (int[] row : matrix) {
	// 不互补
	StringBuilder sb1 = new StringBuilder();
	// 互补
	StringBuilder sb2 = new StringBuilder();
	for (int v : row) {
	sb1.append(v);
	sb2.append(v == 0 ? 1 : 0);
	}
	String s1 = sb1.toString();
	String s2 = sb2.toString();
	if (map.containsKey(s1)) {
	map.put(s1, map.get(s1) + 1);
	} else if (map.containsKey(s2)) {
	map.put(s2, map.get(s2) + 1);
	} else {
	// 都没有
	map.put(s1, 1);
	}
	}
	int ans = 0;
	for (Integer value : map.values()) {
	ans = Math.max(value, ans);
	}
	return ans;
	}
	}

# 哈希表 + 异或优化

可以对上述使用异或优化以下，对开头为 $1$ 的元素进行翻转

例如： $010$ 与 $101$ ，若二者互补，则开头必然相反，则统一将开头为 $1$ 的元素进行翻转

	class Solution {
	public int maxEqualRowsAfterFlips(int[][] matrix) {
	// 0 0 0
	// 0 0 1
	// 1 1 0
	// 不行，因为有可能最大行数相同需要都要比较，导致不断地 2 倍增加
	//dp [j]: 第 j 列的最大行数的集合
	// 当前 j 列可以翻与不翻，更 dp [j - 1] 中元素比较

	// 找互补数目，只有互补无论怎么翻不翻转，最终都是一样的
	// 101; 000
	// 010; 111
	// 100, 001 不行
	// 要互补，例如：101 去寻找 010
	// 统计每个数目对应的互补 / 相同数目的数量，最后比较个数
	Map<String, Integer> map = new HashMap<>();
	int m = matrix[0].length;
	for (int[] row : matrix) {
	// 统一将元素 1 开头的元素翻转
	int v = row[0];
	char[] cs = new char[m];
	for (int i = 0; i < m; i++) {
	cs[i] = (char) (row[i] ^ v + '0');
	}
	String s = new String(cs);
	map.put(s, map.getOrDefault(s, 0) + 1);
	}
	int ans = 0;
	for (Integer value : map.values()) {
	ans = Math.max(value, ans);
	}
	return ans;
	}
	}