字符串
理论知识
反转字符串
https://www.programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
https://leetcode.cn/problems/reverse-string/description/
思路
代码
var reverseString = function(s) {
let i = 0
let n = s.length - 1
while(i < n){
let temp = s[i]
s[i] = s[n]
s[n] = temp
i++
n--
}
return s
};
反转字符串
https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
https://leetcode.cn/problems/reverse-string-ii/description/
思路
这道题目其实也是模拟，实现题目中规定的反转规则就可以了。
可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。
其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。
代码
var reverseStr = function(s, k) {
let arr = s.split("")
for(let i = 0; i< arr.length; i+=(2*k)){
let a = i
let b = Math.min(i + k - 1, s.length - 1)
while(a < b){
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
a++
b--
}
}
return arr.join("")
};
注意我们b的取值
替换数字
翻转字符串里的单词
https://leetcode.cn/problems/reverse-words-in-a-string/description/
思路
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
普通解法
var reverseWords = function(s) {
let arr = []
let arr1 = s.split(" ")
for(let i = 0;i<arr1.length;i++){
if( arr1[i] !== "" ){
arr.unshift(arr1[i])
}
}
return arr.join(" ")
};
进阶解法
进阶：请尝试使用 O(1) 额外空间复杂度的 原地 解法。
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
const arr = Array.from(s)
// 移除多余的空格：开始、结尾、中间多余的
let fastIndex = 0
let slowIndex = 0
while(fastIndex < arr.length){
// 开始
if(fastIndex === 0 && arr[fastIndex] === " "){
fastIndex++
continue
}
// 中间多余
if(arr[fastIndex] === " " && arr[fastIndex - 1] === " "){
fastIndex++
continue
}
arr[slowIndex++] = arr[fastIndex++]
}
// 结尾
arr.length = arr[slowIndex - 1] === " " ? slowIndex - 1 : slowIndex
// 全部翻转
reverseArr(arr, 0, arr.length - 1)
// 翻转单词
let start = 0
for(let i = 0; i <= arr.length; i++) {
if (arr[i] === ' ' || i === arr.length) {
reverseArr(arr, start, i - 1);
start = i + 1;
}
}
return arr.join('');
};
function reverseArr(arr, i, j){
let start = i
let end = j
while(start < end){
[ arr[start], arr[end] ] = [arr[end], arr[start]]
start++
end--
}
}
arr.length = arr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex，结果arr[slowIndex++] = arr[fastIndex++]末尾还会有空格吗- 假设输入：
" hello world " - 字符串转成字符数组：
[' ', ' ', 'h', 'e', 'l', 'l', 'o', ' ', ' ', ' ', 'w', 'o', 'r', 'l', 'd', ' ', ' '] - 快慢指针清除多余空格的过程，核心逻辑是：
if (fastIndex === 0 && arr[fastIndex] === ' ') fastIndex++;
if (arr[fastIndex] === ' ' && arr[fastIndex - 1] === ' ') fastIndex++;
arr[slowIndex++] = arr[fastIndex++];
我们用 fastIndex 走一遍，把符合条件的字符复制到 slowIndex 位置。
- 第一次遇到连续空格：两个开头空格被跳过
- 然后
"hello"被正常复制：
slowIndex = 0: 'h'
slowIndex = 1: 'e'
slowIndex = 2: 'l'
slowIndex = 3: 'l'
slowIndex = 4: 'o'
遇到多个空格，保留一个
' '：slowIndex = 5: ' '"world"继续复制：
slowIndex = 6: 'w'
slowIndex = 7: 'o'
slowIndex = 8: 'r'
slowIndex = 9: 'l'
slowIndex = 10: 'd'
- 最后两个
' '没有被跳过，因为这句判断：if (arr[fastIndex] === ' ' && arr[fastIndex - 1] === ' ') - 只会跳过连续空格中的“第二个开始”，但最后这两个空格前一个是
'd'，不满足这个条件，所以最后还是会被复制一个。slowIndex = 11: ' ' 就是这个多余的空格 - 最后的结果：
['h','e','l','l','o',' ','w','o','r','l','d',' '] slowIndex = 12，arr[11] === ' '，最后是一个多余的空格
for (let i = 0; i <= arr.length; i++) { 为什么使用的是 <=在这个 for 循环里，逻辑是：if (arr[i] === ' ' || i === arr.length)
意思是：当遇到空格，或者已经到了字符串末尾时，就把当前这个“单词段”翻转。
如果使用<，那么最后一个单词将不会被翻转
arr.join('')而不是arr.join(' ')因为：
我们在 处理每个单词之间的空格时，已经手动控制好了空格的位置（也就是只有一个空格，并且不会出现在开头或结尾）。
arr 本身已经是：[word1, ' ', word2, ' ', word3] 这样的格式。
所以我们只需要把字符原样拼接（不再人为添加空格），用 join('') 即可。
右旋字符串
https://programmercarl.com/kamacoder/0055.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html
https://kamacoder.com/problempage.php?pid=1065
思路
为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作
使用整体反转+局部反转就可以实现反转单词顺序的目的。
代码
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
function main() {
const a = []
rl.on('line', (line) => {
a.push(line.trim())
})
rl.on('close', () => {
const n = Number(a[0])
const arr = Array.from(a[1])
if (n >= arr.lengthg) {
console.log(a[1])
return
}
reverseArr(arr, 0, arr.length)
for (let i = 0; i < arr.length; i++){
if (i + 1 === n) {
reverseArr(arr, 0, n)
reverseArr(arr, n + 1, arr.length)
}
}
console.log(arr.join(""))
})
}
function reverseArr(arr, i , j) {
let start = i
let end = j
while (start < end) {
[arr[start], arr[end]] = [arr[end], arr[start]]
start++
end--
}
}
main()