刷LeetCode100道-Day03

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给我详细分析了一下

关键区别

对比项 for 循环版本 while 循环版本
索引计算方式 每次循环需计算 s.length - i - 1,多次访问 s.length 预存右指针 r = s.length - 1,减少属性访问
循环条件判断 每次循环检查 i < Math.floor(s.length/2) 仅检查 l < r (简单变量比较)
引擎优化可能性 可能导致循环条件未缓存,反复计算 条件简单,易被 JIT 优化为寄存器操作

详细分析

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 循环
    仅使用预存的 lr 变量,交换后直接修改指针,指令更为精简

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

性能实测验证

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

数组长度 for 循环(ms) while 循环(ms)
10,000 0.12 0.08
1,000,000 2.5 1.8
10,000,000 25 18

结论

  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('')
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容