反转字符串
对于非核心逻辑，可以使用库函数，否则，不使用。
库函数（不推荐）
双指针法
时间复杂度：O(n)
var reverseString = function(s) {
let i=0;
let j=s.length-1
while(i<j){
[s[i],s[j]]=[s[j],s[i]]
i++
j--
}
};
反转字符串2
题目：https://leetcode.cn/problems/reverse-string-ii/submissions/
考点：复杂规则下的反转字符串，不涉及具体的算法。在for循环的表达式上做文章
function reverseStr(s, k) {
for(let i=0;i<s.length;i+=2*k){
if(i+k<=s.length){
s=reverse(s,i,i+k)
}else{
s=reverse(s,i,s.length)
}
}
return s
}
//翻转逻辑
function reverse(str, start, end) {
let s=str.split('')
for (let i = start, j = end-1; i < j; i++, j--) {
[s[i],s[j]]=[s[j],s[i]]
}
return s.join('')
}
替换空格
题目：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
思路一：库函数
function replaceSpace(str) {
s = s.replace(/\s/g,'%20')
return s
}
思路二：双指针法
时间复杂度：O(n)
空间复杂度：O(1)
function replaceSpace(str) {
let s = str.split("");
let count = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === " ") {
count++;
}
}
let newSize = s.length + 2 * count;
let oldSize = s.length;
let time = 2 * count;
let k;
while (k < time) {
s[s.length + k] = "0";
k++;
}
let i = oldSize - 1;
let j = newSize - 1;
while (i < j) {
if (s[i] !== " ") {
s[j] = s[i];
i--;
j--;
} else {
s[j] = "0";
s[j - 1] = "2";
s[j - 2] = "%";
j = j - 3;
i--;
}
}
return s.join("");
}
反转字符串中的单词
题目：https://leetcode.cn/problems/reverse-words-in-a-string/
思路一：对原字符串进行整体的翻转，再对每个单词做反转。
注意：因为js中的string是不可变的，因此空间复杂度降不到O(1)，不能采用以上思路。
时间复杂度：O(n)
空间复杂度：O(1)
思路二：库函数
时间复杂度：O(n)
空间复杂度：O(n)
var reverseWords = function(s) {
// 去掉空格
let strArr = s.replace(/\s+/g,' ').split(' ')
// 去掉两边空格
if(strArr[0] === ''){
strArr.splice(0,1)
}
if(strArr[strArr.length-1] === ''){
strArr.splice(strArr.length-1,1)
}
return strArr.reverse().join(' ')
};
左旋转字符串
题目：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
思路一：局部反转+整体反转；
具体步骤为：
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
空间复杂度：O(1)
思路二：库函数
空间复杂度：O(n)
var reverseLeftWords = function(s, n) {
let str=s.substr(0,n)
return s.substring(n)+str
};
总结
