代码随想录训练营Day8|字符串

344. 反转字符串

解题思路

• 题目要求原地修改输入数组，不要分配额外的空间
• 使用头尾双指针，变量交换，将字符 一 一反转

var reverseString = function(s) {
    let left = 0;
    let right = s.length - 1;
    let temp;
    while (left < right) {
        temp = s[left]
        s[left] = s[right]
        s[right] = temp
        left++
        right--
    }
    return s;
};

541. 反转字符串 II

解题思路

• 重点是要理解题目，依次计数至 2k个字符后，即每次遍历后索引增加 2 * k ，判断剩余字符是否满足以下条件：
• 如果剩余字符少于 k 个，则将剩余字符全部反转，即 i + k > s.length，反转区间[i, s.length - 1]。
• 如果剩余字符小于 2k 但大于或等于 k 个，即 i + k < a.length，则反转前 k 个字符，反转区间 [i, i + k - 1]，其余字符保持原样。

var reverseStr = function(s, k) {
    s = s.split("")
    for (let i = 0; i < s.length; i += 2 * k) {
        let l = i - 1, r = i + k > s.length ? s.length : i + k;
        while(++l < --r) [s[l], s[r]] = [s[r], s[l]];
    }
    return s.join("")
};

剑指Offer 05.替换空格

题目描述

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1： 输入：s = "We are happy."
输出："We%20are%20happy."

解题思路

• 统计原字符空格出现的次数，声明新数组长度为空格完全替换为 %20 的长度
• 双指针法：左指针 = 原数组长度，右指针 = 新数组长度
• 新数组由后往前依次填充替换
• 如果从左往右填充，那么每次添加元素都要将添加元素之后的所有元素向后移动

var replaceSpace = function(s) {
   // 字符串转为数组
  const strArr = Array.from(s);
  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 >= 0) {
    if (strArr[left] === ' ') {
      strArr[right--] = '0';
      strArr[right--] = '2';
      strArr[right--] = '%';
      left--;
    } else {
      strArr[right--] = strArr[left--];
    }
  }
  // 数组转字符串
  return strArr.join('');
};

151. 反转字符串中的单词

解题思路

• 删除字符串中包括头部、尾部、及中间出现的空格
• 依次反转各个单词
• 补全单词中间的空格

var reverseWords = function(s) {
    let arr = s.split(" ");
    let i = 0;
    while (i < arr.length) {
        if (arr[i] === "") {
            arr.splice(i, 1)
            continue
        }
        i++
    }
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]]
        left++
        right--
    }
    return arr.join(" ")
};

LCR 182. 动态口令

本题同<剑指Offer58-II.左旋转字符串>相同

解题思路

• 局部反转 + 全局反转，如下：
• 反转区间为前n的子串
• 反转区间为n到末尾的子串
• 反转整个字符串

var reverse = function (left, right, arr) {
    while(left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]]
        left++
        right--
    }
}
var dynamicPassword = function(password, target) {
    let strArr = password.split("")
    reverse(0, target-1, strArr);
    reverse(target, strArr.length-1, strArr);
    reverse(0, strArr.length-1,strArr);
    return strArr.join("")
};