代码随想录第九天

28 实现strStr()

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

KMP经典题目
当字符串不匹配时，可以记录一部分之前已经匹配的文本内容，避免从头匹配
主要是字符串匹配

前缀表也就是next数组
前缀表是为了回退的，他记录了模式串与主串不匹配时，模式串应该从哪里开始重新匹配
前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配
记录下标i之前包括i的字符串中，有多大长度的相同前缀后缀

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

前缀表要求的就是相同前后缀的长度
需要做到最长相等前后缀长度

如何计算前缀表
以aabaaf举例
a 最长相同前后缀长度 0
aa 最长相同前后缀长度 1 - a
aab 最长相同前后缀长度 0
aaba 最长相同前后缀长度 1 - a
aabaa 最长相同前后缀长度 2 - aa
aabaaf 最长相同前后缀长度 0

模式串和前缀表对应位置的数字表示的就是下标i前包括i的字符串中，有多大长度的相同前缀后缀
找到不匹配的位置，找前一个字符的前缀表数值，前一个前缀表数值是2，所以把下标移动到下标2的位置继续匹配

前缀表就是next数组，实现方式有两种，一种是前缀表，另一种是前缀表统一减一（右移一位，初始位置是-1）

使用next数组进行匹配，匹配过程见gif图

具体解法：

1. 滑动窗口，简单的双指针

一个指针指长string开头，一个指针指匹配string开头
找不到，就重新在长string中找下一个可以匹配的开头

注意在对比两个string的时候，需要判断index的大小和string的长度

class Solution{
	public int strStr(String haystack, String needle){
	
		// setup length variable
		int m = haystack.length();
		int n = needle.length();
		
		// easy check length
		if(m < n){
			return -1;
		}
		
		//set two pointers
		int i = 0; 
		int j = 0;
		
		// set maximum i
		while (i < m - n + 1){
			// change haystack pointer to the first equal character of needle
			while (i < m && haystack.charAt(i) != needle.charAt(j)) i++;
			
			// if there is no needle first character return
			if (i == m){
				return -1;
			}
			
			// compare each character in haystack and needle
			while (i < m && j < n && haystack.charAt(i) == needle.charAt(j)){
				i++;
				j++;
			}
			
			// if complete needle is found
			if (j == n){
				return i - j;
			} else {
				// if needle is not found, return i to the next postion of the start
				i = i - j + 1;
				j = 0;
			}
		
		}
		
		return -1;
		
	}
}

2. KMP算法，前缀减一法实现
3. 定义getNext函数构建next数组（计算模式串s，前缀表的过程）
   1. 初始化
      定义两个指针i和j，j指向前缀末尾位置，i指向后缀位置
      对next的初始化赋值，第一个值为-1
   2. 处理前后缀不相同的情况
      因为j初始化为-1， i从1开始，进行是s[i] 和是s[j+1]的比较
      如果遇到s[i] 与 s[j+1]不相同 向前回退
      s[i] 与 s[j+1] 不相同，就要找 j+1前一个元素在next数组里的值（就是next[j]）
   3. 处理前后缀相同的情况
      s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i]

2. 得到next数组之后，进行匹配
   定义两个下标j指向模式串起点， i指向文本串起始位置
   j 从 -1开始
   i 从 0开始
   s[i] 与 s[j+1] 比较
3. 如果不相同，j从next数组中找下一个匹配的位置
4. 相同，i和j同时向后移动
   如果j指向模式串的末尾，说明匹配到了，返回i-模式串长度 + 1

具体实现

class Solution {
    public int strStr(String haystack, String needle) {
        int j = -1;
        int[] next = getNext(needle);

        for (int i = 0; i < haystack.length(); i++){
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)){
                j = next[j];
            }

            if (haystack.charAt(i) == needle.charAt(j + 1)){
                j++;
            }

            if (j == needle.length() - 1){
                return i - needle.length() + 1;
            }
        }

        return -1;
    }
    private int[] getNext(String s){
        int[] next = new int[s.length()];
        int j = -1;
        next[0] = j;

        for(int i = 1; i < s.length(); i++){
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)){
                j = next[j];
            }

            if (s.charAt(i) == s.charAt(j + 1)){
                j++;
            }

            next[i] = j;
        }

        return next;
    }
}

459 重复的子字符串

在一个串中查找是否出现过另一个串，就是kmp
再由重复子串组成的字符串中，最长相等前后缀不包含的子串，就是最小重复子串

首先找到next数组，找到最长相等前后缀不包含的子串
然后判断字符串的长度和最小重复子串之间的关系
如果字符串的长度 - 最长相等前后缀长度可以整除字符串长度，则说明可以构成

主要理解最长相等前后缀的子串，与最小重复子串之间的关系

class Solution{
	public boolean repeatedSubstringPattern(String s){
		int[] next = getNext(s);
		if (next[s.length() - 1] != -1 && s.length() % (s.length() - (next[s.length() - 1] + 1)) == 0) return true;
		return false;
	}
	
	private int[] getNext(String s){
		int j = -1; 
		int[] next = new int[s.length()];
		
		for (int i = 1; i < s.length(); i++){
			while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
				j = next[j];
			}
			
			if (s.charAt(i) == s.charAt(j+1)){
				j++;
			}
			
			next[i] = j;
		}
		
		return next;
	}
}

双指针复习

27. 移除元素

讨论需不需要判断右边的元素

1. 判断右边的元素

   class Solution{
   	public int removeElement(int[] nums, int val){
   		int left = 0; 
   		int right = nums.length - 1;
   		while (right >= 0 && nums[right] == val) right--;
   		while (left <= right){
   			if (nums[left] == val) {
   				nums[left] = nums[right--];
   			}
   			left++;
   			while (right >= 0 && nums[right] == val) right--;
   		}
   		
   		return left;
   	}
   }

2. 不判断右边的元素

   class Solution{
   	public int removeElement(int[] nums, int val){
   		int left = 0; 
   		int right = nums.length - 1;
   		
   		while (left <= right){
   			if (nums[left] == val){
   				nums[left] = nums[right--];
   			} else{
   				left++;
   			}
   		}
   		
   		return left;
   	}
   	
   }

3. 快慢指针

   class Solution{
   	public int removeElement(int[] nums, int val){
   		int slowIndex = 0;
   		for (int fastIndex = 0; fastIndex < nums.length; fastIndex++){
   			if (nums[fastIndex] != val){
   				nums[slowIndex++] = nums[fastIndex];
   			}
   		}
   		return slowIndex;
   	}
   }

344 反转字符串

头尾指针，然后同时缩进
in-place swap的用法

class Solution{
	public void reverseString(char[] s){
		int left = 0, right = s.length - 1;
		while (left < right) swapInArray(s, left++, right--);
	}
	
	private void swapInArray(char[] s, int m, int n){
		s[m] ^= s[n];
		s[n] ^= s[m];
		s[m] ^= s[n];
	}
}

替换数字

java解法不需要双指针
C++解法需要inplace扩充数组大小，在尾部需要指针，实时扩充array大小

import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		String s = sc.nextLine();
		
		for (int i = 0; i < s.length(); i++){
			if (Character.isDigit(s.charAt(i))){
				sb.append("number");
			} else {
				sb.append(s.charAt(i));
			}
		}
		
		System.out.println(sb);
	}
}

151 翻转字符串里的单词

先去掉多余空格
再完全反转字符串，再通过双指针，确定每个单词的位置进行翻转

class Solution {
    public String reverseWords(String s) {
        char[] str = removeExtraSpaces(s);
        reverseList(str, 0, str.length - 1);

        int left = 0, right = 0;
        while (left < str.length){
            while(right < str.length && str[right] != ' ') right++;
            reverseList(str, left, right - 1);
            
            right++;
            left = right;
        }

        return new String(str);

    }

    private char[] removeExtraSpaces(String s){
        char[] str = s.toCharArray();
        int left = 0, right = str.length - 1;
        while(left < str.length && str[left] == ' ') left++;
        while(right >= 0 && str[right] == ' ') right--;
        StringBuilder sb = new StringBuilder();
        while (left <= right){
            if (str[left] != ' ' || sb.charAt(sb.length() - 1) != ' '){
                sb.append(str[left]);
            }

            left++;
        }

        return sb.toString().toCharArray();
    }
    private void reverseList(char[] s, int m, int n){
        int left = m, right = n;
        while (left < right) swapInArray(s, left++, right--);
    }
    private void swapInArray(char[] s, int m, int n){
        s[m] ^= s[n];
        s[n] ^= s[m];
        s[m] ^= s[n];
    }
}

206 反转链表

从前往后递归

class Solution{
	public ListNode reverseList(ListNode head){
		return reverse(null, head);
	}
	
	private ListNode reverse(ListNode prev, ListNode cur){
		if (cur == null) return prev;
		
		ListNode temp = cur.next;
		cur.next = prev;
		
		return reverse(cur, temp);
	}
}

从后往前递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        if (head != null && head.next == null) return head;

        ListNode last = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return last;
        
    }
}

简单的双指针
把cur指针的node一个一个连接到prev上面

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return head;

        ListNode prev = null;

        ListNode cur = head;

        while (cur != null){
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }

        return prev;
        
    }
}

19 删除链表的倒数第N个节点

快慢指针找倒数N个节点

快指针先走N步
慢指针再和快指针一起走到快指针到底
慢指针的node就是N个节点

删除N个节点

class Solution{
	public ListNode removeNthFromEnd(ListNode head, int n){
		ListNode dummy = new ListNode(0, head);
		
		ListNode slowIndex = dummy;
		ListNode fastIndex = dummy;
		
		for (int i = 0; i <= n; i++) fastIndex = fastIndex.next;

		while(fastIndex != null){
			fastIndex = fastIndex.next;
			slowIndex = slowIndex.next;
		}
		
		slowIndex.next = slowIndex.next.next;
		
		return dummy.next;
	}
}

160 链表相交

找到两个链表的长度，然后把长的指针移到和短的指针一样的长度，之后比较每一个node

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0;
        int sizeB = 0;
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != null){
            curA = curA.next;
            sizeA++;
        }
        
        while (curB != null){
            curB = curB.next;
            sizeB++;
        }

        if (sizeA < sizeB){
            ListNode temp = headA;
            headA = headB;
            headB = temp;

            sizeA ^= sizeB;
            sizeB ^= sizeA;
            sizeA ^= sizeB;
        }

        curA = headA;
        curB = headB;

        for(int i = 0; i < sizeA - sizeB; i++){
            curA = curA.next;
        }

        while (curA != null){
            if (curA == curB){
                return curA;
            } else {
                curA = curA.next;
                curB = curB.next;
            }
        }
        return null;
    }
}

142 环形链表II

快慢指针找环，一个走两步一个走一步，相交即为有环
之后从头和相交点同时出发，相交点即为环入口

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slowIndex = head;
        ListNode fastIndex = head;

        while (fastIndex != null && fastIndex.next != null){
            fastIndex = fastIndex.next.next;
            slowIndex = slowIndex.next;
            if (fastIndex == slowIndex){
                ListNode index1 = slowIndex;
                ListNode index2 = head;

                while (index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }

                return index1;
            }
        }

        return null;


    }
}

15 三数之和

在i不变的情况下，双指针滑动找3数之和，还有需要去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> sums = new ArrayList<>();

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++){
            if (nums[i] > 0){
                return sums;
            }

            if (i > 0 && nums[i] == nums[i-1]) continue;

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];

                if (sum > 0){
                    right--;
                } else if (sum < 0){
                    left++;
                } else {
                    sums.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    right--;
                    left++;
                }
            }

        }

        return sums;
        
    }
}

18 四数之和

在三数之和的基础上再嵌套一层for loop

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            if (nums[i] > 0 && nums[i] > target){
                return result;
            }
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < nums.length; j++){
                if (j > i+1 && nums[j] == nums[j-1]) continue;

                int left = j + 1;
                int right = nums.length - 1;

                while (right > left){
                    int sum = nums[left] + nums[right] + nums[i] + nums[j];
                    if (sum > target){
                        right--;
                    } else if (sum < target){
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i],nums[j], nums[left],nums[right]));
                        while(right > left && nums[left] == nums[left+1]) left++;
                        while (right > left && nums[right] == nums[right - 1]) right--;

                        left++;
                        right--;
                    }
                }
            }
        }

        return result;
        
    }
}