题目描述
思路解析动画文字版
记牢这把尺子:两端相等就各翻一次,两端不同就不动,正中间单独翻一次。下面每一帧都在套它。
输入矩阵 · 3×3 · 绿=1 蓝=0：这是原始图片,绿色格是 1、蓝色格是 0。我们一行一行地处理,每行用左右两个指针向中间收。
聚焦第 0 行 · 摆好双指针：轮到第 0 行,内容是 [1, 1, 0]。把左指针放在头、右指针放在尾,紫色标出这两端,准备向中间收。
比较两端 · 位置 0 与 2：看这一行的两端:位置 0 是 1,位置 2 是 0。它们不同。互换后再取反正好抵消,所以这两端最终保持原样,不用动。
不同 → 两端保持不变：两端不同,什么都不用改,位置 0 还是 1、位置 2 还是 0。两个指针各自向中间挪一格。
正中间一格 · 位置 1：两个指针在位置 1 相遇,这是正中间那一格,值是 1。它水平翻转后位置不变,所以没有「互相抵消」这回事,只需要老老实实取反一次。
中点取反 → 0：中点从 1 取反成 0(红色闪一下)。这一行所有格子都处理完了。
第 0 行完成 · [1, 0, 0]：第 0 行收工,结果是 [1, 0, 0]。已完成行数加一,接着处理下一行,套路完全一样。
聚焦第 1 行 · 摆好双指针：轮到第 1 行,内容是 [1, 0, 1]。把左指针放在头、右指针放在尾,紫色标出这两端,准备向中间收。
比较两端 · 位置 0 与 2：看这一行的两端:位置 0 是 1,位置 2 是 1。它们相等。水平翻转会把它俩互换,换完仍相等,再各取反,等于两端都要翻一次。
相等 → 两端各翻一次：两端相等,各翻一次:位置 0 变 0、位置 2 变 0(红色闪一下表示刚翻)。这一帧就同时做完了这对格子的翻转和取反。
正中间一格 · 位置 1：两个指针在位置 1 相遇,这是正中间那一格,值是 0。它水平翻转后位置不变,所以没有「互相抵消」这回事,只需要老老实实取反一次。
中点取反 → 1：中点从 0 取反成 1(红色闪一下)。这一行所有格子都处理完了。
第 1 行完成 · [0, 1, 0]：第 1 行收工,结果是 [0, 1, 0]。已完成行数加一,接着处理下一行,套路完全一样。
聚焦第 2 行 · 摆好双指针：轮到第 2 行,内容是 [0, 0, 0]。把左指针放在头、右指针放在尾,紫色标出这两端,准备向中间收。
比较两端 · 位置 0 与 2：看这一行的两端:位置 0 是 0,位置 2 是 0。它们相等。水平翻转会把它俩互换,换完仍相等,再各取反,等于两端都要翻一次。
相等 → 两端各翻一次：两端相等,各翻一次:位置 0 变 1、位置 2 变 1(红色闪一下表示刚翻)。这一帧就同时做完了这对格子的翻转和取反。
正中间一格 · 位置 1：两个指针在位置 1 相遇,这是正中间那一格,值是 0。它水平翻转后位置不变,所以没有「互相抵消」这回事,只需要老老实实取反一次。
中点取反 → 1：中点从 0 取反成 1(红色闪一下)。这一行所有格子都处理完了。
第 2 行完成 · [1, 1, 1]：第 2 行收工,结果是 [1, 1, 1]。三行全部处理完毕,下一帧返回结果。
全部完成 · 返回结果矩阵：三行全部处理完,矩阵变成 [[1,0,0],[0,1,0],[1,1,1]]。每一行都是「逆序 + 取反」的结果,而我们只用一遍双指针就一次性做完了两步。
对照验证 · 两步法同样结果：换个老实办法验证一下:把每行先逆序、再把全图 0 和 1 互换,得到的矩阵和上一帧完全相同。可见双指针那套「相等才翻、不同不动、中点单翻」确实等价于规规矩矩的两步法。
边界先想清:1×1 只取反;偶数边长没有中点,所有格子成对处理。
两个高频追问:合并两步靠逐对算净效果;偶数无中点、奇数补中点。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]: n = len(image) for row in image: i, j = 0, n - 1 while i < j: if row[i] == row[j]: row[i] ^= 1 row[j] ^= 1 i, j = i + 1, j - 1 if i == j: row[i] ^= 1 return image复杂度
- 时间：O(n²)，矩阵共 n×n 个格子,每格恰好被一个指针碰一次,无重复无回头
- 空间：O(1)，原地修改矩阵,只用 i、j 两个指针变量,不开额外矩阵
易错点
面试追问把动画讲成自己的话
追问为什么一遍双指针就能把「翻转」和「取反」两步合并?
追问如果边长是偶数,会不会漏处理某些格子?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按奇偶排序数组
LeetCode 905 · 简单 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题