leetcode每天5题-Day33

1.反转字符串

344. 反转字符串-简单
b站视频-代码随想录
要求：原地修改，空间复杂度为O(1)

该题也是双指针法的一个经典应用。
思路：首尾交换

var reverseString = function(s) {
    const len = s.length;
    if(len === 1) return s;
    let l = 0,r = len - 1;
    while(l < r){
        [s[l], s[r]] = [s[r], s[l]];
        l++,r--;
    }
    return s;
};
1
2
3
4
5
6
7
8
9
10

代码随想录版👇

var reverseString = function(s) {
    //Do not return anything, modify s in-place instead.
    reverse(s)
};

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

2.反转字符串II

541. 反转字符串 II-简单
b站视频-代码随想录
解题思路：模拟，按照题目中的反转规则反转字符串即可
重点：用i遍历字符串时，不是i++，而是i+=2k

var reverseStr = function(s, k) {
    // 把字符串转化成字符串数组sArr
    let sArr = 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){
            [sArr[l],sArr[r]] = [sArr[r],sArr[l]];
        }
    }
    return sArr.join("");
};
1
2
3
4
5
6
7
8
9
10
11

3.替换空格

剑指 Offer 05. 替换空格-简单
双指针
思路：先统计字符串中空格的数量，然后根据这个数量把数组大小扩充为替换空格后的大小，最后双指针从后向前遍历，遇到空格就将其替换成%20

注：从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。

var replaceSpace = function(s) {
    // 将s转为字符串数组sArr
    let sArr = Array.from(s);
    // 统计字符串中空格的数量
    let count = 0;
    for(const c of sArr){
        if(c === ' ') count++;
    }
    let l = s.length - 1;
    let r = s.length + 2*count -1;
    while(l >= 0){
        if(sArr[l] == ' '){
            sArr[r--] = '0';
            sArr[r--] = '2';
            sArr[r--] = '%';
            l--;
        }else{
            sArr[r--] = sArr[l--];
        }
    }
    return sArr.join('');
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：O(n)
空间复杂度：O(1)

4.反转字符串中的单词

151. 反转字符串中的单词-中等
b站视频-代码随想录
思路：移除多余空格—>将整个字符串反转—>将每个单词反转
移除多余空格时，使用双指针，思路与数组那一章节leetcode27.移除元素一样

var removeExtraSpaces = function(sArr) {
    let slow = 0,fast = 0;
    while(fast < sArr.length){
        // 移除开始位置和重复的空格
        if(sArr[fast] === ' ' && (fast === 0 || sArr[fast - 1] === ' ')){
            fast++;
        }else{
            sArr[slow++] = sArr[fast++];
        }
    }
    // 移除末尾空格
    sArr.length = sArr[slow - 1] === ' '?slow - 1:slow;
};
var reverse = function(s,l,r){
    while(l < r){
        [s[l],s[r]] = [s[r],s[l]];
        l++,r--;
    }
};
var reverseWords = function(s) {
    const sArr = Array.from(s);
    removeExtraSpaces(sArr);
    // 将整个字符串反转
    reverse(sArr,0,sArr.length - 1);
    // 反转每个单词
    let start = 0;
    for(let i = 0;i <= sArr.length;i++){
        if(sArr[i] === ' ' || i === sArr.length){
            reverse(sArr,start,i - 1);
            start = i + 1;
        }
    }
    return sArr.join('');
};
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

时：O(n)
空：O(1)
感觉这道题还是比较复杂的，估计做个两三遍才能自己做出来..

5.左旋转字符串

剑指 Offer 58 - II. 左旋转字符串-简单

超时版

var reverseLeftWords = function(s, n) {
    let sArr = Array.from(s);
    while(n > 0){
    let num = sArr.shift();
        sArr.push(num);
        n--;
    }
    return sArr.join('');
};
1
2
3
4
5
6
7
8
9

超出时间限制…
思路：和上一题一样，整体反转+两次局部反转

根据思路自己写的

var reverse = function(s,l,r) {
    while(l < r){
        [s[l],s[r]] = [s[r],s[l]];
        l++,r--;
    }
    return;
}
var reverseLeftWords = function(s, n) {
    let sArr = Array.from(s);
    // 反转整个字符串
    reverse(sArr,0,sArr.length-1);
    // 反转前 sArr.length-n 个字符
    reverse(sArr,0,sArr.length-n-1);
    // 反转后n个字符
    reverse(sArr,sArr.length-n,sArr.length-1);
    return sArr.join('');
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时：O(n)
空：O(1)

代码随想录版

var reverseLeftWords = function(s, n) {
  const length = s.length;
  let i = 0;
  while (i < length - n) {
    s = s[length - 1] + s;
    i++;
  }
  return s.slice(0, length);
};
1
2
3
4
5
6
7
8
9

6.实现 strStr()

28. 找出字符串中第一个匹配项的下标-简单
本题是KMP 经典题目。
“在一个串中查找是否出现过另一个串，这是KMP的看家本领。”
KMP的经典思想就是：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

b站视频-代码随想录

前缀表是什么？
记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
最长相等前后缀？

前缀表其实就是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
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

前缀表统一不减一

var strStr = function(haystack, needle) {
    // 求next数组，即前缀表
    const getNext = (needle) => {
        let next = [];
        let j =0;
        next.push(j);

        for(let i = 1;i < needle.length;i++){
            while(j > 0 && needle[i] !== needle[j]){
            // j回退
                j = next[j-1];
            }
            if(needle[i] === needle[j]){
                j++;
            }
            // 更新next数组
            next.push(j);
        }
        return next;
    }

    let next = getNext(needle);
    let j = 0;
    for(let i = 0;i < haystack.length;i++){
        while(j > 0 && haystack[i] !== needle[j]){
            j = next[j-1];
        }
        if(haystack[i] === needle[j]){
            j++;
        }
        if(j === needle.length){
            return i-needle.length + 1;
        }
    }
    return -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
30
31
32
33
34
35
36

7.重复的子字符串

459. 重复的子字符串-简单
b站视频-代码随想录
①暴力解法O(n²)
字串起始位置一定是0，只需一层for循环找子串结尾位置，一层for循环比较主串与子串。
②移动匹配
思路：如果该字符串由子串组成，那它就满足前半部分与后半部分相等的情况。拼接字符串，然后看去除首尾字符的s+s中是不是存在s
③KMP解法
重点：在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串
推导过程👉代码随想录

var repeatedSubstringPattern = function(s) {
    if(s.length === 0) return false;

    const getNext = (s) => {
        let next = [];
        let j =0;
        next.push(j);
        for(let i = 1;i < s.length;i++){
            while(j > 0 && s[i] !== s[j]){
                j = next[j - 1];
            }
            if(s[i] === s[j]){
                j++;
            }
            next.push(j);
        }
        return next;
    }

    let next = getNext(s);
    if(next[next.length-1] !== 0 && s.length % (s.length - next[next.length-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