代码随想录-字符串

344.反转字符串

双指针完事

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    // 双指针交换字符
    let a = -1,b = s.length
    while(++ a < --b){
        [s[a], s[b]] = [s[b], s[a]]
    }
    return s
};

541.反转字符串Ⅱ

与1的区别在于，先分割，再反转

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    const len = s.length;
    // split() 方法用于把一个字符串分割成字符串数组。
    let resArr = s.split(""); 
    // 每隔 2k 个字符的
    for(let i = 0; i < len; i += 2 * k) {  
        // 前 k 个字符进行反转
        let a = i - 1, b = i + k > len ? len : i + k;
        // 形同反转字符串Ⅰ
        while(++a < --b) {
            [resArr[a], resArr[b]] = [resArr[b], resArr[a]];
        }
    }
    // join('')将数组元素无缝拼接
    return resArr.join("");
};

剑指Offer 05.替换空格

数组填充，先找到填充后的大小，再从后往前填充（节省时间复杂度）

/**
 * @param {string} s
 * @return {string}
 */
/**
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
    为什么要从后向前填充，从前向后填充不行么？
    从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
这么做有两个好处：
    不用申请新数组。
    从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
 */
var replaceSpace = function(s) {
   // 字符串转为数组
  const strArr = s.split("");
  let count = 0;
  // 计算空格数量
  for(let i = 0; i < strArr.length; i++) {
    if (strArr[i] === ' ') {
      count++;
    }
  }
    // 双指针一个指向原长度的尾巴，一个指向填充后长度的尾巴
  let left = strArr.length - 1;
  let right = strArr.length + count * 2 - 1;
    //遍历原字符串
    while(left > -1){
        if(strArr[left] === ' '){
            strArr[right --] = '0'
            strArr[right --] = '2'
            strArr[right --] = '%'
            left --
        }else{
            strArr[right --] = strArr[left --]
        }
    } 

  // 数组转字符串
  return strArr.join('');
};

151.翻转字符串里的单词

先按空格分割，然后双指针去除多余空格，然后直接reverse即可

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    let sArr = s.split(' ')
    // 删除多余空格：双指针
    let slow = 0,fast = 0
    while(fast < sArr.length){
        if(sArr[fast] === ''){
            fast ++
        }else{
            sArr[slow ++] = sArr[fast ++]
        }
    }
    sArr = sArr.slice(0,slow)

    sArr.reverse()
    return sArr.join(' ')
};

剑指Offer 58左旋字符串

左旋字符串，这不得瘦死

/**
 * @param {string} s
 * @param {number} n
 * @return {string}
 */
var reverseLeftWords = function(s, n) {
     if(n == 0){
         return s
     }
    // 方法一：先分割，再拼接
    // return s.slice(n) + s.slice(0, n)

    // 方法二：具体步骤为：反转区间为前n的子串 --> 反转区间为n到末尾的子串 --> 反转整个字符串
    // 当然，顺序反过来也可以
 /** Utils */
    //  反转字符串，双指针即可
    function reverseWords(strArr, start, end) {
        let temp;
        while (start < end) {
            temp = strArr[start];
            strArr[start] = strArr[end];
            strArr[end] = temp;
            start++;
            end--;
        }
    }
    /** Main code */
    // 分割
    let strArr = s.split('');
    let length = strArr.length;
    // 反转全部
    reverseWords(strArr, 0, length - 1);
    // 反转前n个
    reverseWords(strArr, 0, length - n - 1);
    // 反转后n个
    reverseWords(strArr, length - n, length - 1);
    return strArr.join('');
};