反转字符串

对于非核心逻辑，可以使用库函数，否则，不使用。

1. 库函数（不推荐）

2. 双指针法
   时间复杂度：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/
思路一：局部反转+整体反转；
具体步骤为：

1. 反转区间为前n的子串
2. 反转区间为n到末尾的子串
3. 反转整个字符串
   空间复杂度：O(1)
   思路二：库函数
   空间复杂度：O(n)

var reverseLeftWords = function(s, n) {
    let str=s.substr(0,n)
    return s.substring(n)+str
};

总结