LeetCode 题解工作台
转化为全零矩阵的最少反转次数
给你一个 m x n 的二进制矩阵 mat 。每一步，你可以选择一个单元格并将它反转（反转表示 0 变 1 ， 1 变 0 ）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。相邻的两个单元格共享同一条边。 请你返回将矩阵 mat 转化为全零矩阵的 最少反转次数 ，如果无法转化为全零矩阵，…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class Solution: def minFlips(self, mat: List[List[int]]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 m x n 的二进制矩阵 mat。每一步，你可以选择一个单元格并将它反转（反转表示 0 变 1 ，1 变 0 ）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。相邻的两个单元格共享同一条边。
请你返回将矩阵 mat 转化为全零矩阵的最少反转次数，如果无法转化为全零矩阵，请返回 -1 。
二进制矩阵 的每一个格子要么是 0 要么是 1 。
全零矩阵 是所有格子都为 0 的矩阵。
示例 1：
输入：mat = [[0,0],[0,1]] 输出：3 解释：一个可能的解是反转 (1, 0)，然后 (0, 1) ，最后是 (1, 1) 。
示例 2：
输入：mat = [[0]] 输出：0 解释：给出的矩阵是全零矩阵，所以你不需要改变它。
示例 3：
输入：mat = [[1,0,0],[1,0,0]] 输出：-1 解释：该矩阵无法转变成全零矩阵
提示：
m == mat.lengthn == mat[0].length1 <= m <= 31 <= n <= 3mat[i][j]是 0 或 1 。
解题思路
方法一：状态压缩 + BFS
class Solution:
def minFlips(self, mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
state = sum(1 << (i * n + j) for i in range(m) for j in range(n) if mat[i][j])
q = deque([state])
vis = {state}
ans = 0
dirs = [0, -1, 0, 1, 0, 0]
while q:
for _ in range(len(q)):
state = q.popleft()
if state == 0:
return ans
for i in range(m):
for j in range(n):
nxt = state
for k in range(5):
x, y = i + dirs[k], j + dirs[k + 1]
if not 0 <= x < m or not 0 <= y < n:
continue
if nxt & (1 << (x * n + y)):
nxt -= 1 << (x * n + y)
else:
nxt |= 1 << (x * n + y)
if nxt not in vis:
vis.add(nxt)
q.append(nxt)
ans += 1
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(M * N * 2^(M _N)) due to exploring all flip combinations for M x N matrix. Space complexity is O(2^(M_ N)) for the hash table storing visited states. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Exploring small matrices with exponential state space is expected; interviewer may hint at bitmask BFS.
- question_mark
Mentioning repeated flips canceling each other can guide toward combination enumeration rather than naive recursion.
- question_mark
Using hash sets to avoid revisiting states is crucial for correctness and efficiency.
常见陷阱
外企场景- error
Flipping a cell twice is redundant, but forgetting this leads to overcounting steps.
- error
Not representing matrix as a bitmask may cause inefficient state storage and slow BFS.
- error
Neglecting to track visited states can cause infinite loops in BFS.
进阶变体
外企场景- arrow_right_alt
Allow larger matrices where optimized pruning is required beyond BFS.
- arrow_right_alt
Only allow flipping cells without affecting neighbors, changing the pattern to single-cell toggling.
- arrow_right_alt
Count flips required to convert to a specific target matrix rather than zero matrix.