按列翻转得到最大值等行数 图解题解

翻列翻的是什么，最后要数哪种行

给一个只含 0 和 1 的矩阵 matrix，一次操作是挑一整列、把这列里每个 0 和 1 全部取反，可以翻任意多列。要数的不是两行彼此相等，而是某一行自己内部的值全都一样（全 0 或全 1）。翻完之后最多能有多少行做到行内全相等？题面示例 matrix=[[0,1],[1,0]]，翻第 0 列后两行各自全相等，答案是 2。

枚举所有翻法，2ⁿ 会把时间拖垮

n 列里每一列都有翻或不翻两个选择，把所有翻法枚举一遍就是 2ⁿ 种组合，每种还要扫一遍矩阵数出有几行达标，合计 O(2ⁿ·m·n)。列数刚到二十，2ⁿ 就过百万，这条硬枚举的路根本走不动，得找个只扫一遍矩阵就能定答案的办法。

翻掉一整列，行内的相对模式为什么纹丝不动

先盯住单独一行：要让它行内全相等，翻法其实是定死的——凡是和首元素不同的那些列都翻掉，这行立刻变成全 0 或全 1。所以每行都自带一张『翻法清单』。

这张清单只记录行内各格与首元素的相对关系，而翻一整列恰恰动不了这层关系：某格本来和首元素相同，翻这列时首元素也在这列、跟着一起翻，两者仍旧相同；本来不同的也依然不同。既然翻列不改变行内的相对模式，两行能不能用同一组翻列一起达标，就只看它们的相对模式是否完全一致。把每行按『和首元素相同记 0、不同记 1』压成一串 0/1 模式，模式相同的行就是能一起翻齐的行。

统一以首元素定 0 与 1，再拿哈希数模式

落到代码上只有两步。第一步规范化：所有行用同一个口径，以首元素为基准、同记 0 异记 1，这么一压，原始就相同的行和每一位都相反的互补行会得到同一串模式、落进同一个键。第二步计数：把每行的模式丢进哈希表，按键累加次数、平均常数时间就能存取，最后取出现次数最多的那种模式，它的次数就是能同时行内全相等的最大行数。口径必须全表统一，若一行拿首元素当基准、另一行拿别的列，同类就会被拆散、答案跟着错。

对着题面两个矩阵，亲手数一遍模式

第一个示例 matrix=[[0,1],[1,1]]：第一行 [0,1] 首元素是 0，保留原样，模式记成 01；第二行 [1,1] 首元素是 1，每一位异或 1、也就是两位相同得 0 不同得 1，翻过来模式记成 00。两串模式各出现 1 次，最多 1 行，答案 1。第二个示例 matrix=[[0,1],[1,0]]：第一行 [0,1] 模式还是 01；第二行 [1,0] 首元素是 1，异或 1 之后也得到 01。同一串 01 出现了 2 次，答案是 2——对应翻第 0 列，两行正好各自全相等。

互补行凭什么同组，模式全不同又剩几行

复杂度上，每格只参与一次模式计算，时间 O(m·n)；哈希表最坏要存 m 个长度为 n 的键，空间 O(m·n)。有两处地方容易想岔。一处是互补的两行，像 [0,1] 和 [1,0]，表面每位都相反，规范化后却落到同一个键、能一起达标数成 2，别被相反的外表骗过去。另一处是每行模式各不相同时，哈希表里每个键都只有 1，最多只能有一行做到行内全相等。最后别把题意读成『找两行相等』，它要的是一行内部全相同，目标看错，后面全白算。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cnt = Counter()
        for row in matrix:
            t = tuple(row) if row[0] == 0 else tuple(x ^ 1 for x in row)
            cnt[t] += 1
        return max(cnt.values())

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> cnt;
        int ans = 0;
        for (auto& row : matrix) {
            string s;
            for (int x : row) {
                s.push_back('0' + (row[0] == 0 ? x : x ^ 1));
            }
            ans = max(ans, ++cnt[s]);
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> cnt = new HashMap<>();
        int ans = 0, n = matrix[0].length;
        for (int[] row : matrix) {
            char[] cs = new char[n];
            for (int i = 0; i < n; ++i) {
                cs[i] = (char) (row[0] ^ row[i]);
            }
            ans = Math.max(ans, cnt.merge(String.valueOf(cs), 1, Integer::sum));
        }
        return ans;
    }
}