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

这道题到底在问什么

输入

matrix=[[0,1],[1,1]]

输出

1

输入

matrix=[[0,1],[1,0]]

输出

2 · 翻第 0 列后两行各自全相等

先想最直接的笨办法

整道题收束成一句话:把每行规范化成模式,模式相同的行能一起翻成行内全相等,哈希数出现次数最多的那种模式,次数就是答案。这里是 3。一次扫描就解决,不用真去枚举翻哪些列。（动画第 24 步）

最优解：一步一步想明白

1. 3记牢这把尺子:每行压成一串 0/1 模式,首位永远是 0,模式一样的行能一起翻成行内全相等。下面每一帧都在套它。
2. 4原矩阵 4 行 4 列,每格非 0 即 1这是原始矩阵,绿格是 1、蓝格是 0。我们一行一行处理,给每行算一个模式串,再把模式丢进右边的计数表。先想清楚一件事:每行单独都能翻成行内全相等(把和首格不同的列翻掉就行),所以要数的不是一行行不行,关键是哪些行需要翻的列一模一样、能一起翻齐。模式串记的,就是每行该翻哪些列。
3. 5以每行首元素为基准,其余格和它比「同记 0、异记 1」高亮的这一列是每行的「基准」,也就是各行的第 0 个元素。规范化的做法是:让基准位永远记成 0,其余每格和基准比,一样记 0、不一样记 1。这串 0/1 其实是一张「翻法清单」:记 1 的列要翻、记 0 的列不翻,翻完整行就都和首格对齐、变成全相等。两行如果清单(模式)一模一样,要翻的列就完全相同,自然能用同一组翻列一起变齐,所以模式才是判断的依据。
4. 6第 0 行 = [0, 1, 1, 0],基准(首元素)= 0轮到第 0 行(紫色),内容是 [0, 1, 1, 0]。它的基准是首元素 0。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
5. 7第 0 格是 0,基准是 0,相同记 0第 0 格就是基准本身,和自己当然相同,记成 0。模式开头先有一个 0,后面所有格都拿它当尺子。
6. 8第 1 格是 1,基准是 0,不同记 1第 1 格是 1,基准是 0,两者不同,记 1。模式拼到 01。
7. 9第 2 格是 1,基准是 0,不同记 1第 2 格是 1,基准是 0,两者不同,记 1。模式拼到 011。
8. 10第 3 格是 0,基准是 0,相同记 0第 3 格是 0,基准是 0,两者相同,记 0。模式拼到 0110。
9. 11模式 0110 计数变成 1,当前最多 1第 0 行的模式是 0110。把它丢进右边计数表,出现 1 次。当前能凑齐行内全相等的行数最多是 1。
10. 12第 1 行 = [1, 0, 0, 1],基准(首元素)= 1轮到第 1 行(紫色),内容是 [1, 0, 0, 1]。它的基准是首元素 1。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
11. 13逐格和基准 1 比,得到模式 0110第 1 行每个格子和基准 1 比:相同记 0、不同记 1,拼出来是 0110。注意,这和前面第 0 行的模式一模一样。
12. 14模式 0110 计数变成 2,当前最多 2模式 0110 入表,现在出现 2 次。计数表里最高的一格是 2,它就是目前能凑齐行内全相等的最大行数。
13. 15第 2 行 = [0, 0, 1, 0],基准(首元素)= 0轮到第 2 行(紫色),内容是 [0, 0, 1, 0]。它的基准是首元素 0。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
14. 16逐格和基准 0 比,得到模式 0010第 2 行每个格子和基准 0 比:相同记 0、不同记 1,拼出来是 0010。这是一个新模式。
15. 17模式 0010 计数变成 1,当前最多 2模式 0010 入表,现在出现 1 次。计数表里最高的一格是 2,它就是目前能凑齐行内全相等的最大行数。
16. 18第 3 行 = [1, 0, 0, 1],基准(首元素)= 1轮到第 3 行(紫色),内容是 [1, 0, 0, 1]。它的基准是首元素 1。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
17. 19逐格和基准 1 比,得到模式 0110第 3 行每个格子和基准 1 比:相同记 0、不同记 1,拼出来是 0110。注意,这和前面第 0 行的模式一模一样。
18. 20模式 0110 计数变成 3,当前最多 3模式 0110 入表,现在出现 3 次。计数表里最高的一格是 3,它就是目前能凑齐行内全相等的最大行数。
19. 210110 出现 3 次(第 0/1/3 行),0010 出现 1 次四行都规范化完了。计数表里 0110 出现 3 次、0010 出现 1 次。次数最多的是 0110,有 3 行。也就是说,有一组翻列能让这 3 行同时变成行内全相等。答案就是这个最大次数 3。
20. 22对模式 0110,翻基准为 0 时记 1 的那两列即可验证一下 0110 这组。模式里记 1 的位是第 1 列和第 2 列(闪红的两列),把它们整列翻过来,就能让所有 0110 的行各自变成行内全相等。下一帧看翻完的样子。
21. 23翻列后第 0 行全 0、第 1/3 行全 1,共 3 行达标翻完第 1、2 列:第 0 行变成 0000、第 1 行和第 3 行都变成 1111,这三行各自行内全相等(紫色高亮)。第 2 行变成 0100,还是混的、不达标。达标的恰好 3 行,和模式 0110 的出现次数对上了。
22. 24出现最多的模式次数 = 行内全相等的最大行数 = 3整道题收束成一句话:把每行规范化成模式,模式相同的行能一起翻成行内全相等,哈希数出现次数最多的那种模式,次数就是答案。这里是 3。一次扫描就解决,不用真去枚举翻哪些列。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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())

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问