题目描述
思路解析动画文字版
记住这套「两端交换、双指针向中间靠拢」,下面每一帧都在套它。
开局:左指针 l 落在第 0 位 d、右指针 r 落在第 12 位 e。只要 l < r 就交换两端,再一起往中间挪。
第 1 次:l 指着 d、r 指着 e,l < r 成立,这两端该互换。
交换完成:e 换到第 0 位、d 换到第 12 位(绿色=已归位),这两个字符之后不用再动。
指针内移:l 右移到 1、r 左移到 11,继续。
第 2 次:l 指着 a、r 指着 r,l < r 成立,这两端该互换。
交换完成:r 换到第 1 位、a 换到第 11 位(绿色=已归位),这两个字符之后不用再动。
指针内移:l 右移到 2、r 左移到 10,继续。
第 3 次:l 指着 t、r 指着 u,l < r 成立,这两端该互换。
交换完成:u 换到第 2 位、t 换到第 10 位(绿色=已归位),这两个字符之后不用再动。
指针内移:l 右移到 3、r 左移到 9,继续。
第 4 次:l 指着 a、r 指着 t,l < r 成立,这两端该互换。
交换完成:t 换到第 3 位、a 换到第 9 位(绿色=已归位),这两个字符之后不用再动。
指针内移:l 右移到 4、r 左移到 8,继续。
第 5 次:l 指着 s、r 指着 c,l < r 成立,这两端该互换。
交换完成:c 换到第 4 位、s 换到第 8 位(绿色=已归位),这两个字符之后不用再动。
指针内移:l 右移到 5、r 左移到 7,继续。
第 6 次:l 指着 t、r 指着 u,l < r 成立,这两端该互换。
交换完成:u 换到第 5 位、t 换到第 7 位(绿色=已归位),这两个字符之后不用再动。
指针内移:l 和 r 在中点 6 相遇,停。
l 和 r 会合,反转完成,整串变成 erutcurtsatad。正中央第 6 位的 r 没有配对,自己留在原地。全程只在原数组上两两对调、没开新数组,空间 O(1)。
边界先想清:空和单字符都不进循环,本来就无需反转。
两个高频追问,重点是「不可变字符串要先转数组」。
参考代码
from typing import Listclass Solution: def reverseString(self, s: List[str]) -> None: l, r = 0, len(s) - 1 while l < r: s[l], s[r] = s[r], s[l] l += 1 r -= 1复杂度
- 时间:O(n),每个字符只被指针碰一次,一共换 n/2 次
- 空间:O(1),只用 l、r 两个下标,就地交换不开数组
易错点
面试追问把动画讲成自己的话
追问如果是反转「字符串」而不是字符数组,做法一样吗?
追问能不能用语言自带的 reverse 函数?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
反转字符串中的元音
LeetCode 345 · 简单 · 沿着 双指针套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题