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 循环:
仅使用预存的l
和r
变量,交换后直接修改指针,指令更为精简:[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 |
结论
-
时间复杂度相同:均需执行
n/2
次交换,复杂度为O(n)
。 -
实际效率差异:
- 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 字符组成
想法
这道题主要就两步
- 把字符串过滤成无空格无标点符号的纯字母
- 用上面一道题的方法即可
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('')
};