Leetcode

替换元素：从后往前的双指针法

在a-b-c中将每一个-替换成任意一个字符串(比如aj)，空间开销为O(1)的做法：

  1. 首先计算-的数目，算出替换结束后最终字符串会有多大，按新的大小resize字符串

  2. 双指针，一个指针指向新字符串的末尾，另一个指向旧字符串的末尾

  3. 从后往前遍历

    1
    2
    3
    4
    5
    6
    7
    if(s[oldPtr]!='-'){
    	s[newPtr--]=s[oldPtr--];
    } else {
      oldPtr--;
      s[newPtr--]='j';
      s[newPtr--]='a';
    }

删除元素：快慢指针法

在-abc—bbbb-ccc–中删除-

空间开销为O(1)的做法：

  1. 快指针往后走，发现不是’-‘的字符，就让慢指针复制这个元素并往后走一步

  2. 但是这样会把-完全删掉，如果题目要求每两个单词之间至少要保留一个-，那么让快指针每次从’-‘走到有意义的字符时提醒慢指针添加一个’-‘即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 版本二 
    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

翻转句子中的单词

He is a handsome boy.

  1. 首先完全翻转 yob emosdnah a si eH.
  2. 然后将每个单词又翻转回来即可 boy handsome a is He.

K!M!P!

首先我想到的是快慢指针法

快指针和慢指针一开始都指向开头，快指针先顺次遍历，直到匹配不上

这个时候将慢指针移到快指针不匹配的地方，快指针开始从头匹配直到有一天快指针终于匹配上，慢指针在的位置就是要找的位置。

然而这样是错的！

问题的关键在于如果快指针所经历的后缀真子串（我发明的叫法）包含了模式串的前缀真子串，这时候慢指针一跳就把这部分忽略了：

当到达下面的状态时

慢指针直接跳到b从b开始匹配，就把模式串的前缀真子串给略过了

所以我们要用前缀表

使用前缀表，在不匹配的时候在模式串中回退，这种回退必须是考虑到模式串子前缀的，而前缀表可以实现这一点，当模式串匹配失败时，可以检查前缀表考察前面一个子串有没有公共前后缀，如果有的话，那么应该从公共前缀处继续尝试匹配或回退直到退无可退为止(j==0)

详解:实现strstr()

构造前缀表本身就很难

构造前缀表也要用到已经构造好的前缀表，我们用j表示已经匹配到的前缀，当匹配不上时也是一遍回退一遍继续尝试

复杂度

KMP可以将复杂度从暴力算法的O(MN)变成O(M+N)

完整代码

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
class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

检测链表环并找到环入口

在一个单链表中可能存在一个环，找到这个环的入口

检测一个环是很简单的（虽然我还是没想出来），只要一个慢指针一个快指针，慢指针每次走一格，快指针每次走两格，只要有换，快慢指针肯定会碰上

环有了，入口在哪里？

首先要明确一点，fast和slow相遇时，slow还没有在环里走环一圈

可以这样理解：

如果fast和slow同时从环入口出发，那么他们下次相遇也是环入口，这个时候fast走了两圈，slow走了一圈

现在的情况是因为有了X，因此slow进来的时候，fast已经在环的某个位置了，那fast就不用超过slow一圈就能追上了，所以slow是走不满一圈的

那么，相遇时，slow走的距离就是，那么fast呢？fast在相遇时，比slow在环里多走了一圈或多圈，我们设为n，又因为fast的速度是slow的两倍，于是有

这个式子意味着如果我们让一个指针从头出发，一个指针从相遇处出发，那么他们相遇的地方就是入口节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

三数之和为0

给定一个数组，找到其三数之和为0的所有组合，不能重复

排序

一个i从左向右遍历数组，压缩区间，left right分别在区间的两边，按双指针向中间靠拢，不断寻找令nums[left]+nums[right]==-nums[i]的组合即可

去重

i的去重很简单，如果遍历到和上一个一样的i直接继续下一个i即可

left和right应该在找到一个三元组后去重，参考：-3 -1 -1 4 4

注意应该直接在针对这个三元组的结果上去重，而不是傻乎乎的先加减left和right之后再去重

分析这两种写法

1
2
3
4
5
6
7
ans.add(arr);
do{
    left++;
}while(left<right && nums[left]==nums[left+1]);
do{
    right--;
}while(left<right && nums[right]==nums[right-1]);
1
2
3
4
5
ans.add(arr);
while(left<right && nums[left]==nums[left+1]){left++;}
while(left<right && nums[right]==nums[right-1]){right--;}
left++;
right--;

对于输入[-2,0,1,1,2]

第一种写法在找到-2，0,2后直接++–，然后去重，导致-2,1，1被当做重复去掉了

第二种写法不会有这种情况

第一种写法（也就是我的想法）以为可以直接去取重复序列的最后一个值，殊不知这样会挤压另一个指针取到这个重复序列值的可能

第二种方法则总是取重复序列的第一个值，然后去重，这样不会挤压另一个指针的生存空间

想要把第一种方法改对？只需要将nums[left+1]和nums[right-1]改成nums[left-1]和nums[right+1]就能够总是取重复序列的第一个值了

1
2
3
4
5
6
7
ans.add(arr);
do{
  	left++;
}while(left<right && nums[left]==nums[left-1]);
do{
  	right--;
}while(left<right && nums[right]==nums[right+1]);

翻转单链表

（面试百度的时候问到了这个）

最基本的双指针用法，但是要把代码写得优雅精巧是一件很困难的事

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
  public ListNode reverse(ListNode head){
    ListNode cur=head;
    ListNode prev=null;
    ListNode tmp=null;
    while(cur!=null){
      tmp=cur.next;
      cur.next=prev;
      prev=cur;
      cur=tmp;
    }
    return prev;
  }
}