344.反转字符串

题目

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

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

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

示例 2：

    输入：s = ["H","a","n","n","a","h"]
    输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

想法

js里面有提供现成的reverse()方法肯定不能用，循环然后往空数组里push也不能用，题目要求的是原地且O(1)，所以我在想是不是可以第一位和最后一位这样交换

第一种实现

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    for(let i = 0; i < Math.floor(s.length/2); i ++){
        let c = s[i]
        s[i] = s[s.length - i - 1]
        s[s.length - i - 1] = c
    }
};

借助 c = a; a = b; b = c;的思想

第二种实现

利用前后指针，同样利用上述思想，但是不需要for循环，而是前后两个指针同时移动

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let l = 0, r = s.length - 1;
    while(l < r){
        let c = s[l];
        s[l] = s[r];
        s[r] = c;
        l ++;
        r --;
    }
};

注

两种写法复杂度都是O(n)但是 while 运行效果明显快很多，找deepseek给我详细分析了一下

关键区别

详细分析

1. 索引计算的性能差异

• for 循环：
  每次交换需动态计算 s.length - i - 1：

  s[i] = s[s.length - i - 1];  // 需访问 s.length
  

若数组长度 `s.length` 未被缓存为变量，每次访问属性可能触发 JavaScript 引擎的属性查找。

• while 循环：
  右指针 r 预存 s.length - 1，后续直接使用变量：

  s[l] = s[r];  // 仅变量操作，无需计算
  

减少了对 `s.length` 的访问次数，**避免潜在的性能损失**。

2. 循环条件的优化空间

• for 循环：
  条件 i < Math.floor(s.length/2) 需每次迭代时重新计算（虽理论上可优化为常量 mid，但依赖引擎实现）。
  实际可能因未缓存 Math.floor(s.length/2)，导致重复计算。

• while 循环：
  条件为 l < r（简单的变量比较），极容易触发 JIT 优化（如寄存器存储变量），且无计算开销。

3. 交换操作的指令数

• for 循环：
  每次交换需执行两次数组索引计算（正序索引 i、逆序索引 s.length - i - 1）。

  [s[i], s[s.length - i - 1]] = [s[s.length - i - 1], s[i]];  // 隐式计算两次逆序索引
  

• while 循环：
  仅使用预存的 l 和 r 变量，交换后直接修改指针，指令更为精简：

  [s[l], s[r]] = [s[r], s[l]];  // 无额外计算l++; r--;
  

性能实测验证

以下为两种实现针对不同规模数组的近似执行时间对比（不同环境下略有差异）：

结论

1. 时间复杂度相同：均需执行 n/2 次交换，复杂度为 O(n)。
2. 实际效率差异：
   • while 循环因避免了重复索引计算与属性访问，更适合大规模数据。
   • for 循环的实现细节可能导致引擎优化不足，微观效率略低。

推荐使用 while 循环实现，兼具代码清晰度和潜在性能优势。

125.验证回文串

题目

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true；否则，返回false。

示例 1：

    输入: s = "A man, a plan, a canal: Panama"
    输出：true
    解释："amanaplanacanalpanama" 是回文串。

示例 2：

    输入：s = "race a car"
    输出：false
    解释："raceacar" 不是回文串。

示例 3：

    输入：s = " "
    输出：true
    解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。

由于空字符串正着反着读都一样，所以是回文串。

提示：

• 1 <= s.length <= 2 * 105
• s 仅由可打印的 ASCII 字符组成

想法

这道题主要就两步

1. 把字符串过滤成无空格无标点符号的纯字母
2. 用上面一道题的方法即可

s.replace(/[^a-zA-Z0-9]|\s/gi, '')

1. 分解正则表达式

(1) [^a-zA-Z0-9]

• [...] 表示字符组，匹配其中任意一个字符。
• ^ 在字符组内表示否定匹配，即匹配不在字符组内的内容。
• a-zA-Z0-9 覆盖所有字母（大小写）和数字。
• 整体含义：匹配非字母、非数字的字符（如 @, #, $ 等符号）。

(2) |

• 逻辑“或”，表示匹配满足左侧表达式（[^a-zA-Z0-9]）或右侧表达式（\s）的内容。

(3) \s

• 匹配空白字符，包括：
  • 空格（）
  • 制表符（\t）
  • 换行符（\n）
  • 回车符（\r）

(4) 修饰符 gi

• g（全局匹配）：查找所有匹配项（默认仅匹配第一个）。
• i（忽略大小写）：在此正则中无实际作用，因为 a-zA-Z 已覆盖大小写。

第二步这边偷个懒，如果不用现成的数组方法，可以用上面那道题目的思想

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    s = s.replace(/[^a-zA-Z0-9]|\s/gi, '').toLowerCase()
    return s == s.split('').reverse().join('')
};