LeetCode 题解工作台
最少翻转次数使二进制矩阵回文 II
给你一个 m x n 的二进制矩阵 grid 。 如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。 你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。 请你返回 最少 翻转次数，使得矩阵中 所有 行和…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
行和列都是回文的，那么对于任意 $i \in [0, m / 2)$ 和 $j \in [0, n / 2)$，都需要满足 $\text{grid}[i][j] = \text{grid}[m - i - 1][j] = \text{grid}[i][n - j - 1] = \text{grid}[m - i - 1][n - j - 1]$，要么都变成 ，要么都变成 ，变成 的次数为 $c_…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。
请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。
示例 1：
输入：grid = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解释：
示例 2：
输入：grid = [[0,1],[0,1],[0,0]]
输出：2
解释：
示例 3：
输入：grid = [[1],[1]]
输出：2
解释：
提示：
m == grid.lengthn == grid[i].length1 <= m * n <= 2 * 1050 <= grid[i][j] <= 1
解题思路
方法一：分类讨论
行和列都是回文的，那么对于任意 和 ，都需要满足 ，要么都变成 ，要么都变成 ，变成 的次数为 ，变成 的次数为 ，取两者的较小值，累加到答案中。
接下来，我们再讨论 和 的奇偶性：
- 如果 和 都是偶数，那么直接返回答案；
- 如果 和 都是奇数，那么最中间的格子只能是 ，因为题目要求 的数目可以被 整除；
- 如果 是奇数，而 是偶数，那么我们需要考虑最中间的一行；
- 如果 是偶数，而 是奇数，那么我们需要考虑最中间的一列。
对于后两种情况，我们需要统计最中间的一行或一列中对应位置不相同的格子对数 ，以及对应位置相同且为 的格子个数 ，然后再分情况讨论：
- 如果 ，那么我们只需要将 个格子变成 即可，操作次数为 ；
- 否则，说明 ，此时如果 ，我们可以将其中一个格子变成 ，使得 ，那么剩下的 个格子变成 即可，操作次数一共为 。
- 否则，如果 ，我们就把 个格子变成 ，使得 ，操作次数为 。
我们将操作次数累加到答案中，最后返回答案即可。
时间复杂度 ，其中 和 分别是矩阵的行数和列数。空间复杂度 。
class Solution:
def minFlips(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ans = 0
for i in range(m // 2):
for j in range(n // 2):
x, y = m - i - 1, n - j - 1
cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y]
ans += min(cnt1, 4 - cnt1)
if m % 2 and n % 2:
ans += grid[m // 2][n // 2]
diff = cnt1 = 0
if m % 2:
for j in range(n // 2):
if grid[m // 2][j] == grid[m // 2][n - j - 1]:
cnt1 += grid[m // 2][j] * 2
else:
diff += 1
if n % 2:
for i in range(m // 2):
if grid[i][n // 2] == grid[m - i - 1][n // 2]:
cnt1 += grid[i][n // 2] * 2
else:
diff += 1
ans += diff if cnt1 % 4 == 0 or diff else 2
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Does the candidate understand two-pointer scanning?
- question_mark
Is the candidate tracking mirrored pairs correctly?
- question_mark
Can the candidate optimize for minimal flip calculations?
常见陷阱
外企场景- error
Not correctly identifying mirrored pairs across the grid edges.
- error
Failing to track the invariant condition of symmetry while counting flips.
- error
Trying to solve the problem without recognizing that both row and column palindromes must be considered simultaneously.
进阶变体
外企场景- arrow_right_alt
Handling grids where all values are initially palindromic.
- arrow_right_alt
Optimizing for larger grids with minimal space overhead.
- arrow_right_alt
Dealing with cases where certain rows or columns are already palindromic.