第七天——字符串（反转字符串、替换数字、旋转单词字符串）

344.反转字符串

学习链接

https://programmercarl.com/0344.反转字符串.html

个人想法

库函数

reverse结局

双指针

像这种前后移动交换的肯定可以使用双指针达到一次遍历，直接交换位置。

解题代码

库函数


/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    s.reverse()
};

双指针


/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
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--
    }
};

541. 反转字符串II

学习链接

https://programmercarl.com/0541.反转字符串II.html#算法公开课

个人想法

💡

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

解题代码

执行一个循环，遍历整个字符串，step为2k


/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    let array = s.split('')
    for(let i = 0; i < array.length;i = i + 2 * k){
        let l = i
        // 注意这里，我们取的是值 - 1
        let r = (i + k  > array.length ? array.length : i + k) - 1 
        while(l <= r){
            [array[l], array[r]] = [array[r], array[l]]
            l ++ 
            r --
        }
    }
    return array.join('')
};

151.翻转字符串里的单词

学习链接

https://programmercarl.com/0151.翻转字符串里的单词.html#算法公开课

个人想法

split + reverse

双指针法

移除多余空格

将整个字符串反转

将每个单词反转

解题代码


/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(' ').filter(item=>item).map(item=>item.trim()).reverse().join(' ')
};

双指针法


/**
 * @param {string} s
 * @return {string}
 */
 var reverseWords = function(s) {
   // 字符串转数组
   const strArr = Array.from(s);
   // 移除多余空格
   removeExtraSpaces(strArr);
   // 翻转
   reverse(strArr, 0, strArr.length - 1);

   let start = 0;

   for(let i = 0; i <= strArr.length; i++) {
     if (strArr[i] === ' ' || i === strArr.length) {
       // 翻转单词
       reverse(strArr, start, i - 1);
       start = i + 1;
     }
   }

   return strArr.join('');
};

// 删除多余空格
function removeExtraSpaces(strArr) {
  let slowIndex = 0;
  let fastIndex = 0;

  while(fastIndex < strArr.length) {
    // 移除开始位置和重复的空格
    if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
      fastIndex++;
    } else {
      strArr[slowIndex++] = strArr[fastIndex++];
    }
  }

  // 移除末尾空格
  strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
}

// 翻转从 start 到 end 的字符
function reverse(strArr, start, end) {
  let left = start;
  let right = end;

  while(left < right) {
    // 交换
    [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
    left++;
    right--;
  }
}