如何用Python实现的反转？

摘要 反转字符串中的单词是经典的字符串操作问题，常规解法（如" ".join(reversed(s.split()))）虽能通过测试，但额外空间复杂度为 O (N)，无法满足 “O (1) 额外空间复杂度下原地操作” 的进阶要求。 本文将拆解 “原地反转单词” 的核心思路 —— 先去除字符串中多余空格，再整体反转字符串，最后逐个反转单词内部字符，并通过快慢指针、双指针等核心技巧，详细分析实现过程中易踩坑的细节，最终给出符合进阶要求的完整原地解法。 关键词： 原地操作、快慢指针、双指针、字符串反转 题目描述 原题链接：151. 反转字符串中的单词 给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 示例 1： 输入：s = "the sky is blue" 输出："blue is sky the" 示例 2： 输入：s = " hello world " 输出："world hello" 解释：反转后的字符串中不能存在前导空格和尾随空格。 示例 3： 输入：s = "a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。 提示： 1 <= s.length <= 104 s 包含英文大小写字母、数字和空格 ' ' s 中 至少存在一个 单词 进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。 额外空间复杂度 这道题如果用s.split()把字符串转成字符串列表，然后用reverse()反转，看似很简单。但其实split()开辟了内存空间存储新字符串，有O(N)的额外空间复杂度。并不能满足进阶要求的“原地”操作。 正确思路总览 核心三步： 去掉多余空格 ：通过快慢指针的 “快指针读取 - 慢指针写入” 的方式，仅保留单词间单个空格，去除前导 / 尾随空格； 整体反转字符串 ：将整个字符列表反转（如hello world→dlrow olleh）； 逐个单词再反转 ：遍历字符列表，以空格为分隔，逐个反转单词内部字符（如dlrow→world，olleh→hello）。 上述思路如下图所示： 顺序反了，单词内部又恢复了。 这是一种经典技巧：整体反转 + 局部反转 = 顺序翻转 如何原地去除多余空格？ 我们使用快慢指针来去除多余空格，fast负责读取，slow负责写入。 我们先来手动模拟一下 假设字符串为s=" hello world "。这个字符串中前导空格、单词间空格和尾随空格各有 2 个。 我们知道，在很多语言中（如Python）字符串是无法被修改的。为了方便修改，我们需要把字符串转为字符列表（数组）。该字符列表的长度为16。 为了方便演示和理解，我将以表格的形式呈现去除多余空格的过程。 初始状态如下图所示，快慢指针都在索引0。 fast读取->索引0是空格->右移（到索引1）->索引1是空格->右移（到索引2）->索引2不是空格->把s[fast]赋值给s[slow] 后面以此类推，如下图所示，图中标黄处表示被覆盖上的、我们期望得到的字符。 此时，fast==6, slow==4, s_list==['h', 'e', 'l', 'l', 'o', 'l', 'o', ' ', ' ', 'w', 'o', 'r', 'l', 'd', ' ', ' '] 我们通过 覆盖 的方式“原地”去掉了前导空格。此时列表的长度没有变化。 想一想，到目前位置，是什么样的逻辑呢？是不是fast只要读到空格，就跳过（右移，即fast+=1），只要fast读到的不是空格就覆盖（赋值写入，即s[slow]=s[fast]），然后fast和slow各向右移一位。 接下来又出现空格了，如果还按照刚才的逻辑走，fast就会跳过中间两个空格，指向'w'（此时slow==5, fast==9）。如果现在覆盖的话，就是直接在hello后面接'w'，如下图所示，这并不是我们想要的。