1072：按列翻转得到最大值等行数（1797 分）

力扣第 139 场周赛第 2 题

题目

给定 m x n 矩阵 matrix 。

你可以从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

返回 经过一些翻转后，行内所有值都相等的最大行数 。

示例 1：

输入：matrix = [[0,1],[1,1]]
输出：1
解释：不进行翻转，有 1 行所有值都相等。

示例 2：

输入：matrix = [[0,1],[1,0]]
输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。

示例 3：

输入：matrix = [[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] == 0 或 1

分析

假设翻转一些列后，行 r 变为全等，那么只有和 r 完全相同或刚好每位都与 r 相反的 r‘，才能也变为全等。

因此，将 r 和 r’ 中较大的作为 key，统计出现最多的次数即可。

解答

1
2
3
4
5
6

def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
	ct = Counter()
	for row in matrix:
		key = tuple(row) if row[0] else tuple(x^1 for x in row)
		ct[key] += 1
	return max(ct.values())

128 ms