344. 反转字符串
解题思路
- 题目要求原地修改输入数组，不要分配额外的空间
- 使用头尾双指针，变量交换，将字符 一 一反转
var reverseString = function(s) {
let left = 0;
let right = s.length - 1;
let temp;
while (left < right) {
temp = s[left]
s[left] = s[right]
s[right] = temp
left++
right--
}
return s;
};
541. 反转字符串 II
解题思路
- 重点是要理解题目，依次计数至
2k个字符后，即每次遍历后索引增加2 * k，判断剩余字符是否满足以下条件： - 如果剩余字符少于 k 个，则将剩余字符全部反转，即
i + k > s.length，反转区间[i, s.length - 1]。 - 如果剩余字符小于 2k 但大于或等于 k 个，即
i + k < a.length，则反转前 k 个字符，反转区间[i, i + k - 1]，其余字符保持原样。
var reverseStr = function(s, k) {
s = s.split("")
for (let i = 0; i < s.length; i += 2 * k) {
let l = i - 1, r = i + k > s.length ? s.length : i + k;
while(++l < --r) [s[l], s[r]] = [s[r], s[l]];
}
return s.join("")
};
剑指Offer 05.替换空格
题目描述
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1： 输入：s = "We are happy."
输出："We%20are%20happy."
解题思路
- 统计原字符空格出现的次数，声明新数组长度为空格完全替换为
%20的长度 - 双指针法：左指针 = 原数组长度，右指针 = 新数组长度
- 新数组由后往前依次填充替换
- 如果从左往右填充，那么每次添加元素都要将添加元素之后的所有元素向后移动
var replaceSpace = function(s) {
// 字符串转为数组
const strArr = Array.from(s);
let count = 0;
// 计算空格数量
for(let i = 0; i < strArr.length; i++) {
if (strArr[i] === ' ') {
count++;
}
}
let left = strArr.length - 1;
let right = strArr.length + count * 2 - 1;
while(left >= 0) {
if (strArr[left] === ' ') {
strArr[right--] = '0';
strArr[right--] = '2';
strArr[right--] = '%';
left--;
} else {
strArr[right--] = strArr[left--];
}
}
// 数组转字符串
return strArr.join('');
};
151. 反转字符串中的单词
解题思路
- 删除字符串中包括头部、尾部、及中间出现的空格
- 依次反转各个单词
- 补全单词中间的空格
var reverseWords = function(s) {
let arr = s.split(" ");
let i = 0;
while (i < arr.length) {
if (arr[i] === "") {
arr.splice(i, 1)
continue
}
i++
}
let left = 0;
let right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]]
left++
right--
}
return arr.join(" ")
};
LCR 182. 动态口令
本题同<剑指Offer58-II.左旋转字符串>相同
解题思路
- 局部反转 + 全局反转，如下：
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
var reverse = function (left, right, arr) {
while(left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]]
left++
right--
}
}
var dynamicPassword = function(password, target) {
let strArr = password.split("")
reverse(0, target-1, strArr);
reverse(target, strArr.length-1, strArr);
reverse(0, strArr.length-1,strArr);
return strArr.join("")
};
