Day 08 | 344.反转字符串、541.反转字符串II、剑指Offer 05.替换空格、151.翻转字符串里的单词、剑指Offer58-II.左旋转字符串

Leetcode 344.反转字符串

题目：344.反转字符串

初始思路

简单解法就是直接调用字符串的reverse方法。
但是如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。
这题使用双指针即可，从头和尾开始往中间夹

代码

var reverseString = function (s) {
    var temp
    var n = s.length
    for (let i = 0; i < Math.ceil(n / 2); i++) {
        temp = s[i]
        s[i] = s[n - 1 - i]
        s[n - 1 - i] = temp
    }
};
// 二刷
var reverseString = function (s) {
    let left = 0, right = s.length - 1
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]]
        left++
        right--
    }
}

感想

1. 常规题，控制住自己不要使用reverse函数

Leetcode 541.反转字符串II

题目：541.反转字符串II

初始思路

直接按照题目的思路写就行，没有什么出彩的思路。

代码

var reverse = function (arr, left, right) {
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]]
        left++
        right--
    }
}
var reverseStr = function (s, k) {
    const n = s.length
    let arr = s.split('');
    console.log(arr);
    for (let i = 0; i < n; i += 2 * k) {
        // 判断i+k会不会小于数组长度，取两者更小值
        reverse(arr, i, Math.min(i + k, n) - 1)
    }
    return arr.join('')
};

感想

1. reverse函数名被我写错了，直接写成递归了。直接爆栈，纯纯无语。
2. 上一题的反转字符串在这里就能用到了。
3. 主要就是在反转的时候传参，如果i+k超过了数组的长度，也就是说剩余部分不足k的话，全部反转。

剑指Offer 05.替换空格

题目：剑指Offer 05.替换空格 讲解：代码随想录

初始思路

replace函数只能替换第一次出现的字符，如果需要全部替换需要使用正则表达式。
看了一下代码随想录，原来和数组扩容有关。

代码

// 正则表达式
var replaceSpace = function (s) {
    let reg = new RegExp(' ', 'g')
    return s.replace(reg, '%20')
};

// 数组扩容
var replaceSpace = function (s) {
    // 从s转换一个数组
    const strArr = Array.from(s)
    let count = 0
    // 计算空格数量
    for (let i = 0; i < strArr.length; i++) {
        if (strArr[i] === ' ') count++
    }
    // left指向原字符串的最后一个字符
    let left = strArr.length - 1
    // 需要把空格换成%20，比起之前每个空格还需要两个位置
    // right指向扩容后的数组最后一位
    let right = strArr.length + count * 2 - 1
    // 从后向前替换空格，也就是双指针法
    while (left >= 0) {
        if (strArr[left] === ' ') {
            // 倒着填充
            strArr[right--] = '0'
            strArr[right--] = '2'
            strArr[right--] = '%'
            // left指针继续向前寻找空格
            left--
        } else {
            // 如果没遇到空格,把这个元素复制到扩容的部分
            strArr[right--] = strArr[left--]
        }
    }
    return strArr.join('')
}

感想

1. 第一反应就是正则表达式，很简便。
2. 没想到这题的考点是数组扩容，还是有点复杂的，尤其是从后面开始填充很精妙，如果从前面开始替换的话，数组元素需要不停的移动。

Leetcode 151.翻转字符串里的单词

题目：151.翻转字符串里的单词 讲解：代码随想录

初始思路

第一反应是去除多余空格，然后用split分隔，最后倒序相加即可。
看了一下代码随想录，说这个想法会让题目变成水题，要用正经解法。

代码

// 正则表达式
var reverseWords = function (s) {
    return s.trim().split(/\s+/).reverse().join(' ');
};

// 正攻
// 删除多余的空格
var removeExtraSpaces = function (strArr) {
    let slow = 0;
    let fast = 0;
    while (fast < strArr.length) {
        // 移除开始位置和重复的空格
        if (strArr[fast] === ' ' && (fast === 0 || strArr[fast - 1] === ' ')) {
            fast++;
        } else {
            strArr[slow++] = strArr[fast++];
        }
    }
    // 移除末尾空格
    strArr.length = strArr[slow - 1] === ' ' ? slow - 1 : slow;
}
// 翻转字符
var reverse = function (strArr, start, end) {
    let left = start
    let right = end
    while (left < right) {
        [strArr[left], strArr[right]] = [strArr[right], strArr[left]]
        left++
        right--
    }
}
var reverseWords = function (s) {
    // 字符串转数组
    const strArr = Array.from(s)
    // 去除空格
    removeExtraSpaces(strArr)
    // 从头到尾翻转
    reverse(strArr, 0, strArr.length - 1)
    let index = 0
    for (let i = 0; i <= strArr.length; i++) {
        if (strArr[i] === ' ' || i === strArr.length) {
            // 翻转每个单词
            reverse(strArr, index, i - 1)
            index = i + 1
        }
    }
    return strArr.join('')
}

感想

1. 正则表达式依旧很简便。
2. 删除空格的操作有些复杂。
3. 在确定字符的时候要注意for循环 i<=strArr.length。当找到一个空格的时候，开始翻转前面的字符，开始位置用index标记，结束位置是i-1。

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

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

初始思路

使用字符串截取和替换可以很简单的做到。
思路二：可以先整体翻转，然后在中断的地方左右两边分别翻转。

代码

// 使用库函数
var reverseLeftWords = function (s, n) {
    let sub = s.slice(0, n)
    let str = s.replace(sub, '') + sub
    return str
};

// 正攻
// 翻转字符
var reverse = function (strArr, start, end) {
    let left = start
    let right = end
    while (left < right) {
        [strArr[left], strArr[right]] = [strArr[right], strArr[left]]
        left++
        right--
    }
}
var reverseLeftWords = function (s, n) {
    const len = s.length
    const strArr = Array.from(s)
    // 整个翻转
    reverse(strArr, 0, len - 1)
    // 左部分翻转
    reverse(strArr, 0, len - n - 1)
    // 右部分翻转
    reverse(strArr, len - n, len - 1)
    return strArr.join('')
}

感想

1. 和上一题151.翻转字符串里的单词有相似的思路。
2. 这个翻转指定位置的函数要熟练掌握。
3. 万物归于双指针！