代码随想录Day8-Leetcode344.反转字符串 II，541. 反转字符串II ，剑指Offer 05.替换空格 ，151.翻转字符串里的单词，剑指Offer58-II.左旋转字符串

344. 反转字符串

题目链接:https://leetcode.cn/problems/reverse-string
明显的双指针

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

541. 反转字符串 II

题目链接:https://leetcode.cn/problems/reverse-string-ii/
这道题思路我之前写哈夫曼压缩是写过的, 结果搞不清区间怎么算了,从i开始?从len-2k开始?小于?小于等于?
很多东西如果不太明晰,可以参照用例简单推导,举个例子的

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    let arr = s.split('')
    let i =0 
    for(i = 0; i< s.length-2*k; i+=2*k){
        reverse(arr,i,i+k-1)
    }
    if(s.length-i>=k){
        reverse(arr,i,i+k-1)
    }else{
        reverse(arr,i,s.length-1)
    }
    return arr.join('')
};

function reverse(s,left,right){
    for(let l = left, r=right; l<r;l++,r--){
        let tmp = s[l]
        s[l] = s[r]
        s[r] = tmp
    }
}
//问题在于区间是怎样的 是从s.length-2*k开始算的吗?(显然不是)是从i开始算的

看了题解以后, 发现完全有更优雅的解法, 每次+2k, 结尾用三元表达式判断就可以了

剑指Offer 05.替换空格

题目链接:https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
简易解

  /**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    s = s.replaceAll(/\s/g, "%20")
    return s
};

看了题解,发现从后向前填充确实好用,只用移动一遍

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    let strArr = s.split('')
    let bNum = 0
    strArr.forEach(e=>{if(e==' '){bNum++}})
    let i = strArr.length-1
    let j = i+bNum*2
    for(;i>=0;i--){
        if(strArr[i]==' '){
            strArr[j-2] = '%'
            strArr[j-1] = '2'
            strArr[j] = '0'
            j -= 3
        }else{
            strArr[j] = strArr[i]
            j--
        }
    }
    return strArr.join('')
};

151. 反转字符串中的单词

题目链接:https://leetcode.cn/problems/reverse-words-in-a-string/
简易解

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  //用正则效率更高
    return s.split(' ').reverse().filter(e=>e.length!=0).join(' ')
};

正式解, 虽然也是看了题解才有思路;
而且第一遍写的时候没用去除多余空格, 用的splice,速度可想而知
另外最后还是用了splice和trim, 细看题解后发现其实这个也可以不用

/**
 * @param {string} s
 * @return {string}
 */
//反转整个字符串,然后逐个单词反转
var reverseWords = function(s) {
    let strArr = s.trim().split('')
    reverse(strArr,0,strArr.length-1)
    removeExtraBlanks(strArr)
    let l =0, r=0
    while(true){
        while(strArr[r]!=' '&&r<strArr.length){
            r++
        }
        if(r==strArr.length){
            reverse(strArr,l,r)
            break
        }else{
            reverse(strArr,l,r-1)
            r++
            // while(strArr[r] == ' '){
            //     strArr.splice(r,1)
            // }
            l = r
        }
        
    }
    return strArr.join('')
};
//移除多余空格
function removeExtraBlanks(sArr){   
    let l = 0,r = 0
    while(r<sArr.length){
        while(r!=0&&sArr[r]==' '&&sArr[r-1]==' '){
            r++
        }
        sArr[l] = sArr[r]
        l++
        r++
    }
    sArr.splice(l)
}

//反转部分数组元素
function reverse(sArr,left,right){
    for(let l = left,r=right; l<r;l++,r--){
        let tmp = sArr[l]
        sArr[l] = sArr[r]
        sArr[r] = tmp
    }
}

剑指Offer58-II.左旋转字符串

题目链接:https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/solutions/
简易解

/**
 * @param {string} s
 * @param {number} n
 * @return {string}
 */
var reverseLeftWords = function(s, n) {
    let arr = s.split("")
    arr = arr.concat(arr.splice(0,n))
    return arr.join("")
};

正式解

/**
 * @param {string} s
 * @param {number} n
 * @return {string}
 */
 //需要一个O(k)的tmp空间
var reverseLeftWords = function(s, n) {
    let strArr = s.split("")
    let l =0, r = n;
    let tmp = strArr.slice(0,n)

    while(r<strArr.length){
        strArr[l] =strArr[r]
        l++
        r++
    }
    for(let i = 0; i< n;i++){
        strArr[l] = tmp[i] 
        l++
    }
    return strArr.join('')
};