之前写过关于逆序问题的JAVA版总结。因为现在开始搞前端了，所以用JS又做了一遍这些题目。改变语言之后虽然很多思路都差不多但是一些常用的函数还是需要整理一下的。

常见的解法思路：

• 双指针方式。利用var arr = s.split('')得到一个字符数组，然后利用双指针思路进行操作。最后使用arr.join('')得到操作后的字符串。
• 利用栈进行操作。js中用数组来实现栈的操作。

344. Reverse String

解法一：逆序连接字符串

可以像访问数组一样通过索引值访问字符串里面不同位置的字符。

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的语法，因为在ES6中对两个字符进行交换写法更为简单。

解法三：使用栈

在js中可以用数组实现栈

var reverseString = (s) => {
    var reversestr = '';
    var stack = [];//用数组实现栈
    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

这道题和单纯的求逆区别不大，需要在外面再加一层循环，确定要进行逆序的范围
双指针

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函数将句子中的单词取出来，对单词进行求逆。

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

解法一：

先把字符取出来放在数组中，逆序，然后再放回去链接陈字符串。在链接过程中判断是否需要插入非字母的字符。

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

解法三：利用栈

思路：如果没有其他字符，那么该问题就是最简单的逆序问题。将字符压入栈中，然后在从前往后遍历一次字符串，如果原字符串的位置为字符，那么从栈里弹出一个字符放入。

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;
};