28 实现strStr() https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
KMP经典题目
前缀表也就是next数组
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
前缀表要求的就是相同前后缀的长度
如何计算前缀表
模式串和前缀表对应位置的数字表示的就是下标i前包括i的字符串中，有多大长度的相同前缀后缀
前缀表就是next数组，实现方式有两种，一种是前缀表，另一种是前缀表统一减一（右移一位，初始位置是-1）
使用next数组进行匹配，匹配过程见gif图
具体解法：
滑动窗口，简单的双指针
一个指针指长string开头，一个指针指匹配string开头
注意在对比两个string的时候，需要判断index的大小和string的长度
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 class Solution { public int strStr (String haystack, String needle) { int m = haystack.length(); int n = needle.length(); if (m < n){ return -1 ; } int i = 0 ; int j = 0 ; while (i < m - n + 1 ){ while (i < m && haystack.charAt(i) != needle.charAt(j)) i++; if (i == m){ return -1 ; } while (i < m && j < n && haystack.charAt(i) == needle.charAt(j)){ i++; j++; } if (j == n){ return i - j; } else { i = i - j + 1 ; j = 0 ; } } return -1 ; } }
KMP算法，前缀减一法实现
定义getNext函数构建next数组（计算模式串s，前缀表的过程）
初始化
处理前后缀不相同的情况
处理前后缀相同的情况
得到next数组之后，进行匹配
如果不相同，j从next数组中找下一个匹配的位置
相同，i和j同时向后移动
具体实现
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 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数组，找到最长相等前后缀不包含的子串
主要理解最长相等前后缀的子串，与最小重复子串之间的关系
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 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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; } }
不判断右边的元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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; } }
快慢指针
1 2 3 4 5 6 7 8 9 10 11 12 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 反转字符串 头尾指针，然后同时缩进
1 2 3 4 5 6 7 8 9 10 11 12 13 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解法不需要双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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 翻转字符串里的单词 先去掉多余空格
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 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 反转链表 从前往后递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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); } }
从后往前递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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; } }
简单的双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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步
删除N个节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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
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 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 快慢指针找环，一个走两步一个走一步，相交即为有环
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 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数之和，还有需要去重
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 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
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 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; } }
