LeetCode 题解工作台
最少翻转次数使二进制矩阵回文 I
给你一个 m x n 的二进制矩阵 grid 。 如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。 你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。 请你返回 最少 翻转次数，使得矩阵 要么 所有行…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们分别计算行和列的翻转次数，记为 和 ，最后取二者的最小值即可。 时间复杂度 $O(m \times n)$，其中 和 分别是矩阵 的行数和列数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。
请你返回 最少 翻转次数，使得矩阵 要么 所有行是 回文的 ，要么所有列是 回文的 。
示例 1：
输入：grid = [[1,0,0],[0,0,0],[0,0,1]]
输出：2
解释：
将高亮的格子翻转，得到所有行都是回文的。
示例 2：
输入：grid = [[0,1],[0,1],[0,0]]
输出：1
解释：
将高亮的格子翻转，得到所有列都是回文的。
示例 3：
输入：grid = [[1],[0]]
输出：0
解释：
所有行已经是回文的。
提示：
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])
cnt1 = cnt2 = 0
for row in grid:
for j in range(n // 2):
if row[j] != row[n - j - 1]:
cnt1 += 1
for j in range(n):
for i in range(m // 2):
if grid[i][j] != grid[m - i - 1][j]:
cnt2 += 1
return min(cnt1, cnt2)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m*n) because every cell is visited at most once via two-pointer comparisons. Space complexity is O(1) beyond the input grid, as only counters for symmetric groups are stored. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you comparing symmetric cells only once per pair?
- question_mark
Can you track multiple cells together to minimize flips?
- question_mark
Does your approach handle grids with odd and even dimensions correctly?
常见陷阱
外企场景- error
Flipping cells without checking all symmetric counterparts, leading to extra flips.
- error
Miscounting flips in overlapping groups of four cells.
- error
Ignoring odd-length rows or columns, which have a central element that should not be double-flipped.
进阶变体
外企场景- arrow_right_alt
Minimum flips for only row palindromes or only column palindromes.
- arrow_right_alt
Grids where only a subset of rows or columns need palindromic correction.
- arrow_right_alt
Larger grids requiring optimized grouping beyond 2x2 symmetric blocks.