之前寫過關(guān)于逆序問題的JAVA版總結(jié)堕油。因?yàn)楝F(xiàn)在開始搞前端了潘飘，所以用JS又做了一遍這些題目。改變語(yǔ)言之后雖然很多思路都差不多但是一些常用的函數(shù)還是需要整理一下的掉缺。
常見的解法思路：
- 雙指針方式卜录。利用var arr = s.split('')得到一個(gè)字符數(shù)組，然后利用雙指針?biāo)悸愤M(jìn)行操作眶明。最后使用arr.join('')得到操作后的字符串艰毒。
- 利用棧進(jìn)行操作。js中用數(shù)組來實(shí)現(xiàn)棧的操作搜囱。
344. Reverse String
解法一：逆序連接字符串
可以像訪問數(shù)組一樣通過索引值訪問字符串里面不同位置的字符丑瞧。
var reverseString = function(s) {
var reversestring = " ";
for(var i = s.length-1; i >= 0 ; i--){
reversestring += s[i];
}
return reversestring;
};
解法二：雙指針方式
var reverseString = (s) => {
var arr = s.split('');
var i = 0, j = arr.length-1;
while(i<j){
[arr[i], arr[j]] = [arr[j],arr[i]];
i++;
j--;
}
return arr.join('');
};
這里使用了ES6的語(yǔ)法，因?yàn)樵贓S6中對(duì)兩個(gè)字符進(jìn)行交換寫法更為簡(jiǎn)單蜀肘。
解法三：使用棧
在js中可以用數(shù)組實(shí)現(xiàn)棧
var reverseString = (s) => {
var reversestr = '';
var stack = [];//用數(shù)組實(shí)現(xiàn)棧
for(var i = 0;i < s.length; i++){
stack.push(s[i]);
}
while(stack.length!==0){
reversestr += stack.pop();
}
return reversestr;
};
541. Reverse String II
這道題和單純的求逆區(qū)別不大绊汹，需要在外面再加一層循環(huán)，確定要進(jìn)行逆序的范圍
雙指針
var reverseStr = function(s, k) {
var arr = s.split('');
for(var i = 0; i < s.length; i+=2*k){
reverse(arr, i, Math.min(i+k-1, s.length-1));
}
return arr.join('');
};
var reverse = function(arr, i, j){
while(i < j){
var temp = arr[i];
arr[i++] = arr[j];
arr[j--]= temp;
}
};
557. Reverse Words in a String III
image.png
這道題也是需要多一步操作扮宠，就是先利用split函數(shù)將句子中的單詞取出來西乖，對(duì)單詞進(jìn)行求逆。
var reverseWords = function(s) {
var words = s.split(' ');
for(var i = 0; i < words.length; i++){
words[i] = reverse(words[i]);
}
return words.join(' ');
};
var reverse = function(s){
var reversestr = '';
for(var i = s.length-1; i >= 0 ; i--){
reversestr += s[i];
}
return reversestr;
}
917. Reverse Only Letters
image.png
解法一：
先把字符取出來放在數(shù)組中，逆序获雕，然后再放回去鏈接陳字符串薄腻。在鏈接過程中判斷是否需要插入非字母的字符。
var reverseOnlyLetters = function(S) {
if(S.match(/[a-zA-Z]/g) === null) return S;
let arrLetters = S.match(/[a-zA-Z]/g).reverse();
for(var i in S) {
if(!/[a-zA-Z]/.test(S[i])) { arrLetters.splice(i,0,S[i]); }
}
return arrLetters.join('');
};
解法二：雙指針
var reverseOnlyLetters = function(S) {
var arr = S.split('');
var i = 0;
var j = arr.length-1;
while(i<j){
while(i<j && !/[a-zA-Z]/.test(arr[i])){
i++
}
while(i<j && !/[a-zA-Z]/.test(arr[j])){
j--;
}
var temp = arr[i];
arr[i++] = arr[j];
arr[j--] =temp;
}
return arr.join('');
};
解法三：利用棧
思路：如果沒有其他字符届案，那么該問題就是最簡(jiǎn)單的逆序問題被廓。將字符壓入棧中，然后在從前往后遍歷一次字符串萝玷，如果原字符串的位置為字符嫁乘，那么從棧里彈出一個(gè)字符放入。
var reverseOnlyLetters = function(S) {
var stack = [];
for(var i in S){
if(/[a-zA-Z]/.test(S[i]))
stack.push(S[i]);
}
var str ='';
for(var i in S){
if(/[a-zA-Z]/.test(S[i]))
str +=stack.pop();
else
str += S[i];
}
return str;
};
345. Reverse Vowels of a String
image.png
解法一：雙指針
var reverseVowels = function(s) {
var arr = s.split('');
var vowels = 'aeiouAEIOU';
var i = 0;
var j = arr.length-1;
while(i<j){
while(i<j && vowels.indexOf(arr[i]) < 0){
i++;
}
while(i<j && vowels.indexOf(arr[j]) < 0){
j--;
}
var temp = arr[i];
arr[i++] = arr[j];
arr[j--] =temp;
}
return arr.join('');
};
解法二：利用棧
var reverseVowels = function(s) {
var vowels = 'aeiouAEIOU';
var stack = [];
for(var i in s){
if(vowels.indexOf(s[i]) > -1)
stack.push(s[i]);
}
var str ='';
for(var i in s){
if(vowels.indexOf(s[i]) > -1){
str +=stack.pop();
}
else
str += s[i];
}
return str;
};
