问题：反转字符串

问题描述：

1
将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例：

1
2
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

解法：

1
2
3
4
5
6
var reverseString = function(s){
	let l = -1, r = s.length;
    while(++l < --r)
        [s[l], s[r]] = [s[r], s[l]];
    return s;
}

问题：反转字符串II

问题描述：

1
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例：

1
2
输入: s = "abcdefg", k = 2
输出: "bacdfeg"

解题秒点：

1
2
1. 不用使用计算器来计算2k，直接让i+=(2*k)就完事
2. 不用让i每个步长为1，for循环里按需修改步长

解法：

1
2
3
4
5
6
7
8
9
10
11
var reverseStr = function(s, k){
    const len = s.length;
    let resArr = s.split("");
    for(let i=0;i<len;i+=2*k){
        //right的处理好聪明啊！
        let left = i-1, right=i+k>len?len:i+k;
        while(++left < --right)
            [resArr[left], resArr[right]] = [resArr[right], resArr[left]];
    }
    return resArr.join("");
}

问题：替换空格

问题描述：

1
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例：

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

解题步骤：很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作

1
2
1. 扩充数组到每个空格替换成"%20"之后的大小
2. 从后向前替换空格，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾。
解题图示

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 + 2*count - 1;
    while(left >= 0){
        if(strArr[left]===' '){
            strArr[right--] = '0';
            strArr[right--] = '2';
            strArr[right--] = '%';
            left--;
        }else
            strArr[right--] = strArr[left--];
    }
    return strArr.join("");
}

问题：翻转字符串里的单词

问题描述：

1
给定一个字符串，逐个翻转字符串中的每个单词

示例1：

1
2
输入: "the sky is blue"
输出: "blue is sky the"

示例2：

1
2
3
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例3：

1
2
3
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路：

1
2
3
1. 移除多余空格
2. 将整个字符串反转
3. 将每个单词反转

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var reverseWords = function(s){
    var strArr = Array.from(s);
    //移除多余空格
    removeExtraSpaces(strArr);
    //整个字符串翻转
    reverse(strArr, 0, strArr.length-1);
    //翻转单词
    let start = 0;
    for(let i=0;i<=strArr.length;i++){
        if(strArr[i]===' '||i===strArr.length){
            reverse(strArr, start, i-1);
            start = i+1;
        }
    }
    return strArr.join("");
}
function removeExtraSpaces(strArr){
    var slow = 0;
    var fast = 0;
    //不能移除所有空格
    while(fast<strArr.length){
        if(strArr[fast]===' '&&(fast===0||strArr[fast-1]===''))
            fast++;
        else
            strArr[slow++] = strArr[fast++];
    }
    //移除末尾空格
    strArr.length = strArr[slow - 1]===' '?slow-1:slow;
}
function reverse(strArr, start, end){
    let left = start;
    let right = end;
    while(left<right){
        [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
        left++;
        right--;
    }
}

问题：左旋转字符串

问题描述：

1
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例：

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"

解题步骤：

1
2
3
1. 反转区间为前n的子串
2. 反转区间为n到末尾的子串
3. 反转整个字符串
解题释义

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var reverseLeftWords = function(s, n){
    function reverseWords(strArr, start, end){
        while(start<end){
            [strArr[start], strArr[end]] = [strArr[end], strArr[start]];
            start++;
            end--;
        }
    }
    let strArr = s.split('');
    let length = strArr.length;
    reverseWords(strArr, 0, n-1);
    reverseWords(strArr, n, length-1);
    reverseWords(strArr, 0, length-1);
    return strArr.join('');
}

问题：实现strStr()

问题描述：

1
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例：

1
2
输入: haystack = "hello", needle = "ll" 
输出: 2

KMP算法关键点：o(n*m)

1
2
3
4
- next数组是前缀表。前缀表是用来回退的，它记录了模式串和主串不匹配的时候，模式串应该从哪里重新匹配。前缀表用来记录最长相等前后缀。
- 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串，后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
- 模式串与前缀表对应位置的数字之间的关系：下标i之前的字符串中，有多大长度的相同前缀后缀。
- 很多代码实现的时候会将前缀表统一减一，也就是右移一位，初始位置为-1，只是为了具体实现方便。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//next数组右移一位
var strStr = function(haystack, needle){
    if(needle.length===0)
        return 0;
    const getNext = needle=>{
        let next = [];
        let j = -1;
        next.push(j);
        for(let i=1;i<needle.length;i++){
            while(j>=0&&needle[i]!==needle[j+1])
                j = next[j];
            if(needle[i]===needle[j+1])
                j++;
            next.push(j);
        }
        return next;
    }
    let next = getNext(needle);
    let j = -1;
    for(let i=0;i<haystack.length;i++){
        while(j>=0&&haystack[i]!==needle[j+1])
            j = next[j];
        if(haystack[i]===needle[j+1])
            j++;
        if(j === needle.length-1)
            return (i-needle.length+1);
    }
    return -1;
}

问题：重复的子字符串

问题描述：

1
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例：

1
2
3
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

解题步骤（移动匹配+KMP）：

1
2
3
4
5
6
7
8
9
要点：最长相等前后缀不包含的子串就是最小重复子串
步骤：
步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：s[0]s[1]与s[2]s[3]相同 。
步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。
步骤三： 因为 这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。
步骤四：循环往复。
所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。

思路：只要两个s拼接在一起的时候，还出现一个s的话，那么说明是重复串。注意要刨除s+s的首字符和尾字符，避免搜索出原来的s。
图示

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 前缀表统一减一
var repeatedSubstringPattern = function(s){
    if(s.length===0)
        return false;
    const getNext = s=>{
        let next = [];
        let j = -1;
        next.push(j);
        for(let i=1;i<s.length;i++){
            while(j>=0&&s[i]!==s[j+1])
                j = next[j];
            if(s[i]===s[j+1])
                j++;
            next.push(j);
        }
        return next;
    }
    let next = getNext(s);
    //计算所得，若len%(len-(next[len-1]+1))==0则说明有重复子串
    if(next[next.length-1]!==-1&&s.length%(s.length-(next[next.length-1]+1))===0)
        return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const getNext = function(needle){
    let next = [];
    let j = -1;
    next.push(j);
    for(let i=1;i<needle.length;i++){
        while(j>=0&&needle[i]!==needle[j+1])
            j = next[j];
        if(needle[i]===needle[j+1])
            j++;
        next.push(j);
    }
    return next;
}

var repeatedSubstringPattern = function(s){
    if(s.length===0)
        return 0;
    let next = getNext(s);
    let j= -1;
    let s2 = s+s;
    for(let i=1;i<s2.length-1;i++){
        while(j>=0&&s2[i]!==s[j+1])
            j = next[j];
        if(s2[i]===s[j+1])
            j++;
        if(j===s2.length-1)
            return true;
    }
    return false;
}

问题：无重复字符的最长子串

描述：

1
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度

示例：

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 滑动窗口的做法
var lengthOfLongestSubstring = function(s){
    let map = new Map();
    let max = 0, start=0;
    for(let i=0;i<s.length;i++){
        let ch = s.charAt(i);
        if(map.has(ch))
            // 这里如果只是start=map.get(ch)+1的话可能会出现"abba"这样的测试用例过不去
            // 因为后面出现的字符可能在map中出现的位置在前面字符之前
            start = Math.max(start, map.get(ch)+1);
        max = Math.max(max, i-start+1);
        map.set(ch, i);
    }
    return max;
}

最长公共前缀

描述：

1
2
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
var longestCommonPrefix = function(strs){
    if(strs.length===0)
        return "";
   	let length = strs[0].length;
    let count = strs.length;
    for(let i=0;i<length;i++){
        let ch = strs[0].charAt(i);
        for(let j=1;j<count;j++)
            if(i===strs[j].length || strs[j].charAt(i)!==ch)
                return strs[0].substring(0, i);
    }
    return strs[0];
}

验证回文串

描述：

1
2
3
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例：

1
2
3
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

解法：

1
2
3
4
5
6
7
8
var isPalindrome = function(s) {
    // 先替换掉所有非数字和字符
    // 再替换掉所有空格
    // 将所有字母转换为小写
    s = s.replace(/[^a-zA-Z0-9]/g, "").replace(/\s/g,"").toLowerCase();
    // 反转比较是否相同
    return s===[...s].reverse().join('');
};

字符串的排列

描述：

1
2
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

示例：

1
"ab"

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function Permutation(str)
{
    let res = [], path = [];
    let strarr = str.split('');
    // 字符排序需要注意
    strarr.sort((s,t)=>{
        let a = s.toLowerCase();  
        let b = t.toLowerCase();
        console.log(a, b, a<b);  
        if (a < b) return -1;  
        if (a > b) return 1;  
        return 0;
    });
    function backtracking(used){
        if(path.length===strarr.length){
            res.push([...path]);
            return;
        }
        for(let i=0;i<strarr.length;i++){
            if(used[i])
                continue;
            // 去重
            if(i>0&&strarr[i]===strarr[i-1]&&!used[i-1])
                continue;
            used[i]=true;
            path.push(strarr[i]);
            backtracking(used);
            used[i]=false;
            path.pop();
        }
    }
    backtracking([]);
    return res.map(item=>item.join(''));
}

进制转换

描述：

1
给定一个十进制数 M ，以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。

示例：

1
2
输入：7,2
返回值："111"

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function solve( M ,  N ) {
    if(M===0)
        return "0";
    let base = "0123456789ABCDEF";
    let res = [];
    let flag = false;
    if(M<0){
        M = -M;
        flag = true;
    }
    while(M){
        res.push(base.charAt(M%N));
        M=Math.floor(M/N);
    }
    if(flag)
        res.push('-');
    return res.reverse().join('');
}

第一个只出现一次的字符

描述：

1
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

示例：

1
2
输入："google"
返回值：4

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
function FirstNotRepeatingChar(str)
{
    let hash = new Map();
    for(let i=0;i<str.length;i++)
        if(!hash.has(str[i]))
            hash.set(str[i],1);
        else
            hash.set(str[i], hash.get(str[i])+1);
    for(let i=0;i<str.length;i++)
        if(hash.get(str[i])===1)
            return i;
    return -1;
}

比较版本号

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function compare( version1 ,  version2 ) {
    let arr1 = version1.split('.');
    let arr2 = version2.split('.');
    for(let i=0;i<arr1.length||i<arr2.length;i++){
        let str1 = i<arr1.length?arr1[i]:"0";
        let str2 = i<arr2.length?arr2[i]:"0";
        let num1 = 0;
        for(let j=0;j<str1.length;j++)
            num1=num1*10+parseInt(str1[j]);
        let num2 = 0;
        for(let j=0;j<str2.length;j++)
            num2=num2*10+parseInt(str2[j]);
        if(num1>num2)
            return 1;
        if(num1<num2)
            return -1;
    }
    return 0;
}