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('')
};