Vue.js

Appearance

On this page

实战：反转字符串 ​

这道题是双指针算法的"Hello World"。

虽然看似简单，但它考察了两个核心概念：原地算法 (In-place Algorithm) 和 内存交换机制。

题目描述 ​

LeetCode 344. Reverse String

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

关键约束：必须原地修改输入数组、使用 O(1) 的额外空间。

示例：

输入：s = ["h", "e", "l", "l", "o"]
输出：["o", "l", "l", "e", "h"]

问题分析 ​

首先要问：为什么要原地修改？

在实际工程中，如果处理的是 1GB 的日志文件或网络数据包，创建一个新的反转副本需要额外的 1GB 内存，这可能是不可接受的。原地修改只需要几个字节的额外空间（用于指针和临时变量）。

策略： 使用对撞双指针。一个指头，一个指尾，交换它们，然后向中间靠拢。

解法：双指针交换 ​

javascript
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
function reverseString(s) {
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        // 交换两端元素
        const temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        
        // 移动指针
        left++;
        right--;
    }
}

复杂度分析：

  • 时间复杂度：O(N/2) ≈ O(N)。只需遍历一半数组。
  • 空间复杂度：O(1)。只使用了 left, right, temp 三个变量。

深度探讨：交换的艺术 ​

在 JavaScript 中，我们有几种交换变量的方式，面试中可以展开讨论：

1. 临时变量法（最通用、最快） ​

javascript
const temp = s[left];
s[left] = s[right];
s[right] = temp;

这是最稳妥的写法，性能最好，兼容性最强。

2. 解构赋值（最优雅） ​

javascript
[s[left], s[right]] = [s[right], s[left]];

优点：代码简洁。 缺点：在 V8 引擎中，解构赋值会创建临时数组对象，性能略低于临时变量法（但在本题规模下可忽略）。

3. 异或运算（炫技但危险） ​

javascript
// 仅适用于整数，不适用于字符！
// s[left] ^= s[right];
// s[right] ^= s[left];
// s[left] ^= s[right];

这是 C/C++ 时代的经典技巧，不需要额外空间。但在 JavaScript 中：

  1. 字符不是整数，无法直接异或。
  2. 即使转为 ASCII 码，JS 的位运算会将数字转为 32 位整数，可能导致精度问题（虽然 ASCII 码没事）。
  3. 不推荐在 JS 中使用。

举一反三 ​

这道题本身很简单，但它是解决更复杂问题的积木。

变体 1：反转字符串中的单词 (LeetCode 151) 思路：先反转整个字符串（用本题的方法），再逐个反转每个单词。

变体 2：旋转数组 (LeetCode 189) 思路：将数组向右移动 k 位。 解法：

  1. 反转整个数组。
  2. 反转前 k 个元素。
  3. 反转剩余元素。

结论：掌握了"局部反转"和"整体反转"的组合，就能处理各种旋转、移位问题。

常见错误 ​

1. 误用 return ​

题目要求 void（不返回），直接修改 s。如果你写 return s.reverse()，虽然结果对，但不符合"原地算法"的手写要求（面试官通常希望看你实现 reverse）。

2. 循环条件写成 left <= right ​

虽然写 <= 也是对的，但当 left === right 时（奇数长度的中间元素），自己和自己交换是多余的操作。写 < 更精准。

本章小结 ​

  • 核心思想：对撞双指针。
  • 工程价值：理解原地算法对内存的节省。
  • 扩展应用：作为子程序，服务于更复杂的字符串/数组旋转问题。

在 GitHub 上编辑此页