字符串双指针

字数统计: 3.2k字   |   阅读时长: 14分

字符串

反转字符串

https://leetcode.cn/problems/reverse-string/

  • 可以用位运算交换字符或整数
    右侧都是s[i] ^ s[j]

顺序是i j i或j i j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public void reverseString(char[] s) {
    int n = s.length;
    // 当 n = length
    // n为偶数，n/2为比一半多一个
    // n为奇数，n/2为中间元素
    for (int i = 0; i < n / 2; i++) {
        int j = n - 1 - i;
        // s[i] 是 s[i] s[j] 模2加的和
        // char 类型可以自动转成int 但是int不能自动转成char
        // 需要强制类型转换
        s[i] = (char)(s[i] ^ s[j]);
        // s[i] ^ s[j] ^ s[j] = s[i] 
        // s[j] 是以前的s[i]
        s[j] = (char)(s[i] ^ s[j]);
        // s[i] ^ s[j] ^ s[j]
        // 当前的 s[j] 保存的是以前的s[i]，异或的结果是以前的s[j]
        s[i] = (char)(s[i] ^ s[j]);
    }
}

反转字符串

https://leetcode.cn/problems/reverse-string-ii/

  • 奇数k反转 偶数k不变
    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
    public String reverseStr(String s, int k) {
        StringBuilder result = new StringBuilder();
        for (int start = 0; start < s.length(); start += k) {
            int end = start + k;
            end = end > s.length() ? s.length() : end;
            if (start / k % 2 == 0) {
                result.append(this.reverse(s.substring(start, end)));
            } else {
                result.append(s.substring(start, end));
            }
        }
        return result.toString();
    }

    private String reverse(String s) {
        char[] charArray = s.toCharArray();
        
        for (int i = 0; i < charArray.length / 2; i++) {
            int j = charArray.length - i - 1;
            charArray[i] = (char)(charArray[i] ^ charArray[j]);
            charArray[j] = (char)(charArray[i] ^ charArray[j]);
            charArray[i] = (char)(charArray[i] ^ charArray[j]);
        }
        return new String(charArray);
    }

替换空格

https://leetcode.cn/problems/ti-huan-kong-ge-lcof/

1
2
3
4
5
6
7
public String replaceSpace(String s) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i<s.length(); i++) {
        builder.append(s.charAt(i) == ' ' ? "%20" : s.charAt(i));
    }
    return builder.toString();
}

颠倒字符串的单词

https://leetcode.cn/problems/reverse-words-in-a-string/

  • ```java
    public String reverseWords(String s) {
    // 不能用stack push，stack仍然是加入顺序存储
    // 使用deque deque加入倒序存储
        Deque deque = new LinkedList<>();
        StringBuilder builder = new StringBuilder();
    // 遍历字符串，空字符不保存，非空字符保存
        for (int i = 0; i < s.length(); i++) {
    // 遇到空字符，可能是前导字符，也可能是单词的结尾字符
    // 前导空字符直接过，结尾空字符，单词加入deque中
            if (s.charAt(i) == ‘ ‘) {
                if (builder.length() != 0) {
                    deque.addFirst(builder.toString());
                    builder.delete(0, builder.length());
                }
                continue;
            }
            builder.append(s.charAt(i));
        }
    // 最后的单词可能没保存，保存一下
        if (builder.length() != 0) {
            deque.addFirst(builder.toString());
        }
        return String.join(“ “, deque);
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9

    #### 左旋转字符串Ⅱ

    [https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/](https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)

    ```java
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }

KMP

图片

图片

KMP的核心就是匹配失败时，不用从pattern开头匹配，string也不用回退，而是从当前位置继续匹配

比如 string = “aabaabaaf” pattern = “aabaaf”

当匹配到 aabaab aabaaf时，f与b匹配失败，看f前面不包含f的字符串aabaa，最长相等前后缀的长度

发现是2，即前缀aa 后缀aa相等，也就是刚刚后缀aa与aabaa最后的aa匹配了，那么前缀与后缀相等，也

会与aa匹配，所以在重新匹配的时候，直接从前缀的下一个位置开始匹配即可。这个过程最关键的就是：保存最长相等前后缀长度的next数组

next[i]含义 模式串pattern[0, i] 最长相等前后缀的长度

pattern[0, i]前缀 不包含末尾字符i，第一个字符0开始的连续子串

pattern[0, i]后缀 不包含开头字符0，最后一个字符i结束的连续子串

求next数组步骤

j 前缀末尾以及最长前后缀长度

i 后缀末尾

  1. 初始化 j 与 next

  2. 前缀末尾与后缀末尾不相等时的处理

  3. 相等时的处理

  4. 更新next数组

实现strStr()

https://leetcode.cn/problems/implement-strstr/

  • 两层循环嵌套，利用startsWith
    外层循环一次只移动一次，而不是从匹配失败的地方开始，不会漏掉下面的情况

str = “aaaab”

pattern = “aaab”

不然匹配到str的最后一个a，从这个地方匹配pattern的第一个”a”匹配不到

看来只有KMP方法才能让str指针不回退

1
2
3
4
5
6
7
8
9
public int strStr(String haystack, String needle) {
    int length = haystack.length();
    for (int i = 0; i < length; i++) {
        if (haystack.substring(i, length).startsWith(needle)) {
            return i;
        }
    }
    return -1;
}

  • KMP

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    /*
        KMP的核心就是匹配失败时，不用从pattern开头匹配，string也不用回退，而是从当前位置继续匹配
        比如 string = "aabaabaaf" pattern = "aabaaf"
        当匹配到 aabaab aabaaf时，f与b匹配失败，看f前面不包含f的字符串aabaa，最长相等前后缀的长度
        发现是2，即前缀aa 后缀aa相等，也就是刚刚后缀aa与aabaa最后的aa匹配了，那么前缀与后缀相等，也
        会与aa匹配，所以在重新匹配的时候，直接从前缀的下一个位置开始匹配即可。这个过程最关键的就是
        保存最长相等前后缀长度的next数组
    */
    /*
        kmp步骤
        1. 初始化 根据pattern创建next数组，利用getNext方法求next
        2. for遍历string 处理相等字符的情况
        3. 处理不等字符的情况
        4. 判断pattern是否被匹配完
    */
    public int strStr(String haystack, String needle) {
        int[] next = new int[needle.length()];
        this.getNext(needle, next);
        int j = 0;
        // j是pattern的索引，pattern[0, j)表示匹配上了，j指向当前要匹配的字符
        // i是string的索引，string[0, i)已经遍历匹配了，i指向当前要比较的字符
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            // pattern 全匹配上了
            if (j == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        return -1;

    }
    /*
        next[i]含义 模式串pattern[0, i] 最长相等前后缀的长度
        pattern[0, i]前缀 不包含末尾字符i，第一个字符0开始的连续子串
        pattern[0, i]后缀 不包含开头字符0，最后一个字符i结束的连续子串
        求next数组步骤
        j 前缀末尾以及最长前后缀长度
        i 后缀末尾
        1. 初始化 j 与 next
        2. 前缀末尾与后缀末尾不相等时的处理
        3. 相等时的处理
        4. 更新next数组
    */
    private void getNext(String pattern, int[] next) {
        int j = 0;
        next[0] = 0;
        // j是前缀的末尾字符，i是后缀的末尾字符
        // [0, j]是模式串 [前面第一次匹配成功的, i]是待匹配的字符串
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = next[j - 1];
            }
            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++;
            }
            // 记录相等前后缀的长度
            next[i] = j;
        }
    }

  • KMP模板精简注释

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    /*
        kmp步骤
        1. 初始化 求next
        2. 从i=0遍历字符，不等字符处理
        3. 相等字符处理
        4. 判断是否全匹配上了
    */
    public int strStr(String haystack, String needle) {
        int length = needle.length();
        if (length == 0) {
            return 0;
        }
        
        int j = 0;
        int[] next = new int[length];
        this.getNext(needle, next);
        // i是待匹配字符索引，j是模式索引
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == length) {
                return i - length + 1;
            }
        }
        return -1;
    }
    /*
        1. 初始化next
        2. 从i=1遍历字符，不等字符处理，回退
        3. 相等字符处理，j++
        4. 更新next
    */
    private void getNext(String pattern, int[] next) {
        int j = 0;
        next[0] = 0;
        // i是待匹配字符索引，j是模式索引
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }

重复的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/

  • KMP
    len = str.length()

先说结论

如果len % (len - next[len-1])等于0(并且next[len-1] ≠0)，则str是由重复字符串构成的

如何证明该结论，用反证法

图片

即假设str不是由重复子串构成，比如aaba，那么len % (len - next[len - 1]) = 4 % (4 - 1) = 1≠0 (当然我没有举例出所有不是由重复子串构成的str，len % (len - next[len - 1])≠0，所以逻辑是不正确的，主要是我不会)

尝试证明一种特殊的情况

a b c d f a b c d a b c d

由于f不是重复的部分，那么next[len-1]的长度肯定不会超过”bcdf”的长度，那么不想推理了，最后肯定len - next[len - 1] 比len的一半大，那么len % ()肯定不为0

与条件矛盾，假设不成立，原命题正确

反正法的依据是排中律：A ∨A肯定是正确的，即如果A不正确，那么A肯定是正确的

~A => B => C => D

如果证明D完全错了，那么A也是错的，命题与集合是对应的，在推导过程中A集合扩大为B集合，B集合可能完全等价C集合，C集合扩大为D集合，但是A集合是包含于D集合中的，如果发现D命题完全是错的，也就是集合D中全是屎，那么A在D中，A中也全是屎，A是错的，那么A就是正确的

图片

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
public boolean repeatedSubstringPattern(String s) {
    // 只有一个字符，没有重复，所以是false
    if (s.length() == 1) {
        return false;
    }
    int length = s.length();
    int[] next = new int[length];
    this.getNext(s, next);
    System.out.println(Arrays.toString(next));
    // next数组最后不能为0，前后缀不相等，肯定不是重复字符串构成的
    return next[length - 1] != 0 && length % (length - next[length - 1]) == 0;
}

/*
    求next
    1. 初始化
    2. 相等情况处理
    3. 不等情况处理
    4. 更新next
*/
private void getNext(String s, int[] next) {
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < s.length(); i++) {
        while (j > 0 && s.charAt(j) != s.charAt(i)) {
            j = next[j - 1];
        }
        if (s.charAt(j) == s.charAt(i)) {
            j++;
        }
        next[i] = j;
    }
}

双指针

移除元素

https://leetcode.cn/problems/remove-element/

1
2
3
4
5
6
7
8
9
10
11
public int removeElement(int[] nums, int val) {
    // 快慢指针，快指针遍历所有元素，慢指针的前面都是不用删除的元素
    // 快指针遇到要删除的元素就不移动到前面，遇到不用删除的元素移动到前面
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

反转链表

https://leetcode.cn/problems/reverse-linked-list/

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

删除倒数第n个节点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

图片

图片

图片

利用虚拟节点，方便删除头节点

fast节点比slow节点快n+1步，也就是slow会停留在倒数n个节点的前一个，这样才能删除倒数第n个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    // 快指针移动n + 1个节点
    for (int i = 0; i < n + 1; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

长链表移动到和短链表一样的位置，因为如果存在公共节点的话，也是在短链表长度范围内

环形链表Ⅱ

https://leetcode.cn/problems/linked-list-cycle-ii/

图片

本来还想对比一下我自己写的跟代码随想录给的有什么差异，对比改进一下，发现就像屎和金子，都能运行，但差别太大。

核心逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// fast != null 保证fast.next命令正常 fast.next != null 保证 fast.next.next 正常
while (fast != null && fast.next != null) {
  // fast移动两个节点
  fast = fast.next.next;
  slow = slow.next;
  // 用if判断是否相遇，然后再使用循环找入口节点
  if (slow == fast) {
      index1 = slow;
      index2 = fast;
      while (index1 != index2) {
        // 移动一格
      }
      return index2;
  }
  
}

我的屎代码

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
39
40
41
42
43
44
45
46
47
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead==null) {
            return pHead;
        }
        ListNode slow = pHead;
        ListNode fast = pHead.next;
        while (fast!=slow) {
            if (slow == null) {
                return slow;
            }
            else {
                slow = slow.next;
            }
            if (fast == null) {
                return fast;
            }
            else {
                fast = fast.next;
            }
            if (fast == null) {
                return fast;
            }
            else {
                fast = fast.next;
            }
        }
        fast = pHead;
        slow = slow.next;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

三数之和

https://leetcode.cn/problems/3sum/

如果回溯不超时的话，可以直接套用回溯模板

关键就是去重，当前节点是否重复要和上一个访问过的节点比较，而不是和下一个节点比较，否则会丢解

图片

四数之和

https://leetcode.cn/problems/4sum/

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北科大计算机在读<br><br>爱好编程<br><br>热爱技术<br><br>喜欢折腾