老铁们今天咱们来啃一道大厂机考笔试里出镜率极高的题LeetCode 151. 反转字符串中的单词。题目本身只有一句话但能把“字符串处理”“双端队列”“双指针”这几个高频考点全塞进去面试官还特别爱在这道题上追问空间复杂度。很多基础差的朋友一看到“原地反转”四个字就头皮发麻指针绕来绕去边界搞到崩溃。别慌我这次把代码完全嚼碎先带你用双端队列把思路跑通再上双指针原地解法两套方案都给你掰开揉碎保证你从零开始也能吃透下次机考遇到类似题目直接形成肌肉记忆。1. 先别动手写代码把题面嚼透1.1 题面翻译成人话原题英文是 Given an input string s, reverse the order of the words翻译成大白话就是给你一个字符串里面有几个单词单词之间用空格分隔。现在要把单词顺序颠倒同时去掉字符串首尾的多余空格把所有连续空格压缩成单个空格。看几个例子就明白了输入hello world- 输出world hello输入a good example- 输出example good a中间两个空格要压成一个输入 hello world - 输出world hello首尾空格要去掉输入a- 输出a注意一个很关键的细节这里的“单词”指的是连续的非空白字符。比如hello!123整体算一个单词哪怕里面带标点和数字只有空格才是单词分隔符。很多人理解成英文字母串结果把数字和标点处理错了这种失分特别冤。1.2 这题到底在考什么从一个面试官的角度来看这道题想考察三个能力第一你会不会用合适的工具处理字符串能不能自然想到“按空格切分”这个动作。第二你有没有空间复杂度的意识。双端队列虽然好写但能不能把它优化成 O(1) 的原地操作。第三你对边界条件的敏感度。全是空格、连续多个空格、首尾空格、只有一个单词这些用例在笔试里是必跑的。对基础差的同学来说这道题其实是一道分层题直接调库函数 split 也能过但会被面试官追问用双端队列是标准解法里最容易写对的一种用双指针原地翻转才是满分解法。你要做的是把这三级全部打通而不是只求一个 AC。1.3 基础差的人到底卡在哪儿我在带人刷题的过程中发现大家反复卡在这几个点上不知道很多语言的 split 默认会把连续空格当成一个分隔符还能过滤首尾空格结果自己在那里手动处理越写越乱。用 C 时不知道怎么按空格切分字符串去过 istringstream 但用得不够熟。双指针反转时对 reverse 的左闭右开区间记不牢导致单词的首字母或者尾字母没有被反转。先去除多余空格时用了 erase 一个一个删复杂度飙升还容易把迭代器搞失效。这些问题不是因为你笨而是因为你没有把每一步都落到纸面上推演。后面我会用两个完整的方法把每一行代码都过一遍保证你看完能自己复现。2. 方法一双端队列 双指针先保证能 AC2.1 为什么选双端队列这个思路非常直观我们从头扫描原字符串把每个单词按顺序抠出来。因为最终要“反转单词顺序”所以先出现的单词最终要放到后面。那每次抠出一个单词就把它从队头插进去等全部单词都入了队再从队头挨个取出来拼结果顺序自然就是反的。普通队列只能队尾插入、队头取出做不到“队头插入”所以必须用双端队列 deque。我给你打个比方就像你有一摞扑克牌每次摸到一张新牌就往牌堆最上面放。最后你把牌从上往下翻开得到的顺序正好和摸牌顺序相反。双端队列就是这个“牌堆”队头插入就是“放最上面”。2.2 Python 版用双指针切词 deque 存词先给一个清晰好懂的 Python 版本非常适合用它先理解逻辑from collections import deque class Solution: def reverseWords(self, s: str) - str: left, right 0, len(s) - 1 # 去掉首尾空格 while left right and s[left] : left 1 while left right and s[right] : right - 1 dq deque() word [] while left right: if s[left] ! : word.append(s[left]) elif word: # 一个单词结束整体塞到队头 dq.appendleft(.join(word)) word [] left 1 if word: dq.appendleft(.join(word)) return .join(dq)这段代码我一行一行给你说。left, right 0, len(s) - 1双指针一个指向字符串头一个指向尾。这里双指针的主要作用是划定“有效区间”。两个 while 循环分别移动 left 和 right直到它们指向非空格位置。这里用的是left right等号不能漏。如果是空字符串初始时 right 小于 left循环直接跳过后面主循环也不会执行最终返回空字符串。dq deque()创建双端队列word []用来临时攒一个单词的字符。主循环里只要当前字符不是空格就把它装进 word一旦遇到空格并且 word 不为空说明凑完了一个单词立刻用appendleft整体插入队头然后清空 word。循环结束后还有最后一个单词要补进去因为字符串末尾可能恰好不是空格主循环不会触发“遇到空格”的分支。最后 .join(dq)把队列里的单词按队头到队尾的顺序用单个空格连接得到最终结果。注意一个小细节elif word:判断的是 word 这个列表是否非空避免连续空格时把一个空列表反复塞进去。很多新手容易写成elif s[left] 而不判断 word最后 deque 里全是用空字符串 join 出来的空串拼接结果就会有多余空格。拿“牌堆”来想扫描hello world先摸到 hello放在牌堆顶再摸到 world也放在牌堆顶最终牌堆从上到下是 world、hello拼出来就是world hello。完美。2.3 标准 C 版LeetCode 官方思路的原型大厂机考很多同学用 C而且 C 的 deque 用起来也很顺。代码长这样class Solution { public: string reverseWords(string s) { int left 0, right s.size() - 1; // 去掉首尾空格 while (left right s[left] ) left; while (left right s[right] ) --right; dequestring d; string word; while (left right) { if (s[left] word ! ) { d.push_front(word); word ; } else if (s[left] ! ) { word s[left]; } left; } d.push_front(word); string ans; while (!d.empty()) { ans d.front(); d.pop_front(); if (!d.empty()) ans ; } return ans; } };几个容易错的地方我重点说一下。word ! 这个判断等价于 Python 里的elif word目的是防止连续空格时把空字符串塞进 deque。如果不加这个判断输出会变成world hello这种带多余空格的脏结果。循环结束后有一个d.push_front(word)这和 Python 里最后的if word是同一个道理。因为最后一个单词后面没有空格来触发入队必须手动补。拼答案时if (!d.empty()) ans ;是在每两个单词之间加空格。注意它放在弹出一个单词之后判断意思是“如果队列里还有东西就补一个空格”这样最后的单词后面不会多出尾巴空格。时间复杂度 O(n)n 是字符串长度空间复杂度 O(n)因为 deque 里存了所有单词。这个方案的优势是逻辑清晰、不容易写错作为笔试保底解法完全够用。劣势是额外用了 O(n) 空间面试官如果追问“能不能原地做”你得能接住。2.4 用表格推演一遍执行过程为了彻底嚼碎拿s hello world 这个输入推演 C 版的关键步骤。先去掉首尾空格后left 指向第一个 hright 指向最后一个 d。我们用左右指针框住了hello world这个有效区。然后开始扫描位置字符发生了什么deque 内容left 指向 hhword hwordh空......逐步攒出 hello空空格空格wordhellopush_front(hello)word清空[hello]下一个空格空格word,不处理[hello]......跳过连续空格[hello]指向 wwword w开始攒 world[hello]......逐步攒出 world[hello]空格空格wordworldpush_front(world)word清空[world,hello]循环结束—push_front(word)但 word 为空[world,hello]拼接时从队首拿 world拿完后队列还非空补一个空格再拿 hello队列为空不补空格。最终结果world hello。这里你会发现连续空格那段啥也没干直接被跳过了首尾空格在进入主循环前就被双指针排除。所以这个算法不需要额外写“删除空格”的逻辑跟后面双指针原地解法形成了鲜明对比。3. 方法二双指针原地反转冲刺 O(1) 空间如果面试官追问能不能不用额外空间就需要上原地算法。这个方法的精妙程度更高吃透以后非常爽。3.1 三步走的核心思想回想一下两个单词的列表反转最朴素的做法是“先反转整个序列再反转每个单词内部”。为什么因为第一次整体反转把单词顺序倒过来了但单词本身也变成了逆序。比如hello world整体反转得到dlrow olleh。这时候只要再把每个单词内部反转回去hello和world就恢复正常顺序也正确了。这个“反转两次等于不反转”的道理就是整个解法的基础。用式子表示设原串为“单词A 空格 单词B”整体反转后变成“B的逆序 空格 A的逆序”再对每个单词区间做反转得到“B 空格 A”。完美。但这里有个前提原字符串必须是干净的也就是没有首尾空格、没有连续空格。如果输入脏乱差直接整体反转再逐个反转结果里会到处是多余空格。所以原地解法第一步往往先把多余空格清掉。实操中我更推荐“先压缩空格再整体反转再逐词反转”这个顺序。3.2 快慢指针原地清除多余空格这一步是很多基础差考生的噩梦但记住一个模板就够了int slow 0; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast s.size() s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow);这四行模板值得一字一字嚼。slow 是“写入指针”新字符串写到哪个位置就靠它标记fast 是“读取指针”负责扫描原字符串。外部 if 判断当前 fast 指向的字符不是空格说明一个单词要开始了。if (slow ! 0)的意思是如果 slow 已经写过内容说明前面已经有单词那在新单词开头之前必须补一个空格。为什么用 slow ! 0因为 slow 从 0 开始第一个单词前面不需要空格之后每写一个新单词都以一个空格开头从而保证单词之间只有一个空格。内部 while 把整个单词从 fast 位置复制到 slow 位置。注意 fast 在复制过程中也在移动所以它会跳到单词末尾后的空格处正好为下一轮循环做准备。复制完整个字符串后s.resize(slow)把字符串尾巴上多余内容全部砍掉。这一步非常关键很多人的答案末尾带一堆空格就是忘了 resize。给你一个生活化类比快指针 fast 是侦察兵负责探路找单词慢指针 slow 是抄写员负责把找到的单词整理誊写到纸上并在每个新单词前面画一个空格分隔符。侦察兵跳过垃圾抄写员只留干货。3.3 整体反转与逐词反转的代码清理干净后字符串是标准形式word1 word2 ... wordn。然后执行reverse(s.begin(), s.end()); int n s.size(); int i 0; while (i n) { int j i; while (j n s[j] ! ) j; reverse(s.begin() i, s.begin() j); i j 1; }这中间有一个无论如何都要记牢的知识点C 的reverse(first, last)反转的是左闭右开区间[first, last)last 指向的位置不参与反转。所以reverse(s.begin(), s.end())是对整个字符串做反转。找单词时j 从 i 开始扫到第一个空格或者字符串结束。此时[i, j)正好是单词区间直接 reverse。i j 1跳过那个空格指向下一个单词开头。如果 j 已经到 nj1 会大于 n外层 while 立刻退出不会越界。3.4 完整代码与逐段注释把三步串起来完整 C 实现如下class Solution { public: string reverseWords(string s) { // 1. 去除多余空格 int slow 0; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast s.size() s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow); // 2. 整体反转 reverse(s.begin(), s.end()); // 3. 逐个单词反转 int n s.size(); int i 0; while (i n) { int j i; while (j n s[j] ! ) j; reverse(s.begin() i, s.begin() j); i j 1; } return s; } };分三段解释第一段“洗牌”快慢指针把字符串整理成“单词 空格 单词 空格……”的干净形态同时砍掉尾部多余内容。第二段“倒序”整体反转让单词顺序颠倒但单词内部也是反的。第三段“矫正”按空格切出每个单词区间逐个内部反转恢复单词本来面貌。执行 hello world 的完整演变如下步骤结果原输入 hello world 去掉多余空格后hello world整体反转dlrow olleh反转第一个单词 dlrowworld olleh反转第二个单词 ollehworld hello看起来是不是特别顺这段代码的空间复杂度是 O(1)只用了几个 int 变量不依赖字符串长度。时间复杂度还是 O(n)扫描了两到三遍每次都是线性。3.5 两种方法怎么选做一张表给你对照维度双端队列 双指针双指针原地反转空间复杂度O(n)O(1)代码可读性直观易懂需要理解快慢指针和二次反转写错概率较低慢指针补空格那一段容易错面试加分合格明显加分体现优化意识适用场景笔试保底、快速 AC面试手撕、空间优化追问时我的建议很明确先保证自己能写对双端队列版再花时间攻原地版。两道程序都练到肌肉记忆机考时根据题目要求选一个。如果题目没有明确限制空间可以直接用双端队列版如果面试官追问“能不能省空间”直接切换原地版这就是稳稳的加分点。4. 机考实战中的坑与排查手册4.1 五个必须提前跑通的边界用例刷题只看题解没用必须用测试用例把自己容易写崩的地方提前踩完。这道题的高概率边界我整理成了表输入期待输出容易踩的坑跳过所有循环返回空串 去首尾空格后 left rightword 为空aa循环结束后必须 push 最后一个单词 hello world world hello首尾空格、中间单空格a good exampleexample good a连续空格只能压缩成一个我第一次写双端队列版时就挂在“全是空格”这个用例上。因为当时最后一句d.push_front(word)没判断 word 是否为空结果 deque 里多了个空字符串输出变成 也就是一个空格。加不加最后的 if 判断差别就在这种细微的地方。4.2 双指针原地版最容易错的三个位置第一慢指针补空格的写法。很多新手写成这样if (s[fast] ! ) { s[slow] ; ... }这样会导致字符串开头多一个空格。必须用if (slow ! 0)做保护让第一个单词前面不补空格。这个“第一个单词前无空格”的细节是整段代码的精髓。第二内部 while 结束后 fast 的落点。这个 while 每次循环结束时 fast 已经移动到了空格或字符串末尾。如果外部 for 没有意识到这一点在循环体里又对 fast 做多余的操作很容易跳过一个单词。遇到这种问题最好的办法是画下标变化图或者用调试器单步盯着看。第三忘记 resize。忘了 resize 的后果是清理后的字符串尾部还留着原来的字符整体反转后那些垃圾字符会跑到最前面结果完全错乱。我见过不少人反了三次还是不对最后发现是 resize 的位置写错了。4.3 不同语言的一些差异提醒如果你用 Python 写要注意 Python 字符串是不可变的不能真正“原地改”。但可以在字符列表上做快慢指针最后 join或者直接s.split()加反转拼接。面试时如果明确要求 O(1) 空间一般默认是 C/C 语境Python 里的“省空间”其实很难做到严格 O(1)需要主动说清楚语言特性。用 C 的同学还要注意istringstream这个工具istringstream iss(s); string word; while (iss word) { ... }它能自动按空白分割单词省去手写分割的一堆字符非常香。但对这道题不建议一上来就用它替代所有思维。面试官大概率会问你“你是怎么处理连续空格的”你如果说“流自动处理了”他多半会追问“那如果让你手写呢”4.4 这道题练完能顺带吃透哪些题我自己刷题的经验是一道好题的价值不在于 AC而在于你能把它迁移到多少同类题上。151 题练熟后建议再刷这几道反转字符串最简单版只需要reverse(s.begin(), s.end())用来熟悉左闭右开区间。反转字符串 II每隔 k 个字符反转前 k 个需要处理剩余字符不足 k 的边界。反转字符串中的单词 II进阶版题目保证没有多余空格只要求反转单词顺序等价于本题去掉“清洗”步骤后的核心三步。反转字符串中的单词 III要求保留单词顺序但反转每个单词内部跟本题的“单步反转”正好是镜像关系。把这些连在一起练字符串反转这个专题基本就吃透了。机考时碰到任何带“反转”字样的题第一反应都会比对手快很多。最后再分享一个我自己的体会。不要担心第一遍写不出来我见过太多基础差的同学被这道题劝退其实只要把双端队列版照着抄三遍再把手写双指针版背到滚瓜烂熟笔试现场就是一道送分题。代码这个东西嚼碎了真没那么难难的是你愿不愿意在没人催的时候把它一行一行咽下去。