翻转字符串中的单词、右旋转字符串

翻转字符串中的单词

https://leetcode.cn/problems/reverse-words-in-a-string/description/

思路

1、首先需要去除多余的空格
'the sky is blue'

// 使用快慢指针，slowIndex,fastIndex
1.1 先去除字符串首和重复出现的空格
if (strArr[fastIndex] === ' ' && (fastIndex===0 || strArr[fastIndex-1] === ' '))

1.2 去除字符串尾的空格
// 长度 = 最后一位索引 + 1；整个循环结束后慢指针的指向是什么。
// 判断慢指针-1指向的字符是不是空格，是说明原字符串尾部有空格，strArr长度应该是满指针当前位置-1。
// 否说明原字符串尾部没有空格，strArr长度就是满指针所指的位置。
strArr.length = strArr[slowIndex-1] === ' '? slowIndex-1 : slowIndex

2、将整个字符串进行翻转
eg：'the sky is blue' --> 'eulb si yks eht'

使用双指针
while(left<right){
  [strArr[left],strArr[right]] = [strArr[right],strArr[left]]
  left++
  right++
}

3、然后找到每一个单词，对该单词进行翻转
eg：'eulb si yks eht' --> 'blue is the sky'

// 分两步处理
// 假设字符串中有n个单词，先处理前n个单词，再处理最后一个单词

求解

var reverseWords = function (s) {
  let strArr = Array.from(s)
  // 去除多余空格的函数
  const removeBlank = (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]
        slowIndex++
        fastIndex++
      }
    }
    strArr.length =
      strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex
  }
  //翻转字符串的函数，参数1是字符串，参数2是待处理字符串的起点索引，参数3是待处理字符串的终点索引
  const reverse_all = (arr, start, end) => {
    let left = start
    let right = end
    while (left < right) {
      ;[arr[left], arr[right]] = [arr[right], arr[left]]
      left++
      right--
    }
  }
  removeBlank(strArr)
  reverse_all(strArr, 0, strArr.length - 1)
  let startIndex = 0
  for (let i = 0; i < strArr.length; i++) {
    if (strArr[i + 1] == ' ') {
      reverse_all(strArr, startIndex, i)
      startIndex = i + 2
    }
  }
  reverse_all(strArr, startIndex, strArr.length - 1)
  return strArr.join('')
}

右旋转字符串

https://kamacoder.com/problempage.php?pid=1065

思路

同上一道题思路相似，先全部反转，然后再把两部分各进行一次反转。

代码

var right_circle_string = (s,k)=>{
  let strArr = Array.from(s)
  //反转函数
  function reverse_word(sArr,start,end){
    let left = start,right = end
    while(left<right){
      [sArr[left], sArr[right]] = [sArr[right], sArr[left]]
      left++
      right--
    }
    return sArr
  }
  strArr = reverse_word(strArr,0,strArr.length-1)
  strArr = reverse_word(strArr,0,k-1)
  strArr = reverse_word(strArr,k,strArr.length-1)
  return strArr
}