代码随想录学习记录 数组 双指针思想
二分查找 这道题目的前提是数组为有序数组 ,同时题目还强调数组中无重复元素 ,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。
704. 二分查找
704. 二分查找 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int search (int [] nums, int target) { int left = 0 , right = nums.length - 1 ; while (left <= right) { int mid = left + ((right - left) >> 1 ); if (nums[mid] < target) { left = mid + 1 ; } else if (nums[mid] > target) { right = mid - 1 ; } else { return mid; } } return -1 ; } }
35. 搜索插入位置
35. 搜索插入位置 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int searchInsert (int [] nums, int target) { int left = 0 , right = nums.length - 1 ; while (left <= right) { int mid = left + ((right - left) >> 1 ); if (nums[mid] < target) { left = mid + 1 ; } else if (nums[mid] > target) { right = mid - 1 ; } else { return mid; } } return left; } }
34. 在排序数组中查找元素的第一个和最后一个位置
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 class Solution { public int [] searchRange(int [] nums, int target) { int left = 0 , right = nums.length - 1 ; while (left <= right) { int mid = left + ((right - left) >> 1 ); if (nums[mid] < target) { left = mid + 1 ; } else if (nums[mid] > target) { right = mid - 1 ; } else { if (nums[left] != nums[mid]) { left++; } else if (nums[right] != nums[mid]) { right--; } else { return new int [] { left, right }; } } } return new int [] { -1 , -1 }; } }
**69. x 的平方根 **
69. x 的平方根 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int mySqrt (int x) { int left = 0 , right = x, result = -1 ; while (left <= right) { int mid = left + ((right - left) >> 1 ); long square = (long ) mid * mid; if (square < x) { left = mid + 1 ; } else if (square > x) { right = mid - 1 ; } else { return mid; } } return right; } }
367. 有效的完全平方数
367. 有效的完全平方数 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public boolean isPerfectSquare (int num) { int left = 0 , right = num; while (left <= right) { int mid = left + ((right - left) >> 1 ); if ((long ) mid * mid < num) { left = mid + 1 ; } else if ((long ) mid * mid > num) { right = mid - 1 ; } else { return true ; } } return false ; } }
双指针
27. 移除元素
27. 移除元素 - 力扣(LeetCode)
双指针解决,快慢指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int removeElement (int [] nums, int val) { int count = 0 ; int index = 0 ; int i = 0 ; while (i <= nums.length - 1 ) { if (nums[i] == val) { i++; } else { nums[index++] = nums[i++]; count++; } } return count; } }
26. 删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int removeDuplicates (int [] nums) { if (nums.length==0 ){ return 0 ; } int count = 1 ; int lastDifferent = nums[0 ]; int slow = 1 ; for (int fast = 1 ;fast<nums.length;fast++){ if (nums[fast]!=lastDifferent){ lastDifferent = nums[fast]; nums[slow++] = nums[fast]; count++; } } return count; } }
283. 移动零
283. 移动零 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public void moveZeroes (int [] nums) { int slow = 0 ; for (int fast = 0 ; fast < nums.length; fast++) { if (nums[fast] != 0 ) { nums[slow++] = nums[fast]; } } while (slow <= nums.length - 1 ) { nums[slow++] = 0 ; } } }
844. 比较含退格的字符串
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 class Solution { public boolean backspaceCompare (String s, String t) { int i = s.length() - 1 , j = t.length() - 1 ; int skipS = 0 , skipT = 0 ; while (i >= 0 || j >= 0 ) { while (i >= 0 ) { if (s.charAt(i) == '#' ) { skipS++; i--; } else if (skipS > 0 ) { skipS--; i--; } else { break ; } } while (j >= 0 ) { if (t.charAt(j) == '#' ) { skipT++; j--; } else if (skipT > 0 ) { skipT--; j--; } else { break ; } } if (i >= 0 && j >= 0 ) { if (s.charAt(i) != t.charAt(j)) { return false ; } } else { if (i >= 0 || j >= 0 ) { return false ; } } i--; j--; } return true ; } }
977. 有序数组的平方
977. 有序数组的平方 - 力扣(LeetCode)
还可以就是先全部平方,然后一个sort搞定,就是原地操作了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int [] sortedSquares(int [] nums) { int left = 0 , right = nums.length - 1 ; int [] result = new int [nums.length]; int i = result.length - 1 ; while (left <= right) { if (nums[left] * nums[left] < nums[right] * nums[right]) { result[i--] = nums[right] * nums[right]; right--; } else { result[i--] = nums[left] * nums[left]; left++; } } return result; } }
滑动窗口
209. 长度最小的子数组
209. 长度最小的子数组 - 力扣(LeetCode)
在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢。
首先要思考 如果用一个for循环,那么应该表示 滑动窗口的起始位置,还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置,那么如何遍历剩下的终止位置?
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动:如果当前窗口的值大于等于s了,窗口就要向前移动了(也就是该缩小了)。
窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int minSubArrayLen (int target, int [] nums) { int result = Integer.MAX_VALUE; int sum = 0 ; int left = 0 ; for (int right = 0 ;right<nums.length;right++){ sum+=nums[right]; while (sum>=target){ result = Math.min(result,right-left+1 ); sum-=nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; } }
904. 水果成篮
904. 水果成篮 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int totalFruit (int [] fruits) { int result = 0 ; int left = 0 ; HashMap<Integer, Integer> map = new HashMap <>(); for (int right = 0 ; right < fruits.length; right++) { map.put(fruits[right], map.getOrDefault(fruits[right], 0 ) + 1 ); while (map.size() > 2 ) { map.put(fruits[left], map.get(fruits[left]) - 1 ); if (map.get(fruits[left]) == 0 ) { map.remove(fruits[left]); } ++left; } result = Math.max(result, right - left + 1 ); } return result; } }
76. 最小覆盖子串
76. 最小覆盖子串 - 力扣(LeetCode)
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 class Solution { HashMap<Character, Integer> map1 = new HashMap <>(); HashMap<Character, Integer> map2 = new HashMap <>(); public String minWindow (String s, String t) { for (int i = 0 ; i < t.length(); i++) { map1.put(t.charAt(i), map1.getOrDefault(t.charAt(i), 0 ) + 1 ); } int left = 0 ; int len = Integer.MAX_VALUE, l = -1 , r = -1 ; for (int right = 0 ; right < s.length(); right++) { if (map1.containsKey(s.charAt(right))) { map2.put(s.charAt(right), map2.getOrDefault(s.charAt(right), 0 ) + 1 ); } while (check() && left <= right) { if (right - left + 1 < len) { len = right - left + 1 ; l = left; r = right; } if (map1.containsKey(s.charAt(left))) { map2.put(s.charAt(left), map2.getOrDefault(s.charAt(left), 0 ) - 1 ); } left++; } } return l == -1 ? "" : s.substring(l, r + 1 ); } public boolean check () { for (Map.Entry<Character, Integer> entry : map1.entrySet()) { if (map2.getOrDefault(entry.getKey(), 0 ) < entry.getValue()) { return false ; } } return true ; } }
模拟 螺旋
59. 螺旋矩阵 II
59. 螺旋矩阵 II - 力扣(LeetCode)
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 class Solution { public int [][] generateMatrix(int n) { int [][] result = new int [n][n]; int top = 0 , bottom = n - 1 , left = 0 , right = n - 1 ; int i = 0 , j = 0 , temp = 1 ; while (top <= bottom && left <= right) { for (int k = left; k <= right; k++) { result[top][k] = temp++; } top++; for (int k = top; k <= bottom; k++) { result[k][right] = temp++; } right--; for (int k = right; k >= left; k--) { result[bottom][k] = temp++; } bottom--; for (int k = bottom; k >= top; k--) { result[k][left] = temp++; } left++; } return result; } }
54. 螺旋矩阵
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 List<Integer> spiralOrder (int [][] matrix) { int row = matrix.length; if (row == 0 ) { return new ArrayList <Integer>(); } int column = matrix[0 ].length; List<Integer> result = new ArrayList <>(); int top = 0 , bottom = row - 1 , left = 0 , right = column - 1 ; while (top <= bottom && left <= right) { for (int k = left; k <= right; k++) { result.add(matrix[top][k]); } top++; for (int k = top; k <= bottom; k++) { result.add(matrix[k][right]); } right--; if (top <= bottom) { for (int k = right; k >= left; k--) { result.add(matrix[bottom][k]); } bottom--; } if (left <= right) { for (int k = bottom; k >= top; k--) { result.add(matrix[k][left]); } left++; } } return result; } }
LCR 146. 螺旋遍历二维数组
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 [] spiralArray(int [][] array) { int row = array.length; if (row == 0 ) { return new int [0 ]; } int column = array[0 ].length; int [] result = new int [row * column]; int top = 0 , bottom = row - 1 , left = 0 , right = column - 1 ; int temp = 0 ; while (top <= bottom && left <= right) { for (int k = left; k <= right; k++) { result[temp++] = array[top][k]; } top++; for (int k = top; k <= bottom; k++) { result[temp++] = array[k][right]; } right--; if (top <= bottom) { for (int k = right; k >= left; k--) { result[temp++] = array[bottom][k]; } bottom--; } if (left <= right) { for (int k = bottom; k >= top; k--) { result[temp++] = array[k][left]; } left++; } } return result; } }
前缀和 区间和
第一行输入为整数数组 Array 的长度 n,接下来 n 行,每行一个整数,表示数组的元素。随后的输入为需要计算总和的区间下标:a,b (b > = a),直至文件结束。
如果,我们想统计,在vec数组上 下标 2 到下标 5 之间的累加和,那是不是就用 p[5] - p[1] 就可以了。
为什么呢?
p[1] = vec[0] + vec[1]; p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5]; p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];
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 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); int [] vec = new int [n]; int [] p = new int [n]; int presum = 0 ; for (int i = 0 ; i < n; i++) { vec[i] = scanner.nextInt(); presum += vec[i]; p[i] = presum; } while (scanner.hasNextInt()) { int a = scanner.nextInt(); int b = scanner.nextInt(); int sum; if (a == 0 ) { sum = p[b]; } else { sum = p[b] - p[a - 1 ]; } System.out.println(sum); } scanner.close(); } }
开发商购买土地
在一个城市区域内,被划分成了n * m个连续的区块,每个区块都拥有不同的权值,代表着其土地价值。目前,有两家开发公司,A 公司和 B 公司,希望购买这个城市区域的土地。
现在,需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而,由于城市规划的限制,只允许将区域按横向或纵向划分成两个子区域,而且每个子区域都必须包含一个或多个区块。
为了确保公平竞争,你需要找到一种分配方式,使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意:区块不可再分。
【输入描述】
第一行输入两个正整数,代表 n 和 m。
接下来的 n 行,每行输出 m 个正整数。
输出描述
请输出一个整数,代表两个子区域内土地总价值之间的最小差距。
【输入示例】
3 3 1 2 3 2 1 3 1 2 3
【输出示例】
0
【提示信息】
如果将区域按照如下方式划分:
1 2 | 3 2 1 | 3 1 2 | 3
两个子区域内土地总价值之间的最小差距可以达到 0。
【数据范围】:
1 <= n, m <= 100;
n 和 m 不同时为 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 37 38 39 40 41 42 43 44 45 46 47 48 49 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int sum = 0 ; int [][] vec = new int [n][m]; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { vec[i][j] = scanner.nextInt(); sum += vec[i][j]; } } int [] horizontal = new int [n]; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { horizontal[i] += vec[i][j]; } } int [] vertical = new int [m]; for (int j = 0 ; j < m; j++) { for (int i = 0 ; i < n; i++) { vertical[j] += vec[i][j]; } } int result = Integer.MAX_VALUE; int horizontalCut = 0 ; for (int i = 0 ; i < n; i++) { horizontalCut += horizontal[i]; result = Math.min(result, Math.abs(sum - 2 * horizontalCut)); } int verticalCut = 0 ; for (int j = 0 ; j < m; j++) { verticalCut += vertical[j]; result = Math.min(result, Math.abs(sum - 2 * verticalCut)); } System.out.println(result); scanner.close(); } }
链表
链表的种类主要为:单链表,双链表,循环链表
链表的存储方式:链表的节点在内存中是分散存储的,通过指针连在一起。
链表是如何进行增删改查的。
数组和链表在不同场景下的性能分析。
虚拟头节点
203. 移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/
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 ListNode removeElements (ListNode head, int val) { ListNode result = null ; ListNode last = null ; while (head != null ) { if (head.val != val) { if (result == null ) { result = head; } if (last == null ) { last = head; } else { last.next = head; last = last.next; } } head = head.next; } if (last != null ) { last.next = null ; } return result; } }
看下面虚拟节点的
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 ListNode removeElements (ListNode head, int val) { ListNode newHead = new ListNode (); newHead.next = head; ListNode cur = newHead; while (cur.next != null ) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return newHead.next; } }
链表的基本操作
707. 设计链表
707. 设计链表 - 力扣(LeetCode)
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this .val = val; } } class MyLinkedList { private int size; private ListNode head; public MyLinkedList () { size = 0 ; head = new ListNode (); } public int get (int index) { if (index < 0 || index >= size) { return -1 ; } ListNode result = head; for (int i = 0 ; i <= index; i++) { result = result.next; } return result.val; } public void addAtHead (int val) { ListNode newNode = new ListNode (val); ListNode next = head.next; head.next = newNode; newNode.next = next; size++; } public void addAtTail (int val) { ListNode temp = head; for (int i = 0 ; i < size; i++) { temp = temp.next; } temp.next = new ListNode (val); size++; } public void addAtIndex (int index, int val) { if (index < 0 || index > size) { return ; } ListNode temp = head; for (int i = 0 ; i <= index - 1 ; i++) { temp = temp.next; } ListNode next = temp.next; ListNode newNode = new ListNode (val); temp.next = newNode; newNode.next = next; size++; } public void deleteAtIndex (int index) { if (index < 0 || index >= size) { return ; } ListNode temp = head; for (int i = 0 ; i < index; i++) { temp = temp.next; } temp.next = temp.next.next; size--; } }
反转链表
206. 反转链表
206. 反转链表 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public ListNode reverseList (ListNode head) { ListNode last = null ; while (head != null ) { ListNode next = head.next; head.next = last; last = head; head = next; } return last; } }
两两交换链表中的节点
24. 两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣(LeetCode)
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 ListNode swapPairs (ListNode head) { ListNode newHead = new ListNode (-1 , head); ListNode temp = newHead; while (temp.next != null && temp.next.next != null ) { ListNode node1 = temp.next; ListNode node2 = temp.next.next; temp.next = node2; node1.next = node2.next; node2.next = node1; temp = node1; } return newHead.next; } }
删除链表的倒数第N个节点
19. 删除链表的倒数第 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 38 39 40 41 class Solution { public ListNode removeNthFromEnd (ListNode head, int n) { if (n < 1 || head == null ) { return head; } ListNode newHead = new ListNode (-1 , head); ListNode fast = newHead, slow = newHead; int i = 0 ; while (fast.next != null ) { if (i == n) { break ; } fast = fast.next; i++; } if (i != n) { return newHead.next; } while (fast.next != null ) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return newHead.next; } }
链表相交
面试题 02.07. 链表相交
面试题 02.07. 链表相交 - 力扣(LeetCode)
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 class Solution { public ListNode getIntersectionNode (ListNode headA, ListNode headB) { if (headA == null || headB == null ) { return null ; } ListNode A = headA, B = headB; while (A != B) { A = A == null ? headB : A.next; B = B == null ? headA : B.next; } return A; } }
环形链表II
142. 环形链表 II
[142. 环形链表 II - 力扣(LeetCode)
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 public class Solution { public ListNode detectCycle (ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; if (slow == fast) { ListNode node1 = head, node2 = slow; while (node1 != node2) { node1 = node1.next; node2 = node2.next; } return node1; } } return null ; } }
哈希表 一般来说哈希表都是用来快速判断一个元素是否出现集合里 。
对于哈希表,要知道哈希函数 和哈希碰撞 在哈希表中的作用。
哈希函数是把传入的key映射到符号表的索引上。
哈希碰撞处理有多个key映射到相同索引上时的情景,处理碰撞的普遍方式是拉链法和线性探测法。
接下来是常见的三种哈希结构:
当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法 。
但是哈希法也是牺牲了空间换取了时间 ,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法!
数组作为哈希表
242. 有效的字母异位词
242. 有效的字母异位词 - 力扣(LeetCode)
时间复杂度和空间复杂度太高,看下面方法,感觉被局限住了
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 isAnagram (String s, String t) { HashMap<Character, Integer> map = new HashMap <>(); for (int i = 0 ; i < s.length(); i++) { map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0 ) + 1 ); } for (int i = 0 ; i < t.length(); i++) { if (map.getOrDefault(t.charAt(i), 0 ) == 0 ) { return false ; } else { map.put(t.charAt(i), map.get(t.charAt(i)) - 1 ); if (map.get(t.charAt(i)) == 0 ) { map.remove(t.charAt(i)); } } } if (map.keySet().size() != 0 ) { return false ; } return true ; } }
看下面
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 isAnagram (String s, String t) { if (s.length() != t.length()) { return false ; } int [] temp = new int [26 ]; for (int i = 0 ; i < s.length(); i++) { temp[s.charAt(i) - 'a' ]++; } for (int i = 0 ; i < t.length(); i++) { temp[t.charAt(i) - 'a' ]--; } for (int i = 0 ; i < temp.length; i++) { if (temp[i] != 0 ) { return false ; } } return true ; } }
383. 赎金信
383. 赎金信
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public boolean canConstruct (String ransomNote, String magazine) { int [] hash = new int [26 ]; for (char c : magazine.toCharArray()) { hash[c - 'a' ] += 1 ; } for (char c : ransomNote.toCharArray()) { hash[c - 'a' ] -= 1 ; } for (int i : hash) { if (i < 0 ) { return false ; } } return true ; } }
当然可以HashMap解决,但是这里单用字符的26个的特性解决更好,不然HashMap维护红黑树很花时间并且占用内存更多
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public boolean canConstruct (String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) { return false ; } HashMap<Character, Integer> map = new HashMap <>(); for (int i = 0 ; i < magazine.length(); i++) { map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0 ) + 1 ); } for (int i = 0 ; i < ransomNote.length(); i++) { int count = map.getOrDefault(ransomNote.charAt(i), 0 ); if (count > 0 ) { map.put(ransomNote.charAt(i), count - 1 ); } else { return false ; } } return true ; } }
Set作为哈希表
349. 两个数组的交集
349. 两个数组的交集 - 力扣(LeetCode)
下面感觉是根据数据长度跟上面的字母一样可以取巧
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 class Solution { public int [] intersection(int [] nums1, int [] nums2) { int [] hash1 = new int [1001 ]; int [] hash2 = new int [1001 ]; for (int i = 0 ; i < nums1.length; i++) { hash1[nums1[i]]++; } for (int i = 0 ; i < nums2.length; i++) { hash2[nums2[i]]++; } int size = 0 ; for (int i = 0 ; i < hash1.length; i++) { int count = hash1[i] > hash2[i] ? hash2[i] : hash1[i]; if (count != 0 ) { size++; } } int [] result = new int [size]; int k = 0 ; for (int i = 0 ; i < hash1.length; i++) { int count = hash1[i] > hash2[i] ? hash2[i] : hash1[i]; if (count != 0 ) { result[k++] = i; } } return result; } }
HashSet解决
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int [] intersection(int [] nums1, int [] nums2) { if (nums1.length == 0 || nums2.length == 0 ) { return new int [0 ]; } Set<Integer> set = new HashSet <>(); Set<Integer> set2 = new HashSet <>(); for (int i = 0 ; i < nums1.length; i++) { set.add(nums1[i]); } for (int i = 0 ; i < nums2.length; i++) { if (set.contains(nums2[i])) { set2.add(nums2[i]); } } int [] result = new int [set2.size()]; int t = 0 ; for (int i : set2) { result[t++] = i; } return result; } }
Map作为哈希表
1. 两数之和
1. 两数之和 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int [] twoSum(int [] nums, int target) { HashMap<Integer, Integer> map = new HashMap <>(); for (int i = 0 ; i < nums.length; i++) { int temp = target - nums[i]; if (map.containsKey(temp)) { return new int [] { i, map.get(temp) }; } else { map.put(nums[i], i); } } return null ; } }
454. 四数相加 II
454. 四数相加 II - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int fourSumCount (int [] nums1, int [] nums2, int [] nums3, int [] nums4) { int count = 0 ; HashMap<Integer,Integer>map = new HashMap <>(); for (int i :nums1){ for (int j :nums2){ map.put(i+j,map.getOrDefault(i+j,0 )+1 ); } } for (int i :nums3){ for (int j :nums4){ count += map.getOrDefault(0 -i-j,0 ); } } return count; } }
双指针求多数和
15. 三数之和
两数之和 就不能使用双指针法,因为1.两数之和 (opens new window)要求返回的是索引下标, 而双指针法一定要排序,一旦排序之后原数组的索引就被改变了。如果1.两数之和 (opens new window)要求返回的是数值的话,就可以使用双指针法了。
15. 三数之和
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 List<List<Integer>> threeSum (int [] nums) { List<List<Integer>> result = new ArrayList <>(); Arrays.sort(nums); for (int i = 0 ; i < nums.length; i++) { if (nums[i] > 0 ) { break ; } if (i > 0 && nums[i] == nums[i - 1 ]) { continue ; } int right = nums.length - 1 ; int left = i + 1 ; while (left < right) { if (nums[left] + nums[right] + nums[i] < 0 ) { left++; } else if (nums[left] + nums[right] + nums[i] > 0 ) { right--; } else { result.add(Arrays.asList(nums[i], nums[left], nums[right])); left++; right--; while (left < right && nums[left] == nums[left - 1 ]) { left++; } while (left < right && nums[right] == nums[right + 1 ]) { right--; } } } } return result; } }
18. 四数之和
18. 四数之和
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 65 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) { break ; } if (i > 0 && nums[i] == nums[i - 1 ]) { continue ; } for (int j = i + 1 ; j < nums.length; j++) { if (nums[i] + nums[j] >= 0 && nums[i] + nums[j] > target) { break ; } if (j > i + 1 && nums[j] == nums[j - 1 ]) { continue ; } int left = j + 1 ; int right = nums.length - 1 ; while (left < right) { long sum = (long ) nums[i] + nums[j] + nums[left] + nums[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); left++; right--; while (left < right && nums[left] == nums[left - 1 ]) { left++; } while (left < right && nums[right] == nums[right + 1 ]) { right--; } } } } } return result; } }
字符串
344. 反转字符串
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){ char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } } }
541. 反转字符串 II
541. 反转字符串 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 class Solution { public String reverseStr (String s, int k) { char [] target = s.toCharArray(); int count = target.length / (2 * k); for (int i = 0 ; i < count; i++) { reverse(target, 2 * k * i, 2 * k * i + k - 1 ); } int balance = target.length % (2 * k); if (balance >= k) { reverse(target, target.length - balance, target.length - balance + k - 1 ); } else if (balance != 0 ) { reverse(target, target.length - balance, target.length - 1 ); } return new String (target); } public void reverse (char [] target, int left, int right) { while (left < right) { char c = target[left]; target[left] = target[right]; target[right] = c; left++; right--; } } }
151. 反转字符串中的单词
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 class Solution { public String reverseWords (String s) { String target = s.trim(); StringBuilder builder = new StringBuilder (); int right = target.length(), left = target.length() - 1 ; while (left >= 0 ) { if (left - 1 >= 0 && target.charAt(left - 1 ) != ' ' ) { left--; } else { builder.append(target.substring(left, right)); builder.append(" " ); left--; while (left >= 0 && target.charAt(left) == ' ' ) { left--; } right = left + 1 ; } } return builder.toString().trim(); } }
JZ58 左旋转字符串
左旋转字符串_牛客题霸_牛客网 (nowcoder.com)
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 import java.util.*;public class Solution { public String LeftRotateString (String str, int n) { if (str.isEmpty()){ return "" ; } int real = n % str.length(); char [] result = new char [str.length()]; int index = 0 ; for (int i = real;i<str.length();i++){ result[index++] = str.charAt(i); } for (int i = 0 ;i<real;i++){ result[index++] = str.charAt(i); } return new String (result); } }
28. 找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标
简单实现,看下面高级的KMP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int strStr (String haystack, String needle) { int length1 = haystack.length(), length2 = needle.length(); int left = 0 ; while (length1 - left >= length2) { if (haystack.substring(left, left + length2).equals(needle)) { return left; } left++; } 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 class Solution { public int strStr (String haystack, String needle) { int [] next = new int [needle.length()]; getNext(next, needle); int j = 0 ; 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 == needle.length()) { return i - needle.length() + 1 ; } } return -1 ; } public void getNext (int [] next, String str) { int j = 0 ; next[0 ] = 0 ; for (int i = 1 ; i < str.length(); i++) { while (j > 0 && str.charAt(i) != str.charAt(j)) { j = next[j - 1 ]; } if (str.charAt(i) == str.charAt(j)) { j++; } next[i] = j; } } }
459. 重复的子字符串
459. 重复的子字符串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public boolean repeatedSubstringPattern (String s) { int j = 0 ; int [] next = new int [s.length()]; for (int i = 1 ;i<s.length();i++){ while (j>0 &&s.charAt(i)!=s.charAt(j)){ j = next[j-1 ]; } if (s.charAt(i)==s.charAt(j)){ j++; } next[i] = j; } if (next[s.length()-1 ]>0 &&s.length()%(s.length()-next[s.length()-1 ])==0 ){ return true ; } return false ; } }
KMP算法 解决字符串匹配的问题
文本串 是原本的字符串,模式串 是否在文本串中出现过
帮你把KMP算法学个通透!(理论篇)_哔哩哔哩_bilibili
帮你把KMP算法学个通透!(求next数组代码篇)_哔哩哔哩_bilibili
前缀:一个字符串包含首字母但不包含尾字母之间的字符串的所有子序列
后缀: 一个字符串包含尾字母但不包含首字母之间的字符串的所有子序列
这里要求最长相等的前缀的后缀的长度 (网上很多用的是求公共前后缀),这个最后求出来就是前缀表
如何使用前缀表进行匹配?
出现了一个位置不匹配了,那这时候可以看前面字符串的最长相等前后缀的长度,这个长度就是继续匹配的下标
某些代码用的next数组或者prefix数组,其实就是前缀表,但是next数组可能是经过一些调整的,如右移或者统一减一,这个是涉及到KMP算法的具体实现的过程的,就算用原封不动的前缀表作为next数组也可以完成我们的操作
具体算法的实现
初始化next数组和函数各个变量
i指向后缀的末尾位置,j指向前缀的末尾位置,j初始化为0,next[0]=0,0下标自然回退到0开始比较,那i呢?i的话是在遍历中进行的,一开始要从1开始才能比较,从0开始就重叠了,没有前后缀了,不满足i和j的定义
处理前后缀不相同的情况
处理前后缀相同的情况
更新next数组的值
栈和队列 Java精讲 | 45张图庖丁解牛18种Queue,你知道几种?-腾讯云开发者社区-腾讯云 (tencent.com)
Stack详解(Java实现方式)_java stack-CSDN博客
互相模拟
232. 用栈实现队列
232. 用栈实现队列
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 MyQueue { Stack<Integer> stack1 = new Stack <>(); Stack<Integer> stack2 = new Stack <>(); public MyQueue () { } public void push (int x) { while (!stack2.isEmpty()) { stack1.push(stack2.pop()); } stack1.push(x); while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } public int pop () { if (stack2.isEmpty()) { return -1 ; } return stack2.pop(); } public int peek () { if (stack2.isEmpty()) { return -1 ; } return stack2.peek(); } public boolean empty () { return stack2.isEmpty(); } }
225. 用队列实现栈
225. 用队列实现栈
注意top的部分,在while里面移动完再判断size是否等于1赋值有问题的,长度刚好为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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 class MyStack { Queue<Integer> queue1 = new ArrayDeque <>(); Queue<Integer> queue2 = new ArrayDeque <>(); public MyStack () { } public void push (int x) { queue1.offer(x); } public int pop () { if (queue1.size() < 1 ) { return -1 ; } while (queue1.size() > 1 ) { queue2.offer(queue1.poll()); } while (!queue2.isEmpty()) { queue1.offer(queue2.poll()); } return queue1.poll(); } public int top () { if (queue1.size() < 1 ) { return -1 ; } while (queue1.size() > 1 ) { queue2.offer(queue1.poll()); } int result = queue1.peek(); queue2.offer(queue1.poll()); while (!queue2.isEmpty()) { queue1.offer(queue2.poll()); } return result; } public boolean empty () { return queue1.isEmpty(); } }
栈使用
20. 有效的括号
20. 有效的括号
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public boolean isValid (String s) { Stack<Character> stack = new Stack <>(); for (int i = 0 ; i < s.length(); i++) { char c = s.charAt(i); if (c == '(' || c == '[' || c == '{' ) { stack.push(c); } else { if (stack.isEmpty()) { return false ; } char temp = stack.pop(); if (!((c == ')' && temp == '(' ) || (c == ']' && temp == '[' ) || (c == '}' && temp == '{' ))) { return false ; } } } if (stack.isEmpty()) { return true ; } return false ; } }
1047. 删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public String removeDuplicates (String s) { Stack<Character> stack = new Stack <>(); for (int i = 0 ; i < s.length(); i++) { char c = s.charAt(i); if (stack.isEmpty() || stack.peek() != c) { stack.push(c); } else { stack.pop(); } } char [] result = new char [stack.size()]; int i = result.length - 1 ; while (!stack.isEmpty()) { result[i--] = stack.pop(); } return new String (result); } }
拿字符串直接作为栈,省去了栈还要转为字符串的操作。另外思路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public String removeDuplicates (String s) { StringBuffer res = new StringBuffer (); int top = -1 ; for (int i = 0 ; i < s.length(); i++) { char c = s.charAt(i); if (top >= 0 && res.charAt(top) == c) { res.deleteCharAt(top); top--; } else { res.append(c); top++; } } return res.toString(); } }
150. 逆波兰表达式求值
150. 逆波兰表达式求值
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 class Solution { public int evalRPN (String[] tokens) { Stack<Integer> stack = new Stack <>(); for (int i = 0 ; i < tokens.length; i++) { String temp = tokens[i]; if (temp.equals("+" ) || temp.equals("-" ) || temp.equals("*" ) || temp.equals("/" )) { int second = stack.pop(); int first = stack.pop(); if (temp.equals("+" )) { stack.push(first + second); } else if (temp.equals("-" )) { stack.push(first - second); } else if (temp.equals("*" )) { stack.push(first * second); } else if (temp.equals("/" )) { stack.push(first / second); } } else { stack.push(Integer.valueOf(temp)); } } return stack.pop(); } }
代码随想录给的用Deque,双向队列来的,既可以做队列也可做栈使用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int evalRPN (String[] tokens) { Deque<Integer> stack = new LinkedList (); for (String s : tokens) { if ("+" .equals(s)) { stack.push(stack.pop() + stack.pop()); } else if ("-" .equals(s)) { stack.push(-stack.pop() + stack.pop()); } else if ("*" .equals(s)) { stack.push(stack.pop() * stack.pop()); } else if ("/" .equals(s)) { int temp1 = stack.pop(); int temp2 = stack.pop(); stack.push(temp2 / temp1); } else { stack.push(Integer.valueOf(s)); } } return stack.pop(); } }
单调栈 通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了 。时间复杂度为O(n)。
单调栈的本质是空间换时间 ,因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素,优点是整个数组只需要遍历一次。
更直白来说,就是用一个栈来记录我们遍历过的元素 ,因为我们遍历数组的时候,我们不知道之前都遍历了哪些元素,以至于遍历一个元素找不到是不是之前遍历过一个更小的,所以我们需要用一个容器(这里用单调栈)来记录我们遍历过的元素。
在使用单调栈的时候首先要明确如下几点:
单调栈里存放的元素是什么?
单调栈里只需要存放元素的下标i就可以了,如果需要使用对应的元素,直接T[i]就可以获取。
单调栈里元素是递增呢? 还是递减呢?
注意使用的是栈,是先进后出的,别懵逼了,后面没睡醒一样,当成队列一直觉得有问题,笑死
739. 每日温度
739. 每日温度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int [] dailyTemperatures(int [] temperatures) { int [] result = new int [temperatures.length]; Deque<Integer> stack = new LinkedList <>(); for (int i = 0 ; i < temperatures.length; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { result[stack.peek()] = i - stack.peek(); stack.pop(); } stack.push(i); } return result; } }
496. 下一个更大元素 I
496. 下一个更大元素 I
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 class Solution { public int [] nextGreaterElement(int [] nums1, int [] nums2) { int [] result = new int [nums1.length]; Arrays.fill(result, -1 ); HashMap<Integer, Integer> map = new HashMap <>(); for (int i = 0 ; i < nums1.length; i++) { map.put(nums1[i], i); } Stack<Integer> stack = new Stack <>(); for (int i = 0 ; i < nums2.length; i++) { while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) { int temp = nums2[stack.pop()]; if (map.containsKey(temp)) { result[map.get(temp)] = nums2[i]; } } stack.push(i); } return result; } }
503. 下一个更大元素 II
503. 下一个更大元素 II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int [] nextGreaterElements(int [] nums) { int [] result = new int [nums.length]; Arrays.fill(result,-1 ); Stack<Integer>stak = new Stack <>(); for (int i = 0 ;i<2 *nums.length;i++){ while (!stak.isEmpty()&&nums[i%nums.length]>nums[stak.peek()]){ int temp = stak.pop(); result[temp] = nums[i%nums.length]; } stak.push(i%nums.length); } return result; } }
42. 接雨水
42. 接雨水
这题可以双指针解决的,这个是双指针优化版本,还可以遍历两边,分别把从左往右走的左边柱子最大值记录下俩,从右往左走的最大值记录下来,之后再遍历求和即可,如下
1 2 int count = Math.min(maxLeft[i], maxRight[i]) - height[i];if (count > 0 ) sum += count;
双指针优化
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 class Solution { public int trap (int [] height) { if (height.length <= 2 ) { return 0 ; } int left = 1 , right = height.length - 2 ; int maxLeft = height[0 ], maxRight = height[height.length - 1 ]; int result = 0 ; while (left <= right) { maxLeft = Math.max(maxLeft, height[left]); maxRight = Math.max(maxRight, height[right]); if (maxLeft < maxRight) { result += maxLeft - height[left]; left++; } else { result += maxRight - height[right]; right--; } } return result; } }
单调栈(找每个柱子左右两边第一个大于该柱子高度的柱子)
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 class Solution { public int trap (int [] height) { if (height.length<=2 ){ return 0 ; } int result = 0 ; Stack<Integer>stack = new Stack <>(); for (int i = 0 ;i<height.length;i++){ while (!stack.isEmpty()&&height[i]>height[stack.peek()]){ int mid = stack.pop(); if (!stack.isEmpty()){ int left = stack.peek(); int h = Math.min(height[left],height[i]) - height[mid]; int w = i - left - 1 ; result += h * w; } } stack.push(i); } return result; } }
84. 柱状图中最大的矩形
84. 柱状图中最大的矩形
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int largestRectangleArea (int [] heights) { int [] nums = new int [heights.length + 2 ]; System.arraycopy(heights, 0 , nums, 1 , heights.length); int result = 0 ; Stack<Integer> stack = new Stack <>(); stack.push(0 ); for (int i = 1 ; i < nums.length; i++) { while (nums[i] < nums[stack.peek()]) { int mid = stack.pop(); int left = stack.peek(); int w = i - left - 1 ; result = Math.max(result, w * nums[mid]); } stack.push(i); } return result; } }
队列使用
239. 滑动窗口最大值
239. 滑动窗口最大值
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 class Solution { public int [] maxSlidingWindow(int [] nums, int k) { int [] result = new int [nums.length - k + 1 ]; Deque<Integer> queue = new ArrayDeque <>(); for (int i = 0 ; i < nums.length; i++) { while (!queue.isEmpty() && queue.peekFirst() < i - k + 1 ) { queue.pollFirst(); } while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) { queue.pollLast(); } queue.offerLast(i); if (i >= k - 1 ) { result[i - k + 1 ] = nums[queue.peekFirst()]; } } return result; } }
结合使用
347. 前 K 个高频元素
347. 前 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 26 27 28 29 30 31 32 class Solution { public int [] topKFrequent(int [] nums, int k) { HashMap<Integer, Integer> map = new HashMap <>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0 ) + 1 ); } PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue <>( (a, b) -> a.getValue() - b.getValue() ); for (Map.Entry<Integer, Integer> entry : map.entrySet()) { queue.offer(entry); if (queue.size() > k) { queue.poll(); } } int [] result = new int [k]; int i = 0 ; while (!queue.isEmpty()) { result[i++] = queue.poll().getKey(); } return result; } }
二叉树 种类直接去这里看吧
代码随想录 (programmercarl.com)
二叉树的遍历方式 递归 这里帮助大家确定下来递归算法的三个要素。每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!
确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144. 二叉树的前序遍历
144. 二叉树的前序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public List<Integer> preorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); preorder(root, result); return result; } public void preorder (TreeNode node, List<Integer> result) { if (node == null ) { return ; } result.add(node.val); preorder(node.left, result); preorder(node.right, result); } }
94. 二叉树的中序遍历
94. 二叉树的中序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public List<Integer> inorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); inorder(root, result); return result; } public void inorder (TreeNode root, List<Integer> result) { if (root == null ) { return ; } inorder(root.left, result); result.add(root.val); inorder(root.right, result); } }
145. 二叉树的后序遍历
145. 二叉树的后序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public List<Integer> postorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); postorder(root, result); return result; } public void postorder (TreeNode root, List<Integer> result) { if (root == null ) { return ; } postorder(root.left, result); postorder(root.right, result); result.add(root.val); } }
589. N 叉树的前序遍历
589. N 叉树的前序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { List<Integer>result = new ArrayList <>(); public List<Integer> preorder (Node root) { pre(root); return result; } public void pre (Node node) { if (node==null ){ return ; } result.add(node.val); if (node.children!=null &&!node.children.isEmpty()){ for (Node n:node.children){ pre(n); } } } }
590. N 叉树的后序遍历
590. N 叉树的后序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { List<Integer> result = new ArrayList <>(); public List<Integer> postorder (Node root) { post(root); return result; } public void post (Node node) { if (node == null ) { return ; } if (node.children != null && !node.children.isEmpty()) { for (Node n : node.children) { post(n); } } result.add(node.val); } }
迭代 我还是习惯这种不统一的思路,虽然老忘记,统一风格直接看代码随想录官网的吧,代码随想录 (programmercarl.com)
144. 二叉树的前序遍历
144. 二叉树的前序遍历
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 class Solution { public List<Integer> preorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); Stack<TreeNode> stack = new Stack <>(); if (root != null ) { stack.push(root); } while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.right != null ) { stack.push(node.right); } if (node.left != null ) { stack.push(node.left); } } return result; } }
94. 二叉树的中序遍历
94. 二叉树的中序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public List<Integer> inorderTraversal (TreeNode root) { List<Integer>result = new ArrayList <>(); Stack<TreeNode>stack = new Stack <>(); while (root!=null ||!stack.isEmpty()){ if (root!=null ){ stack.push(root); root = root.left; }else { root = stack.pop(); result.add(root.val); root = root.right; } } return result; } }
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 class Solution { public int getMinimumDifference (TreeNode root) { int min = Integer.MAX_VALUE; TreeNode last = null ; Stack<TreeNode> stack = new Stack <>(); while (root != null || !stack.isEmpty()) { if (root != null ) { stack.push(root); root = root.left; } else { root = stack.pop(); if (last != null ) { min = Math.min(min, root.val - last.val); } last = root; root = root.right; } } return min; } }
145. 二叉树的后序遍历
145. 二叉树的后序遍历
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 class Solution { public List<Integer> postorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); Stack<TreeNode> stack = new Stack <>(); TreeNode pre = null ; while (root != null || !stack.isEmpty()) { while (root != null ) { stack.push(root); root = root.left; } root = stack.peek(); if (root.right == null || root.right == pre) { result.add(root.val); stack.pop(); pre = root; root = null ; } else { root = root.right; } } return result; } }
另一种思路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public List<Integer> postorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ){ return result; } Stack<TreeNode> stack = new Stack <>(); stack.push(root); while (!stack.isEmpty()){ TreeNode node = stack.pop(); result.add(node.val); if (node.left != null ){ stack.push(node.left); } if (node.right != null ){ stack.push(node.right); } } Collections.reverse(result); return result; } }
层次遍历
102. 二叉树的层序遍历
102. 二叉树的层序遍历
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 class Solution { public List<List<Integer>> levelOrder (TreeNode root) { List<List<Integer>> result = new ArrayList <>(); Queue<TreeNode> queue = new LinkedList <>(); if (root != null ) { queue.offer(root); } while (!queue.isEmpty()) { int size = queue.size(); List<Integer>list = new ArrayList <>(); while (size != 0 ) { size--; root = queue.poll(); list.add(root.val); if (root.left != null ) { queue.offer(root.left); } if (root.right != null ) { queue.offer(root.right); } } result.add(list); } return result; } }
107. 二叉树的层序遍历 II
107. 二叉树的层序遍历 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 class Solution { public List<List<Integer>> levelOrderBottom (TreeNode root) { List<List<Integer>> result = new ArrayList <>(); Queue<TreeNode> queue = new LinkedList <>(); if (root != null ) { queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> list = new ArrayList <>(); while (size != 0 ) { size--; root = queue.poll(); list.add(root.val); if (root.left != null ) { queue.offer(root.left); } if (root.right != null ) { queue.offer(root.right); } } result.add(0 , list); } } return result; } }
199. 二叉树的右视图
199. 二叉树的右视图
题目的意思是花好二叉树后直接从右边往左边看看到最外围的节点,从上往下
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 class Solution { public List<Integer> rightSideView (TreeNode root) { List<Integer> result = new ArrayList <>(); Queue<TreeNode> queue = new LinkedList <>(); if (root != null ) { queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); while (size > 0 ) { root = queue.poll(); if (root.left != null ) { queue.offer(root.left); } if (root.right != null ) { queue.offer(root.right); } size--; } result.add(root.val); } } return result; } }
637. 二叉树的层平均值
637. 二叉树的层平均值
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 class Solution { public List<Double> averageOfLevels (TreeNode root) { List<Double> result = new ArrayList <>(); Queue<TreeNode> queue = new LinkedList <>(); if (root != null ) { queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); int temp = size; double sum = 0.0 ; while (size > 0 ) { root = queue.poll(); sum += root.val; if (root.left != null ) { queue.offer(root.left); } if (root.right != null ) { queue.offer(root.right); } size--; } result.add(sum / temp); } } return result; } }
429. N 叉树的层序遍历
429. 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 38 39 40 41 42 43 44 45 class Solution { public List<List<Integer>> levelOrder (Node root) { List<List<Integer>> result = new ArrayList <>(); if (root != null ) { Queue<Node> queue = new LinkedList <>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> list = new ArrayList <>(); while (size != 0 ) { Node node = queue.poll(); list.add(node.val); if (node.children != null && !node.children.isEmpty()) { for (Node n : node.children) { queue.offer(n); } } size--; } result.add(list); } } return result; } }
515. 在每个树行中找最大值
515. 在每个树行中找最大值
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 class Solution { public List<Integer> largestValues (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root != null ) { Queue<TreeNode> queue = new LinkedList <>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); int temp = Integer.MIN_VALUE; while (size != 0 ) { root = queue.poll(); temp = Math.max(temp, root.val); if (root.left != null ) { queue.offer(root.left); } if (root.right != null ) { queue.offer(root.right); } size--; } result.add(temp); } } return result; } }
116. 填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针
别先抛出一个,易错
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 Node connect (Node root) { if (root == null ) { return root; } Queue<Node> queue = new LinkedList <>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); Node last = null ; for (int i = 0 ; i < size; i++) { Node current = queue.poll(); if (last != null ) { last.next = current; } last = current; if (current.left != null ) { queue.offer(current.left); } if (current.right != null ) { queue.offer(current.right); } } if (last != null ) { last.next = null ; } } return root; } }
117. 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 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 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public Node connect (Node root) { if (root == null ) { return root; } Queue<Node> queue = new LinkedList <>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); Node last = null ; for (int i = 0 ; i < size; i++) { Node current = queue.poll(); if (last != null ) { last.next = current; } last = current; if (current.left != null ) { queue.offer(current.left); } if (current.right != null ) { queue.offer(current.right); } } if (last != null ) { last.next = null ; } } return root; } }
104. 二叉树的最大深度
104. 二叉树的最大深度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int maxDepth (TreeNode root) { int deep = 0 ; if (root!=null ){ Queue<TreeNode>queue = new LinkedList <>(); queue.offer(root); while (!queue.isEmpty()){ int size = queue.size(); while (size!=0 ){ size--; root = queue.poll(); if (root.left!=null ){ queue.offer(root.left); } if (root.right!=null ){ queue.offer(root.right); } } deep++; } } return deep; } }
111. 二叉树的最小深度
111. 二叉树的最小深度
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 class Solution { public int minDepth (TreeNode root) { int deep = 0 ; if (root != null ) { Queue<TreeNode> queue = new LinkedList <>(); queue.offer(root); while (!queue.isEmpty()) { deep++; int size = queue.size(); while (size != 0 ) { size--; root = queue.poll(); if (root.left != null ) { queue.offer(root.left); } if (root.right != null ) { queue.offer(root.right); } if (root.left==null &&root.right==null ){ return deep; } } } } return deep; } }
二叉树的属性
101. 对称二叉树
101. 对称二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public boolean isSymmetric (TreeNode root) { if (root == null ) { return false ; } return isSymmetry(root.left, root.right); } public boolean isSymmetry (TreeNode left, TreeNode right) { if (left == null && right == null ) { return true ; } else if (left != null && right != null ) { return left.val == right.val && isSymmetry(left.left, right.right) && isSymmetry(left.right, right.left); } 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 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 65 66 67 68 69 70 71 public boolean isSymmetric2 (TreeNode root) { Deque<TreeNode> deque = new LinkedList <>(); deque.offerFirst(root.left); deque.offerLast(root.right); while (!deque.isEmpty()) { TreeNode leftNode = deque.pollFirst(); TreeNode rightNode = deque.pollLast(); if (leftNode == null && rightNode == null ) { continue ; } if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) { return false ; } deque.offerFirst(leftNode.left); deque.offerFirst(leftNode.right); deque.offerLast(rightNode.right); deque.offerLast(rightNode.left); } return true ; } public boolean isSymmetric3 (TreeNode root) { Queue<TreeNode> deque = new LinkedList <>(); deque.offer(root.left); deque.offer(root.right); while (!deque.isEmpty()) { TreeNode leftNode = deque.poll(); TreeNode rightNode = deque.poll(); if (leftNode == null && rightNode == null ) { continue ; } if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) { return false ; } deque.offer(leftNode.left); deque.offer(rightNode.right); deque.offer(leftNode.right); deque.offer(rightNode.left); } return true ; }
104. 二叉树的最大深度
104. 二叉树的最大深度
前面有用层次遍历的写法,这里递归秒了
1 2 3 4 5 6 7 8 class Solution { public int maxDepth (TreeNode root) { if (root == null ) { return 0 ; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 ; } }
111. 二叉树的最小深度
111. 二叉树的最小深度
前面层次遍历有迭代的做法,这里用递归,注意怎么定义最小深度的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int minDepth (TreeNode root) { if (root == null ) { return 0 ; } if (root.left == null ) { return minDepth(root.right) + 1 ; } if (root.right == null ) { return minDepth(root.left) + 1 ; } return 1 + Math.min(minDepth(root.left), minDepth(root.right)); } }
222. 完全二叉树的节点个数
222. 完全二叉树的节点个数
直接当做普通二叉树来做
1 2 3 4 5 6 7 8 class Solution { public int countNodes (TreeNode root) { if (root==null ){ return 0 ; } return 1 +countNodes(root.left)+countNodes(root.right); } }
借助完全二叉树的性质
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 int countNodes (TreeNode root) { if (root == null ) { return 0 ; } TreeNode left = root.left; TreeNode right = root.right; int l = 0 , r = 0 ; while (left != null ) { left = left.left; l++; } while (right != null ) { right = right.right; r++; } if (l == r) { return (2 << l) - 1 ; } return 1 + countNodes(root.left) + countNodes(root.right); } }
110. 平衡二叉树
110. 平衡二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean isBalanced (TreeNode root) { if (root==null ){ return true ; } int l = getTreeDeep(root.left); int r = getTreeDeep(root.right); return Math.abs(l-r)<=1 && isBalanced(root.left) && isBalanced(root.right); } public int getTreeDeep (TreeNode node) { if (node==null ){ return 0 ; } return Math.max(getTreeDeep(node.left),getTreeDeep(node.right))+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 class Solution { public boolean isBalanced (TreeNode root) { return getTreeDeep(root) != -1 ; } public int getTreeDeep (TreeNode node) { if (node == null ) { return 0 ; } int l = getTreeDeep(node.left); if (l == -1 ) { return -1 ; } int r = getTreeDeep(node.right); if (r == -1 ) { return -1 ; } if (Math.abs(l - r) > 1 ) { return -1 ; } return 1 + Math.max(l, r); } }
257. 二叉树的所有路径
257. 二叉树的所有路径
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 class Solution { List<String> result = new ArrayList <>(); public List<String> binaryTreePaths (TreeNode root) { if (root != null ) { resolve(root, new ArrayList <Integer>()); } return result; } public void resolve (TreeNode root, List<Integer> list) { list.add(root.val); if (root.left == null && root.right == null ) { StringBuilder builder = new StringBuilder (); for (Integer i : list) { builder.append(i); builder.append("->" ); } builder.delete(builder.length() - 2 , builder.length()); result.add(builder.toString()); } else { if (root.left != null ) { resolve(root.left, list); list.remove(list.size() - 1 ); } if (root.right != null ) { resolve(root.right, list); list.remove(list.size() - 1 ); } } } }
100. 相同的树
100. 相同的树
1 2 3 4 5 6 7 8 9 10 class Solution { public boolean isSameTree (TreeNode p, TreeNode q) { if (p == null && q == null ) { return true ; } else if (p != null && q != null ) { return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } return false ; } }
404. 左叶子之和
404. 左叶子之和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int sumOfLeftLeaves (TreeNode root) { if (root==null ){ return 0 ; } if (root.left!=null &&root.left.left==null &&root.left.right==null ){ return root.left.val+sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right); }else { return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right); } } }
513. 找树左下角的值
513. 找树左下角的值
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 { int deep = -1 ; int result = 0 ; public int findBottomLeftValue (TreeNode root) { dfs(root,0 ); return result; } public void dfs (TreeNode root,int cur) { if (cur>deep){ result = root.val; deep = cur; } if (root.left!=null ){ dfs(root.left,cur+1 ); } if (root.right!=null ){ dfs(root.right,cur+1 ); } } }
112. 路径总和
112. 路径总和
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 class Solution { public boolean hasPathSum (TreeNode root, int targetSum) { if (root == null ) { return false ; } return isResult(root, 0 , targetSum); } public boolean isResult (TreeNode node, int temp, int targetSum) { temp += node.val; if (node.left == null && node.right == null && temp == targetSum) { return true ; } boolean l = false ; boolean r = false ; if (node.left != null ) { l = isResult(node.left, temp, targetSum); } if (node.right != null ) { r = isResult(node.right, temp, targetSum); } return l || r; } }
572. 另一棵树的子树
572. 另一棵树的子树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean isSubtree (TreeNode root, TreeNode subRoot) { if (root == null ) { return subRoot == null ; } return isSame(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); } public boolean isSame (TreeNode tree1, TreeNode tree2) { if (tree1 == null && tree2 == null ) { return true ; } else if (tree1 != null && tree2 != null ) { return tree1.val == tree2.val && isSame(tree1.left, tree2.left) && isSame(tree1.right, tree2.right); } return false ; } }
559. N 叉树的最大深度
559. N 叉树的最大深度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int maxDepth (Node root) { if (root == null ) { return 0 ; } else if (root.children == null || root.children.isEmpty()) { return 1 ; } int max = 0 ; for (Node n : root.children) { max = Math.max(max, maxDepth(n)); } return max + 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 class Solution { public int maxDepth (TreeNode root) { if (root == null ) { return 0 ; } Deque<TreeNode> deque = new LinkedList <>(); deque.offer(root); int depth = 0 ; while (!deque.isEmpty()) { int size = deque.size(); depth++; for (int i = 0 ; i < size; i++) { TreeNode node = deque.poll(); if (node.left != null ) { deque.offer(node.left); } if (node.right != null ) { deque.offer(node.right); } } } return depth; } }
二叉树的修改与改造
226. 翻转二叉树
226. 翻转二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public TreeNode invertTree (TreeNode root) { invert(root); return root; } public void invert (TreeNode node) { if (node == null ) { return ; } TreeNode temp = node.left; node.left = node.right; node.right = temp; invert(node.left); invert(node.right); } }
递归很简单搞定,也可以BFS,这里直接贴别人的代码了,太无聊了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public TreeNode invertTree (TreeNode root) { if (root == null ) {return null ;} ArrayDeque<TreeNode> deque = new ArrayDeque <>(); deque.offer(root); while (!deque.isEmpty()) { int size = deque.size(); while (size-- > 0 ) { TreeNode node = deque.poll(); swap(node); if (node.left != null ) deque.offer(node.left); if (node.right != null ) deque.offer(node.right); } } return root; } public void swap (TreeNode root) { TreeNode temp = root.left; root.left = root.right; root.right = temp; } }
106. 从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
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 class Solution { public TreeNode buildTree (int [] inorder, int [] postorder) { if (inorder.length == 0 ) { return null ; } TreeNode head = new TreeNode (postorder[postorder.length - 1 ]); int k; for (k = 0 ; k < inorder.length; k++) { if (inorder[k] == postorder[postorder.length - 1 ]) { break ; } } int leftLength = k; int rightLength = inorder.length - k - 1 ; head.left = buildTree(Arrays.copyOfRange(inorder, 0 , leftLength), Arrays.copyOfRange(postorder, 0 , leftLength)); head.right = buildTree(Arrays.copyOfRange(inorder, k + 1 , inorder.length), Arrays.copyOfRange(postorder, leftLength, postorder.length - 1 )); return head; } }
copy出来很浪费时间和空间,不copy用下面的类似题目的方法
105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
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 TreeNode buildTree (int [] preorder, int [] inorder) { return build(preorder, inorder, 0 , preorder.length - 1 , 0 , inorder.length); } public TreeNode build (int [] preorder, int [] inorder, int preStart, int preEnd, int inStart, int inEnd) { if (preorder.length == 0 || preStart > preEnd) { return null ; } TreeNode root = new TreeNode (preorder[preStart]); int k; for (k = inStart; k <= inEnd; k++) { if (inorder[k] == preorder[preStart]) { break ; } } int lenL = k - inStart; root.left = build(preorder, inorder, preStart + 1 , preStart + 1 + lenL - 1 , inStart, k - 1 ); root.right = build(preorder, inorder, preStart + 1 + lenL, preEnd, k + 1 , inEnd); return root; } }
654. 最大二叉树
654. 最大二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public TreeNode constructMaximumBinaryTree (int [] nums) { return build(nums, 0 , nums.length - 1 ); } public TreeNode build (int [] nums, int start, int end) { if (start > end) { return null ; } int big = start; for (int i = start + 1 ; i <= end; i++) { if (nums[i] > nums[big]) { big = i; } } TreeNode root = new TreeNode (nums[big]); root.left = build(nums, start, big - 1 ); root.right = build(nums, big + 1 , end); return root; } }
617. 合并二叉树
617. 合并二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public TreeNode mergeTrees (TreeNode root1, TreeNode root2) { if (root1 == null ) { return root2; } if (root2 == null ) { return root1; } root1.val += root2.val; root1.left = mergeTrees(root1.left, root2.left); root1.right = mergeTrees(root1.right, root2.right); return root1; } }
二叉搜索树的属性
700. 二叉搜索树中的搜索
700. 二叉搜索树中的搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public TreeNode searchBST (TreeNode root, int val) { if (root==null ){ return null ; } if (root.val<val){ return searchBST(root.right,val); } if (root.val>val){ return searchBST(root.left,val); } return root; } }
98. 验证二叉搜索树
98. 验证二叉搜索树
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 class Solution { TreeNode max; public boolean isValidBST (TreeNode root) { if (root == null ) { return true ; } boolean l = isValidBST(root.left); if (!l) { return false ; } if (max != null && max.val >= root.val) { return false ; } max = root; return isValidBST(root.right); } }
530. 二叉搜索树的最小绝对差
530. 二叉搜索树的最小绝对差
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { TreeNode last; int min = Integer.MAX_VALUE; public int getMinimumDifference (TreeNode root) { midOrder(root); return min; } public void midOrder (TreeNode root) { if (root==null ){ return ; } midOrder(root.left); if (last!=null ){ min = Math.min(min,root.val-last.val); } last = root; midOrder(root.right); } }
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 class Solution { public int getMinimumDifference (TreeNode root) { int min = Integer.MAX_VALUE; TreeNode last = null ; Stack<TreeNode> stack = new Stack <>(); while (root != null || !stack.isEmpty()) { if (root != null ) { stack.push(root); root = root.left; } else { root = stack.pop(); if (last != null ) { min = Math.min(min, root.val - last.val); } last = root; root = root.right; } } return min; } }
501. 二叉搜索树中的众数
501. 二叉搜索树中的众数
如果是普通树就需要用Map了,这里的话是二叉搜索树,可以借助他的特性,还要注意考虑只有一个都特殊情况怎么处理
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 { int count = 0 ; TreeNode last; int temp = 0 ; List<Integer> result = new ArrayList <>(); public int [] findMode(TreeNode root) { midOrder(root); int [] nums = new int [result.size()]; for (int i = 0 ; i < nums.length; i++) { nums[i] = result.get(i); } return nums; } public void midOrder (TreeNode root) { if (root == null ) { return ; } midOrder(root.left); if (last == null || root.val > last.val) { temp = 1 ; } else { temp++; } if (temp > count) { count = temp; result.clear(); result.add(root.val); } else if (temp == count) { result.add(root.val); } last = root; midOrder(root.right); } }
538. 把二叉搜索树转换为累加树
538. 把二叉搜索树转换为累加树
右->中->左就是倒序了,用一个保存上次的位置的值即可,初始化为0,每次遍历到的加上上次位置的值即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { int last = 0 ; public TreeNode convertBST (TreeNode root) { convertBSTTree(root); return root; } public void convertBSTTree (TreeNode root) { if (root == null ) { return ; } convertBSTTree(root.right); root.val += last; last = root.val; convertBSTTree(root.left); } }
1038. 从二叉搜索树到更大和树
1038. 从二叉搜索树到更大和树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { int last = 0 ; public TreeNode bstToGst (TreeNode root) { bstToGstTree(root); return root; } public void bstToGstTree (TreeNode root) { if (root == null ) { return ; } bstToGstTree(root.right); root.val += last; last = root.val; bstToGstTree(root.left); } }
二叉树公共祖先问题
236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null ) { return root; } if (left == null ) { return right; } else { return left; } } }
235. 二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先
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 class Solution { public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { if (root == null ) { return null ; } if (root.val < p.val && root.val < q.val) { TreeNode right = lowestCommonAncestor(root.right, p, q); if (right != null ) { return right; } } else if (root.val > p.val && root.val > q.val) { TreeNode left = lowestCommonAncestor(root.left, p, q); if (left != null ) { return left; } } else { return root; } return null ; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { while (root != null ) { if (root.val < p.val && root.val < q.val) { root = root.right; } else if (root.val > p.val && root.val > q.val) { root = root.left; } else { return root; } } return null ; } }
二叉搜索树的修改与构造
701. 二叉搜索树中的插入操作
701. 二叉搜索树中的插入操作
没想出来。。。真裂开
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public TreeNode insertIntoBST (TreeNode root, int val) { if (root == null ) { return new TreeNode (val); } if (root.val > val) { root.left = insertIntoBST(root.left, val); } else { root.right = insertIntoBST(root.right, val); } return root; } }
迭代好理解点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public TreeNode insertIntoBST (TreeNode root, int val) { if (root == null ) { return new TreeNode (val); } TreeNode last = root; TreeNode newHead = root; while (root != null ) { last = root; if (root.val > val) { root = root.left; } else { root = root.right; } } if (last.val > val) { last.left = new TreeNode (val); } else { last.right = new TreeNode (val); } return newHead; } }
450. 删除二叉搜索树中的节点
450. 删除二叉搜索树中的节点
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 TreeNode deleteNode (TreeNode root, int key) { if (root==null ){ return null ; }else if (root.val==key){ if (root.left==null &&root.right==null ){ return null ; } else if (root.left!=null &&root.right==null ){ return root.left; } else if (root.right!=null &&root.left==null ){ return root.right; } else { TreeNode cur = root.right; while (cur.left!=null ){ cur = cur.left; } cur.left = root.left; return root.right; } }else { if (root.val<key){ root.right = deleteNode(root.right,key); }else { root.left = deleteNode(root.left,key); } return root; } } }
108. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public TreeNode sortedArrayToBST (int [] nums) { return build(nums,0 ,nums.length-1 ); } public TreeNode build (int [] nums,int start,int end) { if (start>end){ return null ; } int mid = start +(end-start)/2 ; TreeNode root = new TreeNode (nums[mid]); root.left = build(nums,start,mid-1 ); root.right = build(nums,mid+1 ,end); return root; } }
回溯算法 回溯也叫回溯搜索法,是一种搜索的方式,回溯是递归的副产物,有递归就会有回溯,回溯函数就是指一个递归函数。
回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案 ,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质,所以回溯并不是高效的算法,但有些问题只能进行暴力搜索,最多再剪枝一下,没有更高效的算法了。
回溯法解决的问题都可以抽象为树形结构 ,因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度就构成了树的深度 。递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。
回溯模板
回溯函数模板返回值以及参数
回溯函数终止条件
回溯搜索的遍历过程
1 2 3 4 5 6 7 8 9 10 11 12 void backtracking (参数) { if (终止条件) { 存放结果; return ; } for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); 回溯,撤销处理结果 } }
能解决的问题
组合问题:N个数里面按一定规则找出k个数的集合
切割问题:一个字符串按一定规则有几种切割方式
子集问题:一个N个数的集合里有多少符合条件的子集
排列问题:N个数按一定规则全排列,有几种排列方式
棋盘问题:N皇后,解数独等等
组合问题
77. 组合
77. 组合
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 class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> temp = new ArrayList <>(); public List<List<Integer>> combine (int n, int k) { backtrack(1 , n, k); return result; } public void backtrack (int startIndex, int n, int k) { if (temp.size() == k) { result.add(new ArrayList <>(temp)); return ; } if (temp.size() + n - startIndex + 1 < k) { return ; } for (int i = startIndex; i <= n; i++) { temp.add(i); backtrack(i + 1 , n, k); temp.remove(temp.size() - 1 ); } } }
39. 组合总和
39. 组合总和
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 class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> temp = new ArrayList <>(); public List<List<Integer>> combinationSum (int [] candidates, int target) { Arrays.sort(candidates); backTracking(candidates, target, 0 , 0 ); return result; } public void backTracking (int [] candidates, int target, int index, int sum) { if (sum >= target) { if (sum == target) { result.add(new ArrayList <>(temp)); } return ; } for (int i = index; i < candidates.length; i++) { if (sum + candidates[i] > target) { break ; } sum += candidates[i]; temp.add(candidates[i]); backTracking(candidates, target, i, sum); sum -= candidates[i]; temp.remove(temp.size() - 1 ); } } }
40. 组合总和 II
40. 组合总和 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 28 29 30 31 32 33 class Solution { public List<List<Integer>> combinationSum2 (int [] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> result = new ArrayList <>(); backTracking(candidates, target, 0 , 0 , result, new ArrayList <>()); return result; } public void backTracking (int [] candidates, int target, int sum, int index, List<List<Integer>> result, List<Integer> temp) { if (sum == target) { result.add(new ArrayList <>(temp)); } for (int i = index; i < candidates.length; i++) { if (sum + candidates[i] > target) { break ; } if (i > index && candidates[i] == candidates[i - 1 ]) { continue ; } sum += candidates[i]; temp.add(candidates[i]); backTracking(candidates, target, sum, i + 1 , result, temp); sum -= candidates[i]; temp.remove(temp.size() - 1 ); } } }
216. 组合总和 III
216. 组合总和 III
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 class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> temp = new ArrayList <>(); int sum = 0 ; public List<List<Integer>> combinationSum3 (int k, int n) { backTracking(k, n, 1 ); return result; } public void backTracking (int k, int n, int startIndex) { if (temp.size() >= k || sum >= n) { if (temp.size() == k && sum == n) { result.add(new ArrayList <>(temp)); } return ; } for (int i = startIndex; i <= 9 - (k - temp.size()) + 1 ; i++) { sum += i; temp.add(i); backTracking(k, n, i + 1 ); temp.remove(temp.size() - 1 ); sum -= i; } } }
17. 电话号码的字母组合
17. 电话号码的字母组合
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 { List<String>result = new ArrayList <>(); char [] temp; Map<Character,String>map = new HashMap <>(); public List<String> letterCombinations (String digits) { temp = new char [digits.length()]; map.put('2' ,"abc" ); map.put('3' ,"def" ); map.put('4' ,"ghi" ); map.put('5' ,"jkl" ); map.put('6' ,"mno" ); map.put('7' ,"pqrs" ); map.put('8' ,"tuv" ); map.put('9' ,"wxyz" ); if (digits.length()!=0 ){ backTracking(digits,0 ); } return result; } public void backTracking (String digits,int index) { if (index==digits.length()){ result.add(new String (temp)); return ; } char c = digits.charAt(index); String s = map.get(c); for (int i = 0 ;i<s.length();i++){ temp[index] = s.charAt(i); backTracking(digits,index+1 ); temp[index] = ' ' ; } } }
排列问题
46. 全排列
46. 全排列
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 class Solution { public List<List<Integer>> permute (int [] nums) { boolean [] isVisited = new boolean [nums.length]; List<List<Integer>> result = new ArrayList <>(); List<Integer> temp = new ArrayList <>(); backTracking(result, new ArrayList <>(), isVisited, nums); return result; } public void backTracking (List<List<Integer>> result, List<Integer> temp, boolean [] isVisited, int [] nums) { if (temp.size() == nums.length) { result.add(new ArrayList <>(temp)); } for (int i = 0 ; i < nums.length; i++) { if (isVisited[i]) { continue ; } temp.add(nums[i]); isVisited[i] = true ; backTracking(result, temp, isVisited, nums); temp.remove(temp.size() - 1 ); isVisited[i] = false ; } } }
47. 全排列 II
47. 全排列 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 28 29 30 31 32 33 34 class Solution { public List<List<Integer>> permuteUnique (int [] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList <>(); backTracking(result, new ArrayList <>(), new boolean [nums.length], nums); return result; } public void backTracking (List<List<Integer>> result, List<Integer> temp, boolean [] isVisited, int [] nums) { if (temp.size() == nums.length) { result.add(new ArrayList <>(temp)); return ; } for (int i = 0 ; i < nums.length; i++) { if (i != 0 && nums[i] == nums[i - 1 ] && !isVisited[i - 1 ]) { continue ; } if (isVisited[i]) { continue ; } isVisited[i] = true ; temp.add(nums[i]); backTracking(result, temp, isVisited, nums); isVisited[i] = false ; temp.remove(temp.size() - 1 ); } } }
子集问题
78. 子集
78. 子集
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 class Solution { public List<List<Integer>> subsets (int [] nums) { List<List<Integer>>result = new ArrayList <>(); backTracking(result,new ArrayList <>(),nums,0 ); return result; } public void backTracking (List<List<Integer>>result, List<Integer>temp,int [] nums,int index) { if (index>=nums.length){ result.add(new ArrayList <>(temp)); return ; } for (int i = index;i<=nums.length;i++){ if (i==nums.length){ backTracking(result,temp,nums,i+1 ); continue ; } temp.add(nums[i]); backTracking(result,temp,nums,i+1 ); temp.remove(temp.size()-1 ); } } }
也可以不靠终止条件,而是记录每个结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { List<List<Integer>> result = new ArrayList <>(); LinkedList<Integer> path = new LinkedList <>(); public List<List<Integer>> subsets (int [] nums) { subsetsHelper(nums, 0 ); return result; } private void subsetsHelper (int [] nums, int startIndex) { result.add(new ArrayList <>(path)); if (startIndex >= nums.length){ return ; } for (int i = startIndex; i < nums.length; i++){ path.add(nums[i]); subsetsHelper(nums, i + 1 ); path.removeLast(); } } }
90. 子集 II
90. 子集 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 class Solution { public List<List<Integer>> subsetsWithDup (int [] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList <>(); backTracking(result, new ArrayList <>(), nums, 0 ); return result; } public void backTracking (List<List<Integer>> result, List<Integer> temp, int [] nums, int index) { result.add(new ArrayList <>(temp)); for (int i = index; i < nums.length; i++) { if (i != index && nums[i] == nums[i - 1 ]) { continue ; } temp.add(nums[i]); backTracking(result, temp, nums, i + 1 ); temp.remove(temp.size() - 1 ); } } }
分割问题
131. 分割回文串
131. 分割回文串
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 class Solution { public List<List<String>> partition (String s) { List<List<String>> result = new ArrayList <>(); backTracking(result, new ArrayList <>(), s, 0 ); return result; } public void backTracking (List<List<String>> result, List<String> temp, String s, int index) { if (index == s.length()) { result.add(new ArrayList <>(temp)); } for (int i = index; i < s.length(); i++) { String wait = s.substring(index, i + 1 ); if (isMoslems(wait)) { temp.add(wait); backTracking(result, temp, s, i + 1 ); temp.remove(temp.size() - 1 ); } } } public boolean isMoslems (String s) { if (s == null || s.length() == 0 ) { return false ; } int left = 0 , right = s.length() - 1 ; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false ; } left++; right--; } return true ; } }
93. 复原 IP 地址
93. 复原 IP 地址
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 class Solution { public List<String> restoreIpAddresses (String s) { List<String> result = new ArrayList <>(); backTracking(result, new StringBuilder (), s, 1 , 0 ); return result; } public void backTracking (List<String> result, StringBuilder builder, String s, int deep, int index) { if (deep > 4 ) { if (index >= s.length()) { result.add(builder.toString()); } return ; } for (int i = index; i < s.length() - (4 - deep); i++) { String temp = s.substring(index, i + 1 ); if (isCurrent(temp)) { builder.append(temp); if (deep != 4 ) { builder.append("." ); } backTracking(result, builder, s, deep + 1 , i + 1 ); int length = builder.length(); if (deep == 4 ) { builder.delete(length - temp.length(), length); } else { builder.delete(length - temp.length() - 1 , length); } } } } public boolean isCurrent (String s) { if (s.isBlank()) { return false ; } if (s.length() > 1 && s.charAt(0 ) == '0' ) { return false ; } try { int num = Integer.parseInt(s); return num >= 0 && num <= 255 ; } catch (Exception e) { return false ; } } }
棋盘问题 都是困难级别的题目
51. N 皇后
51. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 class Solution { public List<List<String>> solveNQueens (int n) { List<List<String>> result = new ArrayList <>(); char [][] board = new char [n][n]; for (int i = 0 ; i < n; i++) { Arrays.fill(board[i], '.' ); } backTracking(n, 0 , board, result); return result; } public boolean isLegal (int row, int column, int n, char [][] board) { for (int i = 0 ; i < row; i++) { if (board[i][column] == 'Q' ) { return false ; } } for (int i = row - 1 , j = column - 1 ; i >= 0 && j >= 0 ; i--, j--) { if (board[i][j] == 'Q' ) { return false ; } } for (int i = row - 1 , j = column + 1 ; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q' ) { return false ; } } return true ; } public void backTracking (int n, int deep, char [][] board, List<List<String>> result) { if (deep == n) { List<String> temp = new ArrayList <>(); for (int i = 0 ; i < n; i++) { temp.add(new String (board[i])); } result.add(temp); return ; } for (int j = 0 ; j < n; j++) { if (isLegal(deep, j, n, board)) { board[deep][j] = 'Q' ; backTracking(n, deep + 1 , board, result); board[deep][j] = '.' ; } } } }
37. 解数独
37. 解数独
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 class Solution { public void solveSudoku (char [][] board) { solveSudokuHelper(board); } public boolean isLegal (int row, int column, char num, char [][] board) { for (int j = 0 ; j < 9 ; j++) { if (board[row][j] == num) { return false ; } } for (int i = 0 ; i < 9 ; i++) { if (board[i][column] == num) { return false ; } } int top = row / 3 * 3 , start = column / 3 * 3 ; for (int i = top; i < top + 3 ; i++) { for (int j = start; j < start + 3 ; j++) { if (board[i][j] == num) { return false ; } } } return true ; } public boolean solveSudokuHelper (char [][] board) { for (int i = 0 ; i < 9 ; i++) { for (int j = 0 ; j < 9 ; j++) { if (board[i][j] == '.' ) { for (int num = 1 ; num <= 9 ; num++) { char c = (char ) (num + '0' ); if (isLegal(i, j, c, board)) { board[i][j] = c; if (solveSudokuHelper(board)) { return true ; } board[i][j] = '.' ; } } return false ; } } } return true ; } }
这里一定需要能判断是否处理完,不然不知道什么时候跳出,等自然循环跳出最后都恢复为原状了,也可以如下
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 65 66 class Solution { public void solveSudoku (char [][] board) { for (int i = 0 ; i < 9 ; i++) { for (int j = 0 ; j < 9 ; j++) { if (board[i][j] == '.' ) { for (int num = 1 ; num <= 9 ; num++) { char c = (char ) (num + '0' ); if (isLegal(i, j, c, board)) { board[i][j] = c; solveSudoku(board); if (isSolved(board)) return ; board[i][j] = '.' ; } } return ; } } } } public boolean isLegal (int row, int column, char num, char [][] board) { for (int j = 0 ; j < 9 ; j++) { if (board[row][j] == num) { return false ; } } for (int i = 0 ; i < 9 ; i++) { if (board[i][column] == num) { return false ; } } int top = row / 3 * 3 , start = column / 3 * 3 ; for (int i = top; i < top + 3 ; i++) { for (int j = start; j < start + 3 ; j++) { if (board[i][j] == num) { return false ; } } } return true ; } public boolean isSolved (char [][] board) { for (int i = 0 ; i < 9 ; i++) { for (int j = 0 ; j < 9 ; j++) { if (board[i][j] == '.' ) { return false ; } } } return true ; } }
其他问题
491. 非递减子序列
491. 非递减子序列
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 class Solution { List<List<Integer>>result = new ArrayList <>(); List<Integer>temp = new ArrayList <>(); public List<List<Integer>> findSubsequences (int [] nums) { backTracking(nums,0 ); return result; } public void backTracking (int []nums,int index) { if (temp.size()>=2 ){ result.add(new ArrayList <>(temp)); } Set<Integer>used = new HashSet <>(); for (int i = index;i<nums.length;i++){ if (used.contains(nums[i])){ continue ; } if (temp.size()>0 &&temp.get(temp.size()-1 )>nums[i]){ continue ; } temp.add(nums[i]); used.add(nums[i]); backTracking(nums,i+1 ); temp.remove(temp.size()-1 ); } } }
332. 重新安排行程
332. 重新安排行程
贪心算法 贪心的本质是选择每一阶段的局部最优,从而达到全局最优 。
刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心 。
并没有太多的技巧性,贪心想不到反例就可能可以用,不行就只能动规了,但很多时候还是需要数学理论来支持的,有些没写过类似的不会就是不会了
贪心算法一般分为如下四步:
将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
但其实很多时候用不上,想得到贪心策略很重要,想不出啥步骤都没用
简单难度
455. 分发饼干
455. 分发饼干
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int findContentChildren (int [] g, int [] s) { Arrays.sort(g); Arrays.sort(s); int count = 0 ; int i = 0 , j = 0 ; while (i < g.length && j < s.length) { if (s[j] >= g[i]) { i++; j++; count++; } else { j++; } } return count; } }
1005. K 次取反后最大化的数组和
1005. K 次取反后最大化的数组和
下面是自己写的,时间复杂度和空间复杂度都比较高
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int largestSumAfterKNegations (int [] nums, int k) { PriorityQueue<Integer> queue = new PriorityQueue <>(); for (int i : nums) { queue.offer(i); } while (k != 0 ) { queue.offer(-queue.poll()); k--; } int sum = 0 ; while (!queue.isEmpty()) { sum += queue.poll(); } return sum; } }
版本2也是不断排序,没啥好看的了
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 class Solution { public int largestSumAfterKNegations (int [] nums, int K) { nums = IntStream.of(nums) .boxed() .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)) .mapToInt(Integer::intValue).toArray(); int len = nums.length; for (int i = 0 ; i < len; i++) { if (nums[i] < 0 && K > 0 ) { nums[i] = -nums[i]; K--; } } if (K % 2 == 1 ) nums[len - 1 ] = -nums[len - 1 ]; return Arrays.stream(nums).sum(); } } class Solution { public int largestSumAfterKNegations (int [] nums, int k) { if (nums.length == 1 ) return nums[0 ]; Arrays.sort(nums); for (int i = 0 ; i < nums.length && k > 0 ; i++) { if (nums[i] < 0 ) { nums[i] = -nums[i]; k--; } } if (k % 2 == 1 ) { Arrays.sort(nums); nums[0 ] = -nums[0 ]; } int sum = 0 ; for (int num : nums) { sum += num; } return sum; } }
860. 柠檬水找零
860. 柠檬水找零
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 class Solution { public boolean lemonadeChange (int [] bills) { int fiveCount = 0 , tenCount = 0 ; for (int i = 0 ; i < bills.length; i++) { if (bills[i] == 5 ) { fiveCount++; } else if (bills[i] == 10 ) { fiveCount--; tenCount++; if (fiveCount < 0 ) { return false ; } } else { if (tenCount > 0 ) { fiveCount--; tenCount--; } else { fiveCount -= 3 ; } if (fiveCount < 0 || tenCount < 0 ) { return false ; } } } return true ; } }
中等难度 序列问题
376. 摆动序列
376. 摆动序列
思考有偏差,裂开,没有考虑到一路向下和一路向上的更新情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int wiggleMaxLength (int [] nums) { int result = 1 , pre = 0 ; for (int i = 1 ; i < nums.length; i++) { int current = nums[i] - nums[i - 1 ]; if ((current < 0 && pre >= 0 ) || (current > 0 && pre <= 0 )) { result++; pre = current; } } return result; } }
738. 单调递增的数字
738. 单调递增的数字
没想到贪心啊,暴力超时的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int monotoneIncreasingDigits (int n) { char [] chars = String.valueOf(n).toCharArray(); int start = chars.length; for (int i = chars.length - 2 ; i >= 0 ; i--) { if (chars[i] > chars[i + 1 ]) { chars[i]--; start = i + 1 ; } } for (int i = start; i < chars.length; i++) { chars[i] = '9' ; } return Integer.valueOf(new String (chars)); } }
股票问题
121. 买卖股票的最佳时机
121. 买卖股票的最佳时机
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int maxProfit (int [] prices) { int max = 0 ; int min = prices[0 ]; for (int i = 1 ; i < prices.length; i++) { if (prices[i] > min) { int temp = prices[i] - min; max = Math.max(max, temp); } else { min = prices[i]; } } return max; } }
动态规划,顺便放这里了,后面动规部分可以直接跳转来这里看,我是觉得这里用动规是有点难理解的,回头多看几遍吧
代码随想录 (programmercarl.com)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int maxProfit (int [] prices) { int length = prices.length; if (length <= 1 ) { return 0 ; } int [][] dp = new int [length][2 ]; dp[0 ][0 ] = -prices[0 ]; dp[0 ][1 ] = 0 ; for (int i = 1 ; i < length; i++) { dp[i][0 ] = Math.max(dp[i - 1 ][0 ], -prices[i]); dp[i][1 ] = Math.max(dp[i - 1 ][1 ], dp[i - 1 ][0 ] + prices[i]); } return dp[length - 1 ][1 ]; } }
122. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int maxProfit (int [] prices) { int result = 0 , min = prices[0 ]; for (int i = 1 ; i < prices.length; i++) { if (prices[i] < prices[i - 1 ]) { result += (prices[i - 1 ] - min); min = prices[i]; } } if (prices[prices.length - 1 ] - min > 0 ) { result += (prices[prices.length - 1 ] - min); } return result; } }
假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
更简化
1 2 3 4 5 6 7 8 9 10 class Solution { public int maxProfit (int [] prices) { int result = 0 ; for (int i = 1 ; i < prices.length; i++) { result += Math.max(prices[i] - prices[i - 1 ], 0 ); } return result; } }
动态规划解决
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int maxProfit (int [] prices) { int length = prices.length; if (length <= 1 ) { return 0 ; } int [][] dp = new int [length][2 ]; dp[0 ][0 ] = -prices[0 ]; dp[0 ][1 ] = 0 ; for (int i = 1 ; i < length; i++) { dp[i][0 ] = Math.max(dp[i - 1 ][0 ], dp[i - 1 ][1 ] - prices[i]); dp[i][1 ] = Math.max(dp[i - 1 ][1 ], dp[i - 1 ][0 ] + prices[i]); } return dp[length - 1 ][1 ]; } }
714. 买卖股票的最佳时机含手续费
714. 买卖股票的最佳时机含手续费
这里的贪心是真的睿智,贪心思想可以浓缩成一句话,即当我们卖出一支股票时,我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int maxProfit (int [] prices, int fee) { int max = 0 ; int buy = prices[0 ] + fee; for (int i = 1 ; i < prices.length; i++) { if (prices[i] + fee < buy) { buy = prices[i] + fee; } else if (prices[i] > buy) { max += prices[i] - buy; buy = prices[i]; } } return max; } }
动规
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int maxProfit (int [] prices, int fee) { int length = prices.length; if (length <= 1 ) { return 0 ; } int [] dp = new int [2 ]; dp[0 ] = -prices[0 ]; for (int i = 1 ; i < length; i++) { dp[0 ] = Math.max(dp[0 ], dp[1 ] - prices[i]); dp[1 ] = Math.max(dp[1 ], dp[0 ] + prices[i] - fee); } return dp[1 ]; } }
两个维度权衡问题 遇到两个维度的时候,一定要想如何确定一个维度,然后再按照另一个维度重新排序,如果两个维度一起考虑肯定会顾此失彼
406. 根据身高重建队列
406. 根据身高重建队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int [][] reconstructQueue(int [][] people) { Arrays.sort(people, (a, b) -> { if (a[0 ] == b[0 ]) return a[1 ] - b[1 ]; return b[0 ] - a[0 ]; }); List<int []> temp = new ArrayList <>(); for (int [] ints : people) { temp.add(ints[1 ], ints); } int [][] reuslt = new int [people.length][2 ]; for (int i = 0 ; i < temp.size(); i++) { reuslt[i] = temp.get(i); } return reuslt; } }
135. 分发糖果
135. 分发糖果
力扣上定义是困难,这里考虑局部的时候如果左右都兼顾那么就会顾此失彼,这里使用两次贪心的
一次是从左到右遍历,只比较右边孩子评分比左边大的情况。
一次是从右到左遍历,只比较左边孩子评分比右边大的情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int candy (int [] ratings) { int [] candy = new int [ratings.length]; candy[0 ] = 1 ; for (int i = 1 ; i < ratings.length; i++) { candy[i] = ratings[i] > ratings[i - 1 ] ? candy[i - 1 ] + 1 : 1 ; } for (int i = ratings.length - 2 ; i >= 0 ; i--) { if (ratings[i] > ratings[i + 1 ]) { candy[i] = Math.max(candy[i], candy[i + 1 ] + 1 ); } } int result = 0 ; for (int i : candy) { result += i; } return result; } }
困难难度 区间问题
55. 跳跃游戏
55. 跳跃游戏
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean canJump (int [] nums) { if (nums.length == 1 ) { return true ; } int balance = nums[0 ], i = 0 ; while (balance != 0 && i != nums.length) { balance--; if (nums[i] > balance) { balance = nums[i]; } i++; } return i == nums.length ? true : false ; } }
45. 跳跃游戏 II
45. 跳跃游戏 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 28 class Solution { public int jump (int [] nums) { if (nums == null || nums.length == 0 || nums.length == 1 ) { return 0 ; } int result = 0 ; int maxCanJump = 0 ; int end = 0 ; for (int i = 0 ; i < nums.length; i++) { maxCanJump = Math.max(maxCanJump, i + nums[i]); if (i == end) { result++; end = maxCanJump; } if (end >= nums.length - 1 ) { break ; } } return result; } }
452. 用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球
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 class Solution { public int findMinArrowShots (int [][] points) { int result = 0 ; Arrays.sort(points, (a, b) -> Integer.compare(a[0 ], b[0 ])); int [] range = new int [2 ]; range[0 ] = points[0 ][0 ]; range[1 ] = points[0 ][1 ]; for (int i = 1 ; i < points.length; i++) { if (points[i][0 ] > range[1 ]) { result++; range[0 ] = points[i][0 ]; range[1 ] = points[i][1 ]; } else { range[0 ] = Math.max(points[i][0 ], range[0 ]); range[1 ] = Math.min(points[i][1 ], range[1 ]); } } return result + 1 ; } }
这样更简洁
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.Arrays;class Solution { public int findMinArrowShots (int [][] points) { if (points == null || points.length == 0 ) return 0 ; Arrays.sort(points, (a, b) -> Integer.compare(a[1 ], b[1 ])); int result = 1 ; int end = points[0 ][1 ]; for (int i = 1 ; i < points.length; i++) { if (points[i][0 ] > end) { result++; end = points[i][1 ]; } } return result; } }
435. 无重叠区间
435. 无重叠区间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int eraseOverlapIntervals (int [][] intervals) { Arrays.sort(intervals,(a,b)->Integer.compare(a[0 ],b[0 ])); int count = 0 ; int end = intervals[0 ][1 ]; for (int i = 1 ;i<intervals.length;i++){ if (end>intervals[i][0 ]){ count++; end = Math.min(end,intervals[i][1 ]); }else { end = intervals[i][1 ]; } } return count; } }
763. 划分字母区间
763. 划分字母区间
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 class Solution { public List<Integer> partitionLabels (String s) { int [] hash = new int [26 ]; List<Integer> result = new ArrayList <>(); for (int i = 0 ; i < s.length(); i++) { hash[s.charAt(i) - 'a' ] = i; } int last = -1 ; int index = 0 ; for (int i = 0 ; i < s.length(); i++) { index = Math.max(index, hash[s.charAt(i) - 'a' ]); if (i == index) { result.add(i - last); last = i; } } return result; } }
56. 合并区间
56. 合并区间
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 class Solution { public int [][] merge(int [][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0 ], b[0 ])); List<int []> temp = new ArrayList <>(); int start = intervals[0 ][0 ]; int end = intervals[0 ][1 ]; for (int i = 0 ; i < intervals.length; i++) { if (end >= intervals[i][0 ]) { end = Math.max(end, intervals[i][1 ]); } else { int [] ints = new int [2 ]; ints[0 ] = start; ints[1 ] = end; temp.add(ints); start = intervals[i][0 ]; end = intervals[i][1 ]; } } int [] ints = new int [2 ]; ints[0 ] = start; ints[1 ] = end; temp.add(ints); int [][] result = new int [temp.size()][2 ]; for (int i = 0 ; i < temp.size(); i++) { result[i] = temp.get(i); } return result; } }
其他
53. 最大子数组和
53. 最大子数组和
贪心
1 2 3 4 5 6 7 8 9 10 11 class Solution { public int maxSubArray (int [] nums) { int result = nums[0 ], temp = nums[0 ]; for (int i = 1 ; i < nums.length; i++) { temp = Math.max(temp + nums[i], nums[i]); result = temp > result ? temp : result; } return result; } }
动规
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int maxSubArray (int [] nums) { int [] dp = new int [nums.length]; int result = nums[0 ]; dp[0 ] = nums[0 ]; for (int i = 1 ;i<nums.length;i++){ dp[i] = Math.max(dp[i-1 ]+nums[i],nums[i]); result = dp[i]>result?dp[i]:result; } return result; } }
134. 加油站
134. 加油站
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 class Solution { public int canCompleteCircuit (int [] gas, int [] cost) { int totalGas = 0 ; int totalCostGas = 0 ; int index = 0 ; int range = 0 ; for (int i = 0 ; i < gas.length; i++) { totalGas += gas[i]; totalCostGas += cost[i]; range = range + gas[i] - cost[i]; if (range < 0 ) { index = i + 1 ; range = 0 ; } } return totalGas >= totalCostGas ? index : -1 ; } }
968. 监控二叉树
968. 监控二叉树
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 { int result = 0 ; public int minCameraCover (TreeNode root) { if (putCamera(root) == 0 ) { result++; } return result; } public int putCamera (TreeNode root) { if (root == null ) { return 2 ; } int left = putCamera(root.left); int right = putCamera(root.right); if (left == 2 && right == 2 ) { return 0 ; } else if (left == 0 || right == 0 ) { result++; return 1 ; } else { return 2 ; } } }
动态规划 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心 ,贪心没有状态推导,而是从局部直接选最优的。
对于动态规划问题,我将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!
确定dp数组(dp table)以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导的!
做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果 。
基础题目
509. 斐波那契数
509. 斐波那契数
1 2 3 4 5 6 7 8 9 class Solution { public int fib (int n) { if (n == 0 || n == 1 ) { return n; } return fib(n - 1 ) + fib(n - 2 ); } }
递归好理解,但这里迭代快很多
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int fib (int n) { if (n == 0 || n == 1 ) { return n; } int first = 0 , second = 1 ; for (int i = 2 ; i <= n; i++) { int temp = first + second; first = second; second = temp; } return second; } }
非压缩版本
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int fib (int n) { if (n <= 1 ) return n; int [] dp = new int [n + 1 ]; dp[0 ] = 0 ; dp[1 ] = 1 ; for (int index = 2 ; index <= n; index++){ dp[index] = dp[index - 1 ] + dp[index - 2 ]; } return dp[n]; } }
70. 爬楼梯
70. 爬楼梯
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int climbStairs (int n) { if (n<=2 ){ return n; } int first = 1 ,second = 2 ; for (int i = 3 ;i<=n;i++){ int temp = first+second; first = second; second = temp; } return second; } }
746. 使用最小花费爬楼梯
746. 使用最小花费爬楼梯
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int minCostClimbingStairs (int [] cost) { int [] dp = new int [cost.length + 1 ]; dp[0 ] = 0 ; dp[1 ] = 0 ; for (int i = 2 ; i <= cost.length; i++) { dp[i] = Math.min(dp[i - 1 ] + cost[i - 1 ], dp[i - 2 ] + cost[i - 2 ]); } return dp[dp.length - 1 ]; } }
62. 不同路径
62. 不同路径
还有究极节省内存就是用一行保存dp即可,因为其实每次只用到一行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int uniquePaths (int m, int n) { int [][] dp = new int [m][n]; for (int i = 0 ;i<m;i++){ for (int j = 0 ;j<n;j++){ if (i==0 ||j==0 ){ dp[i][j] = 1 ; continue ; } dp[i][j] = dp[i-1 ][j]+dp[i][j-1 ]; } } return dp[m-1 ][n-1 ]; } }
63. 不同路径 II
63. 不同路径 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 class Solution { public int uniquePathsWithObstacles (int [][] obstacleGrid) { int [][] dp = new int [obstacleGrid.length][obstacleGrid[0 ].length]; dp[0 ][0 ] = 1 ; for (int i = 0 ; i < obstacleGrid.length; i++) { for (int j = 0 ; j < obstacleGrid[0 ].length; j++) { if (obstacleGrid[i][j] == 1 ) { dp[i][j] = 0 ; continue ; } if (i - 1 >= 0 && j - 1 >= 0 ) { dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ]; } else if (i - 1 >= 0 ) { dp[i][j] = dp[i - 1 ][j]; } else if (j - 1 >= 0 ) { dp[i][j] = dp[i][j - 1 ]; } } } return dp[obstacleGrid.length - 1 ][obstacleGrid[0 ].length - 1 ]; } }
343. 整数拆分
343. 整数拆分
这个要借助数学知识,真看不出来,拆分后数值近似相等最后相乘是最大的
动态规划,本题关键在于理解递推公式!| LeetCode:343. 整数拆分_哔哩哔哩_bilibili
首先定义dp[i],dp[i]是指i拆分后得到的最大的乘积,i拆分为两个数的时候一个拆分为j另一个就是i-j,那三个数的时候就是j和dp[i-j],只能说恍然大悟,看视频讲的很好
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int integerBreak (int n) { int [] dp = new int [n + 1 ]; dp[2 ] = 1 ; for (int i = 3 ; i <= n; i++) { for (int j = 1 ; j <= i / 2 ; j++) { dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j])); } } return dp[n]; } }
这个也可以用贪心,这个需要数学证明合理性
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int integerBreak (int n) { if (n == 2 ) return 1 ; if (n == 3 ) return 2 ; if (n == 4 ) return 4 ; int result = 1 ; while (n > 4 ) { result *= 3 ; n -= 3 ; } result *= n; return result; } };
96. 不同的二叉搜索树
96. 不同的二叉搜索树
直接拿代码随想录官网的图过来了,大致思路下面也有,图更直观
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int numTrees (int n) { int [] dp = new int [n + 1 ]; if (n <= 2 ) { return n; } dp[0 ] = 1 ; dp[1 ] = 1 ; dp[2 ] = 2 ; for (int k = 3 ; k <= n; k++) { for (int i = 0 , j = k - 1 ; i <= k - 1 && j >= 0 ; i++, j--) { dp[k] += dp[i] * dp[j]; } } return dp[n]; } }
背包问题
01背包
46. 携带研究材料(第六期模拟笔试)
46. 携带研究材料(第六期模拟笔试) (kamacoder.com)
力扣没有01背包,这题跟01背包原题很像
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 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int m = scanner.nextInt(); int n = scanner.nextInt(); int [] weight = new int [m]; int [] values = new int [m]; for (int i = 0 ;i<m;i++){ weight[i] = scanner.nextInt(); } for (int i = 0 ;i<m;i++){ values[i] = scanner.nextInt(); } int [][] dp = new int [m][n+1 ]; for (int i = weight[0 ];i<=n;i++){ dp[0 ][i] = values[0 ]; } for (int i = 1 ;i<m;i++){ for (int j = 0 ;j<=n;j++){ if (j<weight[i]){ dp[i][j] = dp[i-1 ][j]; }else { dp[i][j] = Math.max( dp[i-1 ][j],dp[i-1 ][j-weight[i]]+values[i]); } } } System.out.println(dp[m-1 ][n]); } }
416. 分割等和子集
416. 分割等和子集
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 class Solution { public boolean canPartition (int [] nums) { int sum = 0 ; for (int i : nums) { sum += i; } if (sum % 2 != 0 ) { return false ; } sum /= 2 ; int [][] dp = new int [nums.length][sum + 1 ]; for (int i = nums[0 ]; i <= sum; i++) { dp[0 ][i] = nums[0 ]; } for (int i = 1 ; i < nums.length; i++) { for (int j = 1 ; j <= sum; j++) { if (nums[i] > j) { dp[i][j] = dp[i - 1 ][j]; } else { dp[i][j] = Math.max(dp[i - 1 ][j], nums[i] + dp[i - 1 ][j - nums[i]]); } } } return dp[nums.length - 1 ][sum] == sum ? true : false ; } }
1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II
本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了
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 class Solution { public int lastStoneWeightII (int [] stones) { int sum = 0 ; for (int i : stones) { sum += i; } int temp = sum; sum /= 2 ; int [][] dp = new int [stones.length][sum + 1 ]; for (int i = stones[0 ]; i <= sum; i++) { dp[0 ][i] = stones[0 ]; } for (int i = 1 ; i < stones.length; i++) { for (int j = 0 ; j <= sum; j++) { if (stones[i] > j) { dp[i][j] = dp[i - 1 ][j]; } else { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i - 1 ][j - stones[i]] + stones[i]); } } } return (temp - dp[stones.length - 1 ][sum]) - dp[stones.length - 1 ][sum]; } }
494. 目标和
494. 目标和
这题暴力回溯会超时,先贴出解答,后面有解析
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 class Solution { public int findTargetSumWays (int [] nums, int target) { int sum = 0 ; for (int i : nums) { sum += i; } if ((sum + target) % 2 != 0 ) { return 0 ; } if (Math.abs(target) > sum) { return 0 ; } int bagSize = (sum + target) / 2 ; int [] dp = new int [bagSize + 1 ]; dp[0 ] = 1 ; for (int i = 0 ; i < nums.length; i++) { for (int j = bagSize; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } return dp[bagSize]; } }
假设加法的总和为x,那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为,用nums装满容量为x的背包,有几种方法 。
这里的x,就是bagSize,也就是我们后面要求的背包容量。
大家看到(target + sum) / 2
应该担心计算的过程中向下取整有没有影响。
这么担心就对了,例如sum是5,target是2 的话其实就是无解的,所以:
1 2 (C++代码中,输入的S 就是题目描述的 target) if ((target + sum) % 2 == 1 ) return 0 ;
同时如果target 的绝对值已经大于sum,那么也是没有方案的。
1 if (abs (target) > sum) return 0 ;
之后拿题目例子来看,可以知道dp[i] [j]如下,但是这里dp表示的是有多少可能性,第一行需要初始化,第一列同样需要初始化
474. 一和零
474. 一和零
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 class Solution { public int findMaxForm (String[] strs, int m, int n) { int [][] dp = new int [m + 1 ][n + 1 ]; for (String str : strs) { int oneCount = 0 , zeroCount = 0 ; for (char c : str.toCharArray()) { if (c == '1' ) { oneCount++; } else { zeroCount++; } } for (int i = m; i >= zeroCount; i--) { for (int j = n; j >= oneCount; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1 ); } } } return dp[m][n]; } }
01背包基础上对滚动数组理解 其实就是把dp的二维数组压缩到一维数组
1 2 3 4 5 6 for (int i = 0 ; i < weight.size(); i++) { for (int j = bagWeight; j >= weight[i]; j--) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
这里大家发现和二维dp的写法中,遍历背包的顺序是不一样的!
二维dp遍历的时候,背包容量是从小到大,而一维dp遍历的时候,背包是从大到小。
为什么呢?
倒序遍历是为了保证物品i只被放入一次! 。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
举一个例子:物品0的重量weight[0] = 1,价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。
为什么倒序遍历,就可以保证物品只放入一次呢?
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 (dp数组已经都初始化为0)
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
那么问题又来了,为什么二维dp数组遍历的时候不用倒序呢?
因为对于二维dp,dp[i][j]都是通过上一层即dp[i - 1][j]计算而来,本层的dp[i][j]并不会被覆盖!
再来看看两个嵌套for循环的顺序,代码中是先遍历物品嵌套遍历背包容量,那可不可以先遍历背包容量嵌套遍历物品呢?
不可以!
因为一维dp的写法,背包容量一定是要倒序遍历(原因上面已经讲了),如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。
所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的! ,这一点大家一定要注意。****
完全背包
322. 零钱兑换
322. 零钱兑换
第一次的思路,时间复杂度太高
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 int coinChange (int [] coins, int amount) { int [] dp = new int [amount+1 ]; Arrays.fill(dp,amount+1 ); dp[0 ] = 0 ; for (int i = 0 ;i<coins.length;i++){ for (int j = amount;j>=coins[i];j--){ for (int k = 1 ;k<=j/coins[i];k++){ dp[j] = Math.min(dp[j],dp[j-k*coins[i]]+k); } } } return dp[amount]>amount ?-1 :dp[amount]; } }
改进
遍历 amount
的目的 :我们希望找到每个 i
金额所需的最少硬币数,外层循环从小到大依次处理每个可能的金额(从 1
到 amount
)。这样,当前金额 i
是基于之前的计算结果(dp[i - coin]
)更新的。
遍历 coins
的目的 :对于每一个金额 i
,我们要尝试所有不同面值的硬币,看看哪个硬币能让我们使用的硬币数量最少。因此,内层循环遍历每一个硬币,找到当前金额的最优解。
状态转移方程 :
1 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1 );
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int coinChange (int [] coins, int amount) { int [] dp = new int [amount+1 ]; Arrays.fill(dp,amount+1 ); dp[0 ] = 0 ; for (int i = 0 ;i<coins.length;i++){ for (int j = coins[i];j<=amount;j++){ dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1 ); } } return dp[amount]>amount ?-1 :dp[amount]; } }
518. 零钱兑换 II
518. 零钱兑换 II
忘记了为什么是这个遍历顺序就去看看思路吧
代码随想录 (programmercarl.com)
如果求组合数就是外层for循环遍历物品,内层for遍历背包(无顺序) 。
如果求排列数就是外层for遍历背包,内层for循环遍历物品(有顺序) 。
像上面的求最小数量的什么顺序都可以
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int change (int amount, int [] coins) { int [] dp = new int [amount+1 ]; dp[0 ] = 1 ; for (int coin:coins){ for (int j = coin;j<=amount;j++){ dp[j]+=dp[j-coin]; } } return dp[amount]; } }
377. 组合总和 Ⅳ
377. 组合总和 Ⅳ
这里需要考虑顺序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int combinationSum4 (int [] nums, int target) { int [] dp = new int [target + 1 ]; dp[0 ] = 1 ; for (int i = 0 ; i <= target; i++) { for (int j = 0 ; j < nums.length; j++) { if (i >= nums[j]) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; } }
JZ71 跳台阶扩展问题
跳台阶扩展问题_牛客题霸_牛客网 (nowcoder.com)
这里之前找规律类斐波那契也可以解决,这里用完全背包再解决一次罢了,跟上面代码一模一样,这里放一下斐波那契的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 import java.util.*;public class Solution { public int jumpFloorII (int number) { int lastSum = 0 , result = 0 ; for (int i = 0 ; i < number; i++) { result = lastSum + 1 ; lastSum += result; } return result; } }
279. 完全平方数
279. 完全平方数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int numSquares (int n) { int [] dp = new int [n + 1 ]; Arrays.fill(dp, n + 1 ); dp[0 ] = 0 ; for (int i = 1 ; i <= (int ) Math.sqrt(n); i++) { for (int j = i * i; j <= n; j++) { dp[j] = Math.min(dp[j], dp[j - i * i] + 1 ); } } return dp[n]; } }
139. 单词拆分
139. 单词拆分
举一反三想出来了,一次ac,双爽
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public boolean wordBreak (String s, List<String> wordDict) { int length = s.length(); boolean [] dp = new boolean [length + 1 ]; dp[0 ] = true ; for (int i = 0 ; i <= length; i++) { for (int j = 0 ; j < wordDict.size(); j++) { int wordLength = wordDict.get(j).length(); if (wordLength <= i) { dp[i] = (dp[i - wordLength] && s.substring(i - wordLength, i).equals(wordDict.get(j))) || dp[i]; } } } return dp[length]; } }
打家劫舍
198. 打家劫舍
198. 打家劫舍
1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public int rob (int [] nums) { int [] dp = new int [nums.length + 1 ]; dp[1 ] = nums[0 ]; for (int i = 2 ; i <= nums.length; i++) { dp[i] = Math.max(dp[i - 2 ] + nums[i - 1 ], dp[i - 1 ]); } return dp[nums.length]; } }
213. 打家劫舍 II
213. 打家劫舍 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 28 29 class Solution { public int rob (int [] nums) { if (nums.length==1 ){ return nums[0 ]; } int [] dp = new int [nums.length + 1 ]; dp[1 ] = nums[0 ]; for (int i = 2 ; i < nums.length; i++) { dp[i] = Math.max(dp[i - 2 ] + nums[i - 1 ], dp[i - 1 ]); } int temp = dp[nums.length-1 ]; dp = new int [nums.length+1 ]; for (int i = 2 ; i <= nums.length; i++) { dp[i] = Math.max(dp[i - 2 ] + nums[i - 1 ], dp[i - 1 ]); } temp = Math.max(temp,dp[nums.length]); return temp; } }
337. 打家劫舍 III
337. 打家劫舍 III
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 int rob (TreeNode root) { postOrder(root); return root.val; } public void postOrder (TreeNode root) { if (root == null ) { return ; } postOrder(root.left); postOrder(root.right); int l1 = 0 , l2 = 0 , r1 = 0 , r2 = 0 ; int l = 0 , r = 0 ; if (root.left != null ) { l = root.left.val; if (root.left.left != null ) { l1 = root.left.left.val; } if (root.left.right != null ) { l2 = root.left.right.val; } } if (root.right != null ) { r = root.right.val; if (root.right.left != null ) { r1 = root.right.left.val; } if (root.right.right != null ) { r2 = root.right.right.val; } } root.val = Math.max(l + r, root.val + r1 + r2 + l1 + l2); } }
股票问题
123. 买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III
不能同时参与多笔交易(必须在再次购买前出售掉之前的股票),理解初始化很重要
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 class Solution { public int maxProfit (int [] prices) { int length = prices.length; if (length <= 1 ) { return 0 ; } int [] dp = new int [4 ]; dp[0 ] = -prices[0 ]; dp[1 ] = 0 ; dp[2 ] = -prices[0 ]; dp[3 ] = 0 ; for (int i = 1 ; i < length; i++) { dp[0 ] = Math.max(dp[0 ], 0 - prices[i]); dp[1 ] = Math.max(dp[1 ], dp[0 ] + prices[i]); dp[2 ] = Math.max(dp[2 ], dp[1 ] - prices[i]); dp[3 ] = Math.max(dp[3 ], dp[2 ] + prices[i]); } return dp[3 ]; } }
188. 买卖股票的最佳时机 IV
188. 买卖股票的最佳时机 IV
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int maxProfit (int k, int [] prices) { int [] dp = new int [2 * k + 1 ]; dp[0 ] = 0 ; for (int j = 1 ; j <= k; j++) { dp[j * 2 - 1 ] = -prices[0 ]; dp[j * 2 ] = 0 ; } for (int i = 1 ; i < prices.length; i++) { for (int j = 1 ; j <= k; j++) { dp[j * 2 - 1 ] = Math.max(dp[j * 2 - 1 ], dp[j * 2 - 2 ] - prices[i]); dp[j * 2 ] = Math.max(dp[j * 2 ], dp[j * 2 - 1 ] + prices[i]); } } return dp[2 * k]; } }
309. 买卖股票的最佳时机含冷冻期
309. 买卖股票的最佳时机含冷冻期
结合前面几题理解不同状态的设置,突然恍然大悟
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 class Solution { public int maxProfit (int [] prices) { int length = prices.length; if (length <= 1 ) { return 0 ; } int [][] dp = new int [length][4 ]; dp[0 ][0 ] = -prices[0 ]; for (int i = 1 ; i < length; i++) { dp[i][0 ] = Math.max(dp[i - 1 ][0 ], Math.max(dp[i - 1 ][2 ] - prices[i], dp[i - 1 ][3 ] - prices[i])); dp[i][1 ] = dp[i - 1 ][0 ] + prices[i]; dp[i][2 ] = Math.max(dp[i - 1 ][2 ], dp[i - 1 ][3 ]); dp[i][3 ] = dp[i - 1 ][1 ]; } return Math.max(dp[length - 1 ][1 ], Math.max(dp[length - 1 ][2 ], dp[length - 1 ][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 class Solution { public int maxProfit (int [] prices) { int length = prices.length; if (length <= 1 ) { return 0 ; } int [] dp = new int [4 ]; dp[0 ] = -prices[0 ]; for (int i = 1 ; i < length; i++) { int oldZero = dp[0 ]; int oldFirst = dp[1 ]; dp[0 ] = Math.max(dp[0 ], Math.max(dp[2 ] - prices[i], dp[3 ] - prices[i])); dp[1 ] = oldZero + prices[i]; dp[2 ] = Math.max(dp[2 ], dp[3 ]); dp[3 ] = oldFirst; } return Math.max(dp[1 ], Math.max(dp[2 ], dp[3 ])); } }
子序列问题 子序列(不连续)
300. 最长递增子序列
300. 最长递增子序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int lengthOfLIS (int [] nums) { int [] dp = new int [nums.length]; for (int i = 0 ; i < nums.length; i++) { int temp = 1 ; for (int j = i - 1 ; j >= 0 ; j--) { if (nums[i] > nums[j]) { temp = Math.max(temp, dp[j] + 1 ); } } dp[i] = temp; } int result = 1 ; for (int i : dp) { result = Math.max(result, i); } return result; } }
1143. 最长公共子序列
1143. 最长公共子序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int longestCommonSubsequence (String text1, String text2) { int [][] dp = new int [text1.length() + 1 ][text2.length() + 1 ]; for (int i = 0 ; i < text1.length(); i++) { for (int j = 0 ; j < text2.length(); j++) { if (text1.charAt(i) == text2.charAt(j)) { dp[i + 1 ][j + 1 ] = Math.max(dp[i][j] + 1 , dp[i][j + 1 ]); } else { dp[i + 1 ][j + 1 ] = Math.max(dp[i + 1 ][j], dp[i][j + 1 ]); } } } return dp[text1.length()][text2.length()]; } }
时间复杂度和空间复杂度比较高,优化
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 class Solution { public int longestCommonSubsequence (String text1, String text2) { int [] dp = new int [text2.length() + 1 ]; for (int i = 1 ; i <= text1.length(); i++) { int last = dp[0 ]; for (int j = 1 ; j <= text2.length(); j++) { int cur = dp[j]; if (text1.charAt(i - 1 ) == text2.charAt(j - 1 )) { dp[j] = last + 1 ; } else { dp[j] = Math.max(dp[j], dp[j - 1 ]); } last = cur; } } return dp[text2.length()]; } }
1035. 不相交的线
1035. 不相交的线
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 class Solution { public int maxUncrossedLines (int [] nums1, int [] nums2) { int [] dp = new int [nums2.length + 1 ]; for (int i = 1 ; i <= nums1.length; i++) { int last = dp[0 ]; for (int j = 1 ; j <= nums2.length; j++) { int cur = dp[j]; if (nums1[i - 1 ] == nums2[j - 1 ]) { dp[j] = last + 1 ; } else { dp[j] = Math.max(dp[j], dp[j - 1 ]); } last = cur; } } return dp[nums2.length]; } }
子序列(连续)
674. 最长连续递增序列
674. 最长连续递增序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int findLengthOfLCIS (int [] nums) { int result = 1 ,temp = 1 ,last = nums[0 ]; for (int i = 1 ;i<nums.length;i++){ if (nums[i]>last){ result = Math.max(result,++temp); }else { temp = 1 ; } last = nums[i]; } return result; } }
动规就是大于前一个就前一个的dp+1,不然就是1,可以初始化全为1,也可以贪心保存最大,不然就是回去遍历一遍找到最大的,简单,不写了,看到这题肯定贪心的
718. 最长重复子数组
718. 最长重复子数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int findLength (int [] nums1, int [] nums2) { int result = 0 ; int [] dp = new int [nums2.length + 1 ]; for (int i = 0 ; i < nums1.length; i++) { for (int j = nums2.length - 1 ; j >= 0 ; j--) { if (nums1[i] == nums2[j]) { dp[j + 1 ] = dp[j] + 1 ; result = Math.max(result, dp[j + 1 ]); } else { dp[j + 1 ] = 0 ; } } } return result; } }
编辑距离
392. 判断子序列
392. 判断子序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public boolean isSubsequence (String s, String t) { int len1 = s.length(), len2 = t.length(); int i = 0 , j = 0 ; while (i != len1 && j != len2) { if (s.charAt(i) == t.charAt(j)) { i++; j++; } else { j++; } } return i == len1; } }
动规
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public boolean isSubsequence (String s, String t) { int [][] dp = new int [s.length() + 1 ][t.length() + 1 ]; for (int i = 1 ; i <= s.length(); i++) { for (int j = 1 ; j <= t.length(); j++) { if (s.charAt(i - 1 ) == t.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = dp[i][j - 1 ]; } } } return s.length() == dp[s.length()][t.length()]; } }
583. 两个字符串的删除操作
583. 两个字符串的删除操作
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 class Solution { public int minDistance (String word1, String word2) { int [][] dp = new int [word1.length() + 1 ][word2.length() + 1 ]; for (int i = 1 ; i <= word1.length(); i++) { for (int j = 1 ; j <= word2.length(); j++) { if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i][j - 1 ]); } } } int max = dp[word1.length()][word2.length()]; return word1.length() - max + word2.length() - max; } }
上面取巧,下面思路
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 class Solution { public int minDistance (String word1, String word2) { int [][] dp = new int [word1.length() + 1 ][word2.length() + 1 ]; for (int i = 0 ; i < word1.length() + 1 ; i++) dp[i][0 ] = i; for (int j = 0 ; j < word2.length() + 1 ; j++) dp[0 ][j] = j; for (int i = 1 ; i <= word1.length(); i++) { for (int j = 1 ; j <= word2.length(); j++) { if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ]; } else { dp[i][j] = Math.min(dp[i - 1 ][j], dp[i][j - 1 ]) + 1 ; } } } return dp[word1.length()][word2.length()]; } }
72. 编辑距离
72. 编辑距离
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 class Solution { public int minDistance (String word1, String word2) { int [][] dp = new int [word1.length() + 1 ][word2.length() + 1 ]; for (int i = 1 ; i <= word1.length(); i++) { dp[i][0 ] = i; } for (int j = 1 ; j <= word2.length(); j++) { dp[0 ][j] = j; } for (int i = 1 ; i <= word1.length(); i++) { for (int j = 1 ; j <= word2.length(); j++) { if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ]; } else { dp[i][j] = Math.min(dp[i - 1 ][j], dp[i][j - 1 ]) + 1 ; dp[i][j] = Math.min(dp[i][j], dp[i - 1 ][j - 1 ] + 1 ); } } } return dp[word1.length()][word2.length()]; } }
115. 不同的子序列
115. 不同的子序列
如果本题是求连续序列,就可以考虑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 class Solution { public int numDistinct (String s, String t) { int [][] dp = new int [s.length() + 1 ][t.length() + 1 ]; for (int i = 0 ; i <= s.length(); i++) { dp[i][0 ] = 1 ; } for (int i = 1 ; i <= s.length(); i++) { for (int j = 1 ; j <= t.length(); j++) { if (s.charAt(i - 1 ) == t.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ] + dp[i - 1 ][j]; } else { dp[i][j] = dp[i - 1 ][j]; } } } return dp[s.length()][t.length()]; } }
回文
647. 回文子串
647. 回文子串
动态规划写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int countSubstrings (String s) { int result = 0 ; boolean [][] dp = new boolean [s.length()][s.length()]; for (int i = s.length() - 1 ; i >= 0 ; i--) { for (int j = i; j < s.length(); j++) { if (s.charAt(i) == s.charAt(j)) { if (i == j || j - i == 1 || dp[i + 1 ][j - 1 ]) { result++; dp[i][j] = true ; } } } } return result; } }
双指针,时间复杂度和空间复杂度都更低
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int countSubstrings (String s) { int result = 0 ; for (int i = 0 ;i<s.length();i++){ result+=caculate(s,i,i); result+=caculate(s,i,i+1 ); } return result; } public int caculate (String s,int left,int right) { int count = 0 ; while (left>=0 &&right<s.length()&&s.charAt(left)==s.charAt(right)){ count++; left--; right++; } return count; } }
516. 最长回文子序列
516. 最长回文子序列
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 class Solution { public int longestPalindromeSubseq (String s) { int [][] dp = new int [s.length()][s.length()]; for (int i = s.length() - 1 ; i >= 0 ; i--) { for (int j = i; j < s.length(); j++) { if (s.charAt(i) == s.charAt(j)) { if (i == j) { dp[i][j] = 1 ; } else if (j - i == 1 ) { dp[i][j] = 2 ; } else if (j - i > 1 ) { dp[i][j] = dp[i + 1 ][j - 1 ] + 2 ; } } else { if (j - i == 1 ) { dp[i][j] = 1 ; } else { dp[i][j] = Math.max(dp[i + 1 ][j], dp[i][j - 1 ]); } } } } return dp[0 ][s.length() - 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 class Solution { public int longestPalindromeSubseq (String s) { int [][] dp = new int [s.length() + 1 ][s.length() + 1 ]; for (int i = s.length() - 1 ; i >= 0 ; i--) { dp[i][i] = 1 ; for (int j = i + 1 ; j < s.length(); j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1 ][j - 1 ] + 2 ; } else { dp[i][j] = Math.max(dp[i][j], Math.max(dp[i + 1 ][j], dp[i][j - 1 ])); } } } return dp[0 ][s.length() - 1 ]; } }
数位dp
面试题 17.06. 2出现的次数
面试题 17.06. 2出现的次数
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 class Solution { int [][][] memory; public int numberOf2sInRange (int n) { String s = String.valueOf(n); memory = new int [s.length()][s.length()][2 ]; for (int [][] nums : memory) { for (int [] init : nums) { Arrays.fill(init, -1 ); } } return dp(0 , s, 0 , false ); } public int dp (int solve, String target, int count, boolean isCanSelectedRandom) { if (solve == target.length()) { return count; } if (memory[solve][count][isCanSelectedRandom ? 1 : 0 ] != -1 ) { return memory[solve][count][isCanSelectedRandom ? 1 : 0 ]; } int res = 0 ; int limit = isCanSelectedRandom ? 9 : target.charAt(solve) - '0' ; for (int i = 0 ; i <= limit; i++) { int cnt = count + ((i == 2 ) ? 1 : 0 ); res += dp(solve + 1 , target, cnt, isCanSelectedRandom || i < limit); } memory[solve][count][isCanSelectedRandom ? 1 : 0 ] = res; return res; } }
233. 数字 1 的个数
233. 数字 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 37 38 39 40 41 42 43 class Solution { int [][][] memory; public int countDigitOne (int n) { String s = String.valueOf(n); memory = new int [s.length()][s.length()][2 ]; for (int [][] init : memory) { for (int [] init1 : init) { Arrays.fill(init1, -1 ); } } return dp(s, 0 , 0 , false ); } public int dp (String s, int deep, int count, boolean isCanSelectRandom) { if (deep == s.length()) { return count; } if (memory[deep][count][isCanSelectRandom ? 1 : 0 ] != -1 ) { return memory[deep][count][isCanSelectRandom ? 1 : 0 ]; } int limit = isCanSelectRandom ? 9 : s.charAt(deep) - '0' ; int ans = 0 ; for (int i = 0 ; i <= limit; i++) { ans += dp(s, deep + 1 , count + (i == 1 ? 1 : 0 ), isCanSelectRandom || (i < limit)); } memory[deep][count][isCanSelectRandom ? 1 : 0 ] = ans; return ans; } }
图论 理论 基本理论 图论理论基础 | 代码随想录 (programmercarl.com)
任何两个节点都是可以到达的
无向图 连通图
有向图 强连通图
在无向图中的极大连通子图称之为该图的一个连通分量
在有向图中极大强连通子图称之为该图的强连通分量
构建
邻接矩阵 邻阶表
并查集理论 并查集常用来解决连通性问题,并查集主要有两个功能,第一个功能是将两个元素添加到一个集合中,第二个功能是判断两个元素在不在同一个集合。
并查集理论基础 | 代码随想录
1. 首先知道怎么表示并查集
这里用个一维数组表示就好,比如1->2,那么parent[2] = 1,表示2的parent也就是来者是1
所以说用一个一维数组表示就好,每个位置代表这个下标对应节点的parent
那怎么初始化呢?自己来自自己呗
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class DisJoint { private int [] father; public DisJoint (int size) { father = new int [size+1 ]; init(); } private void init () { for (int i = 1 ;i<father.length;i++){ father[i] = i; } } }
2. 之后就要知道并查集是怎么查找parent的
根据并查集的表示方式,怎么知道到根了呢,自然就是i = parent[i],没得父亲找了,不然比如parent[1] = 2,那么就可以往2下标去找,parent[2] = 5,之后还要往5去找,parent[5] = 5,那么就到头了,可以找到1的root为5,也就是5->2->1是路径
那本次查找后就发现了,我要找5的root为1,2的root也为1,那是不是可以优化,也就是压缩路径呢,下次找5可以直接输出1即可,在递归中如果parent[i]!=i,就可以进行优化,是当然直接返回就好了
1 2 3 4 5 public int find (int u) { return u == father[u] ? father[u] : (father[u] = find(father[u])); }
3. 下一步就是要知道怎么加入并查集了
要加入并查集有两个值一个为u,一个为v,其中u->v,那么并查集是表示可以连通的在一个集合中,如果这两个已经连通了就没必要加入了,不连通才需要去加入,说明有新连通,那么怎么判断是否在同一个集合,就找两个都root看是不是一样就好
1 2 3 4 5 6 7 8 9 10 public void join (int u, int v) { u = find(u); v = find(v); if (u!=v){ father[v] = u; } }
4. 之后就是要判断两个节点是否是连通的
跟第三部分差不多,看两个节点的parent是否相等就行,上面的备注写的很清楚了,两个不同的时候加入并查集是让parent相连,而不是u和v相连,所以在join不能直接调用这个方法判断是否相连就让u和v相连
1 2 3 4 public boolean isSame (int u, int v) { return find(u) == find(v); }
整个类就是并查集的模板代码了,复制粘贴就好
下面看一下深搜和广搜在使用上的区别,广搜是用来解决最短路径问题的,深搜就没那么好用了,深搜就是回溯,一路到头再回来。下面用一道例题感受两者的区别就好
深搜
98. 所有可达路径
98. 所有可达路径 (kamacoder.com)
邻接矩阵写法
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 import java.util.Scanner;import java.util.ArrayList;import java.util.List;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); int [][] graph = new int [n+1 ][n+1 ]; while (m!=0 ){ graph[scanner.nextInt()][scanner.nextInt()] = 1 ; m--; } List<String>result= new ArrayList <>(); List<Integer>temp = new ArrayList <>(); boolean [] isVisited = new boolean [n+1 ]; temp.add(1 ); isVisited[1 ] = true ; backTracking(result,temp,n,graph,isVisited,1 ); if (result.isEmpty()){ System.out.println("-1" ); return ; } for (int i = 0 ;i<result.size();i++){ System.out.println(result.get(i)); } } public static void backTracking (List<String>result,List<Integer>temp,int n,int [][] graph,boolean [] isVisited,int point) { if (point==n){ StringBuilder builder = new StringBuilder (); for (int i = 0 ;i<temp.size();i++){ builder.append(temp.get(i)); builder.append(" " ); } result.add(builder.toString().trim()); return ; } for (int i = 1 ;i<=n;i++){ if (!isVisited[i]&&graph[point][i]==1 ){ isVisited[i] = true ; temp.add(i); backTracking(result,temp,n,graph,isVisited,i); temp.remove(temp.size()-1 ); isVisited[i] = 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 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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); List<LinkedList<Integer>>graph = new ArrayList <>(); for (int i = 0 ;i<=n;i++){ graph.add(new LinkedList <>()); } while (m!=0 ){ m--; graph.get(scanner.nextInt()).add(scanner.nextInt()); } List<String>result = new ArrayList <>(); List<Integer>path = new ArrayList <>(); path.add(1 ); backTracking(n,result,path,graph,1 ); if (result.isEmpty()){ System.out.println("-1" ); return ; } for (String s:result){ System.out.println(s); } } public static void backTracking (int n, List<String>result,List<Integer>path,List<LinkedList<Integer>>graph,int point) { if (point==n){ StringBuilder builder = new StringBuilder (); for (int i : path){ builder.append(i); builder.append(" " ); } result.add(builder.toString().trim()); return ; } for (int i:graph.get(point)){ path.add(i); backTracking(n,result,path,graph,i); path.remove(path.size()-1 ); } } }
99. 岛屿数量
99. 岛屿数量 (kamacoder.com)
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 import java.util.*;public class Main { public static int [][] dir = new int [][]{{1 ,0 },{-1 ,0 },{0 ,-1 },{0 ,1 }}; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); int [][] graph = new int [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ graph[i][j] = scanner.nextInt(); } } int result = 0 ; boolean [][] isVisited = new boolean [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (!isVisited[i][j]&&graph[i][j]==1 ){ result++; dfs(graph,isVisited,n,m,i,j); } } } System.out.println(result); } public static void dfs (int [][]graph,boolean [][] isVisited,int n,int m,int i,int j) { isVisited[i][j] = true ; for (int k = 0 ;k<4 ;k++){ int nextI = i+dir[k][0 ]; int nextJ = j+dir[k][1 ]; if (nextI>=0 &&nextI<n&&nextJ>=0 &&nextJ<m&&!isVisited[nextI][nextJ]&&graph[i][j]==1 ){ dfs(graph,isVisited,n,m,nextI,nextJ); } } } }
广搜
99. 岛屿数量
99. 岛屿数量 (kamacoder.com)
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 65 import java.util.*;public class Main { public static int [][] dir = new int [][]{{1 ,0 },{-1 ,0 },{0 ,-1 },{0 ,1 }}; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); int [][] graph = new int [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ graph[i][j] = scanner.nextInt(); } } int result = 0 ; boolean [][] isVisited = new boolean [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (!isVisited[i][j]&&graph[i][j]==1 ){ result++; bfs(graph,isVisited,i,j,n,m); } } } System.out.println(result); } public static void bfs (int [][] graph,boolean [][] isVisited,int i,int j,int n,int m) { Queue<int []>queue = new LinkedList <>(); queue.offer(new int []{i,j}); isVisited[i][j] = true ; while (!queue.isEmpty()){ int [] cur = queue.poll(); int curI = cur[0 ],curJ = cur[1 ]; for (int t = 0 ;t<4 ;t++){ int nextI = curI + dir[t][0 ], nextJ = curJ + dir[t][1 ]; if (nextI>=0 && nextI<n && nextJ>=0 && nextJ<m && !isVisited[nextI][nextJ] && graph[nextI][nextJ]==1 ){ queue.offer(new int []{nextI,nextJ}); isVisited[nextI][nextJ] = true ; } } } } }
110. 字符串接龙
110. 字符串接龙
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 65 66 67 68 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int N = scanner.nextInt(); scanner.nextLine(); String[] words = scanner.nextLine().split(" " ); List<String>dic = new ArrayList <>(); for (int i = 0 ;i<N;i++){ dic.add(scanner.nextLine()); } System.out.println(bfs(dic,words[0 ],words[1 ])); } public static int bfs (List<String> dic, String beginWord, String endWord) { Queue<String>queue = new LinkedList <>(); HashMap<String,Integer>map = new HashMap <>(); HashSet<String>set = new HashSet <>(dic); queue.offer(beginWord); map.put(beginWord,1 ); while (!queue.isEmpty()){ String curStr = queue.poll(); int path = map.get(curStr); for (int i = 0 ;i<curStr.length();i++){ char [] chars = curStr.toCharArray(); for (char c = 'a' ;c<='z' ;c++){ chars[i] = c; String s = new String (chars); if (s.equals(endWord)){ return path+1 ; } if (set.contains(s)&&!map.containsKey(s)){ queue.offer(s); map.put(s,path+1 ); } } } } return 0 ; } }
题目
105. 有向图的完全可达性
105. 有向图的完全可达性
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 65 66 67 68 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(), k = scanner.nextInt(); List<List<Integer>>graph = new ArrayList <>(); for (int i = 0 ;i<=n;i++){ graph.add(new LinkedList <>()); } for (int i = 0 ;i<k;i++){ graph.get(scanner.nextInt()).add(scanner.nextInt()); } boolean [] isVisited = new boolean [n+1 ]; bfs(graph,isVisited); for (int i = 1 ;i<=n;i++){ if (!isVisited[i]){ System.out.println(-1 ); return ; } } System.out.println(1 ); } public static void dfs (List<List<Integer>>graph, boolean [] isVisited, int point) { isVisited[point] = true ; for (int i : graph.get(point)){ if (!isVisited[i]){ dfs(graph,isVisited,i); } } } public static void bfs (List<List<Integer>>graph, boolean [] isVisited) { Queue<Integer>queue = new LinkedList <>(); queue.offer(1 ); isVisited[1 ] = true ; while (!queue.isEmpty()){ int point = queue.poll(); for (int i : graph.get(point)){ if (!isVisited[i]){ queue.offer(i); isVisited[i] = true ; } } } } }
100. 岛屿的最大面积
100. 岛屿的最大面积 (kamacoder.com)
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 import java.util.*;public class Main { public static int [][] dir = new int [][]{{1 ,0 },{-1 ,0 },{0 ,-1 },{0 ,1 }}; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); int [][] graph = new int [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ graph[i][j] = scanner.nextInt(); } } boolean [][] isVisited = new boolean [n][m]; int result = 0 ; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (!isVisited[i][j]&&graph[i][j]==1 ){ result = Math.max(result,dfs(graph,isVisited,n,m,i,j)); } } } System.out.println(result); } public static int dfs (int [][] graph,boolean [][] isVisited,int n,int m,int i,int j) { isVisited[i][j] = true ; int result = 1 ; for (int k = 0 ;k<4 ;k++){ int nextI = i+dir[k][0 ]; int nextJ = j+dir[k][1 ]; if (nextI>=0 &&nextI<n&&nextJ>=0 &&nextJ<m&&!isVisited[nextI][nextJ]&&graph[nextI][nextJ]==1 ){ result+=dfs(graph,isVisited,n,m,nextI,nextJ); } } return result; } }
101. 孤岛的总面积
101. 孤岛的总面积 (kamacoder.com)
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 import java.util.*;public class Main { public static int [][] dir = new int [][]{{1 ,0 },{-1 ,0 },{0 ,-1 },{0 ,1 }}; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); int [][] graph = new int [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ graph[i][j] = scanner.nextInt(); } } int result = 0 ; for (int i = 0 ;i<n;i++){ if (graph[i][0 ]==1 ){ dfs(graph,n,m,i,0 ); } if (graph[i][m-1 ]==1 ){ dfs(graph,n,m,i,m-1 ); } } for (int j = 0 ;j<m;j++){ if (graph[0 ][j]==1 ){ dfs(graph,n,m,0 ,j); } if (graph[n-1 ][j]==1 ){ dfs(graph,n,m,n-1 ,j); } } for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (graph[i][j]==1 ){ result += dfs(graph,n,m,i,j); } } } System.out.println(result); } public static int dfs (int [][] graph,int n,int m,int i,int j) { int result = 1 ; graph[i][j] = 0 ; for (int k = 0 ;k<4 ;k++){ int nextI = i+dir[k][0 ]; int nextJ = j+dir[k][1 ]; if (nextI>=0 &&nextI<n&&nextJ>=0 &&nextJ<m&&graph[nextI][nextJ]==1 ){ result+=dfs(graph,n,m,nextI,nextJ); } } return result; } }
102. 沉没孤岛
102. 沉没孤岛 (kamacoder.com)
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 import java.util.*;public class Main { public static int [][] dir = new int [][]{{1 ,0 },{-1 ,0 },{0 ,-1 },{0 ,1 }}; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); int [][] graph = new int [n][m]; int [][] result = new int [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ graph[i][j] = scanner.nextInt(); result[i][j] = graph[i][j]; } } for (int i = 0 ;i<n;i++){ if (graph[i][0 ]==1 ){ dfs(graph,n,m,i,0 ); } if (graph[i][m-1 ]==1 ){ dfs(graph,n,m,i,m-1 ); } } for (int j = 0 ;j<m;j++){ if (graph[0 ][j]==1 ){ dfs(graph,n,m,0 ,j); } if (graph[n-1 ][j]==1 ){ dfs(graph,n,m,n-1 ,j); } } for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (graph[i][j]==1 ){ result[i][j] = 0 ; } } } for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ System.out.print(result[i][j]); System.out.print(" " ); } System.out.println(); } } public static int dfs (int [][] graph,int n,int m,int i,int j) { int result = 1 ; graph[i][j] = 0 ; for (int k = 0 ;k<4 ;k++){ int nextI = i+dir[k][0 ]; int nextJ = j+dir[k][1 ]; if (nextI>=0 &&nextI<n&&nextJ>=0 &&nextJ<m&&graph[nextI][nextJ]==1 ){ result+=dfs(graph,n,m,nextI,nextJ); } } return result; } }
103. 水流问题
103. 水流问题 (kamacoder.com)
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 65 66 67 68 69 70 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(),m = scanner.nextInt(); int [][] graph = new int [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ graph[i][j] = scanner.nextInt(); } } boolean [][] first = new boolean [n][m]; boolean [][] second = new boolean [n][m]; for (int i = 0 ;i<n;i++){ dfs(graph,first,n,m,i,0 ,Integer.MIN_VALUE); dfs(graph,second,n,m,i,m-1 ,Integer.MIN_VALUE); } for (int i = 0 ;i<m;i++){ dfs(graph,first,n,m,0 ,i,Integer.MIN_VALUE); dfs(graph,second,n,m,n-1 ,i,Integer.MIN_VALUE); } List<List<Integer>>result = new ArrayList <>(); for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (first[i][j]&&second[i][j]){ result.add(Arrays.asList(i,j)); } } } for (List<Integer>list:result){ System.out.print(list.get(0 )); System.out.print(" " ); System.out.println(list.get(1 )); } } public static void dfs (int [][] graph,boolean [][] isVisited,int n,int m,int i,int j,int pre) { if (i>=0 && i<n && j>=0 && j<m && !isVisited[i][j] && pre<=graph[i][j]){ isVisited[i][j] = true ; dfs(graph,isVisited,n,m,i+1 ,j,graph[i][j]); dfs(graph,isVisited,n,m,i-1 ,j,graph[i][j]); dfs(graph,isVisited,n,m,i,j-1 ,graph[i][j]); dfs(graph,isVisited,n,m,i,j+1 ,graph[i][j]); } } }
104. 建造最大岛屿 104. 建造最大岛屿
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 import java.util.*;public class Main { public static int size = 0 ; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int m = scanner.nextInt(),n = scanner.nextInt(); int [][] graph = new int [m][n]; for (int i = 0 ;i<m;i++){ for (int j = 0 ;j<n;j++){ graph[i][j] = scanner.nextInt(); } } int max = 0 ; int mark = 2 ; HashMap<Integer,Integer>map = new HashMap <>(); boolean [][] isVisited = new boolean [m][n]; for (int i = 0 ;i<m;i++){ for (int j = 0 ;j<n;j++){ if (!isVisited[i][j]&&graph[i][j]==1 ){ size = 0 ; dfs(graph,m,n,i,j,mark,isVisited); map.put(mark,size); mark++; max = Math.max(max,size); } } } for (int i = 0 ;i<m;i++){ for (int j = 0 ;j<n;j++){ if (graph[i][j]==0 ){ max = Math.max(max,caculateArea(graph,map,i,j,m,n)); } } } System.out.println(max); } public static int caculateArea (int [][] graph,HashMap<Integer,Integer>map,int i,int j,int m,int n) { int result = 0 ; HashSet<Integer>set = new HashSet <>(); for (int t = 0 ;t<4 ;t++){ i+=dir[t][0 ]; j+=dir[t][1 ]; if (i<0 ||i>=m||j<0 ||j>=n||graph[i][j]==0 ){ i-=dir[t][0 ]; j-=dir[t][1 ]; continue ; } if (set.add(graph[i][j])){ result+=map.get(graph[i][j]); } i-=dir[t][0 ]; j-=dir[t][1 ]; } result+=1 ; return result; } public static int [][] dir = new int [][]{{-1 ,0 },{1 ,0 },{0 ,-1 },{0 ,1 }}; public static void dfs (int [][] graph,int m,int n,int i,int j,int mark,boolean [][] isVisited) { if (i<0 ||i>=m||j<0 ||j>=n||isVisited[i][j]||graph[i][j]==0 ){ return ; } size++; isVisited[i][j] = true ; graph[i][j] = mark; for (int t = 0 ;t<4 ;t++){ dfs(graph,m,n,i+dir[t][0 ],j+dir[t][1 ],mark,isVisited); } } }
避免惯性思维引入 不是看到图就是广搜和深搜了
106. 岛屿的周长
106. 岛屿的周长
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(), m = scanner.nextInt(); int [][] graph = new int [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ graph[i][j] = scanner.nextInt(); } } int result = 0 ; int [][] dir = new int [][]{{-1 ,0 },{1 ,0 },{0 ,-1 },{0 ,1 }}; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (graph[i][j]==1 ){ for (int t = 0 ;t<4 ;t++){ int tempI = i + dir[t][0 ], tempJ = j + dir[t][1 ]; if (tempI<0 ||tempI>=n||tempJ<0 ||tempJ>=m||graph[tempI][tempJ]==0 ){ result++; } } } } } System.out.println(result); } }
并查集题目
107. 寻找存在的路径
107. 寻找存在的路径
当然深搜也是能过的,但是并查集思想更快
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 import java.util.*;public class Main { public static boolean isCanArrival = false ; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(), m = scanner.nextInt(); List<List<Integer>>graph = new ArrayList <>(); for (int i = 0 ;i<=n;i++){ graph.add(new LinkedList <>()); } for (int i = 0 ;i<m;i++){ int start = scanner.nextInt(), end = scanner.nextInt(); graph.get(start).add(end); graph.get(end).add(start); } int begin = scanner.nextInt(), destination = scanner.nextInt(); boolean [] isVisited = new boolean [n+1 ]; dfs(graph,isVisited,begin,destination); System.out.println(isCanArrival?1 :0 ); } public static void dfs (List<List<Integer>>graph, boolean [] isVisited, int point, int target) { if (point==target){ isCanArrival = true ; return ; } for (int i : graph.get(point)){ if (!isVisited[i]){ isVisited[i] = true ; dfs(graph,isVisited,i,target); } } } }
并查集解法
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(), m = scanner.nextInt(); DisJoint disJoint = new DisJoint (n); for (int i = 0 ;i<m;i++){ disJoint.join(scanner.nextInt(), scanner.nextInt()); } if (disJoint.isSame(scanner.nextInt(), scanner.nextInt())){ System.out.println(1 ); }else { System.out.println(0 ); } } } class DisJoint { private int [] father; public DisJoint (int size) { father = new int [size+1 ]; init(); } private void init () { for (int i = 1 ;i<father.length;i++){ father[i] = i; } } public int find (int u) { return u == father[u] ? father[u] : (father[u] = find(father[u])); } public void join (int u, int v) { u = find(u); v = find(v); if (u!=v){ father[v] = u; } } public boolean isSame (int u, int v) { return find(u) == find(v); } }
108. 冗余连接
108. 冗余连接
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); DisJoint disJoint = new DisJoint (n); for (int i = 0 ;i<n;i++){ int u = scanner.nextInt(), v = scanner.nextInt(); if (disJoint.isSame(u, v)){ System.out.printf("%d %d" ,u,v); return ; }else { disJoint.join(u,v); } } } } class DisJoint { private int [] father; public DisJoint (int size) { father = new int [size+1 ]; init(); } private void init () { for (int i = 1 ;i<father.length;i++){ father[i] = i; } } public int find (int u) { return u == father[u] ? u : (father[u] = find(father[u])) ; } public void join (int u, int v) { u = find(u); v = find(v); if (u!=v){ father[v] = u; } } public boolean isSame (int u, int v) { return find(u) == find(v); } }
109. 冗余连接II
109. 冗余连接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 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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 import java.util.*;public class Main { public static List<int []>graph; public static int [] edge; public static int [] father; public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); graph = new ArrayList <>(); edge = new int [n+1 ]; for (int i = 0 ;i<n;i++){ int begin = scanner.nextInt(), end = scanner.nextInt(); graph.add(new int []{begin, end}); edge[end]++; } List<Integer>solve = new ArrayList <>(); for (int i = n-1 ;i>=0 ;i--){ if (edge[graph.get(i)[1 ]]==2 ){ solve.add(i); } } father = new int [n+1 ]; if (solve.size()>1 ){ if (isTreeAfterDelete(solve.get(0 ))){ System.out.printf("%d %d" , graph.get(solve.get(0 ))[0 ],graph.get(solve.get(0 ))[1 ]); }else { System.out.printf("%d %d" , graph.get(solve.get(1 ))[0 ],graph.get(solve.get(1 ))[1 ]); } } else { removeCircle(); } } public static void init () { for (int i = 1 ;i<father.length;i++){ father[i] = i; } } public static int find (int u) { return u == father[u] ? u : (father[u] = find(father[u])); } public static void join (int u, int v) { u = find(u); v = find(v); if (u!=v){ father[v] = u; } } public static boolean isSame (int u, int v) { return find(u) == find(v); } public static boolean isTreeAfterDelete (int deleteEdge) { init(); for (int i = 0 ;i<graph.size();i++){ if (deleteEdge==i){ continue ; } if (isSame(graph.get(i)[0 ],graph.get(i)[1 ])){ return false ; } join(graph.get(i)[0 ],graph.get(i)[1 ]); } return true ; } public static void removeCircle () { init(); for (int i = 0 ;i<graph.size();i++){ if (isSame(graph.get(i)[0 ],graph.get(i)[1 ])){ System.out.printf("%d %d" , graph.get(i)[0 ],graph.get(i)[1 ]); return ; }else { join(graph.get(i)[0 ],graph.get(i)[1 ]); } } } }
一些知识 Java常用容器 Java 提供了丰富的容器类(集合类)用于存储和操作数据。以下是一些常用的 Java 容器类,它们主要位于 java.util
包中,可以根据需要选择合适的容器:
List(列表)接口及其实现类 List
是一种有序的容器,允许重复元素。
Set(集合)接口及其实现类
Set
是一种无序且不允许重复元素的容器。
HashSet :
基于哈希表实现,允许 null
值,元素无序。
添加、删除、查找的时间复杂度为 O(1)(假设哈希冲突少)。
1 Set<String> set = new HashSet <>();
LinkedHashSet :
基于哈希表和链表实现,维护元素的插入顺序。
添加、删除、查找的时间复杂度和 HashSet
一样为 O(1),但会占用更多内存来维护顺序。
1 Set<String> set = new LinkedHashSet <>();
TreeSet :
基于红黑树(自平衡二叉树)实现,元素是有序的。
添加、删除、查找的时间复杂度为 O(log n),适合需要排序的场景。
1 Set<String> set = new TreeSet <>();
Map(映射)接口及其实现类
Map
是一种键值对(key-value)的映射结构,其中键不能重复。
Queue(队列)接口及其实现类
Queue
是一种先进先出(FIFO)的容器。
LinkedList (作为队列实现):
可以作为 Queue
实现,提供队列操作如 offer()
, poll()
, peek()
等。
1 Queue<String> queue = new LinkedList <>();
PriorityQueue :
基于堆(优先队列)实现,元素根据自然顺序或自定义比较器排序。
每次出队操作都是取优先级最高的元素。
1 Queue<Integer> queue = new PriorityQueue <>();
Deque(双端队列)接口及其实现类
Deque
是一种双端队列,允许在两端进行插入和删除操作。
LinkedList (作为 Deque
实现):
1 Deque<String> deque = new LinkedList <>();
ArrayDeque :
基于动态数组实现,作为双端队列的高效实现。
比 LinkedList
更快,且不允许 null
元素。
1 Deque<String> deque = new ArrayDeque <>();
Stack(栈)类
Stack
(继承自 Vector,较老的栈实现):
线程安全,基于 Vector
实现,遵循后进先出(LIFO)原则。
可以使用 push()
压栈,pop()
弹栈。
1 Stack<Integer> stack = new Stack <>();
注意 :Stack
是较旧的类,通常推荐使用 Deque
来代替 Stack
。
总结:
List :ArrayList
, LinkedList
, Vector
。
Set :HashSet
, LinkedHashSet
, TreeSet
。
Map :HashMap
, LinkedHashMap
, TreeMap
, Hashtable
。
Queue :LinkedList
, PriorityQueue
。
Deque :ArrayDeque
, LinkedList
。
Stack :Stack
(推荐使用 Deque
)。
选择容器类时,应该根据具体的使用场景选择合适的实现类,比如需要线程安全则使用 Vector
或 ConcurrentHashMap
,需要排序则选择 TreeSet
或 TreeMap
。
Java 中的容器类操作方法 Java 中的容器类提供了许多常用的方法来进行数据存储、检索、修改和操作。以下列举了各个常用容器类的一些常用方法:
List 接口常用方法 (ArrayList
, LinkedList
, Vector
)
List
是一个有序集合,支持通过索引访问元素,允许重复元素。
1 List<String> list = new ArrayList <>();
add(E e)
1 2 3 4 5 :在列表末尾添加元素。 ```java list.add("Apple");
add(int index, E e)
1 2 3 4 5 :在指定索引处添加元素。 ```java list.add(1, "Banana");
get(int index)
1 2 3 4 5 :获取指定索引处的元素。 ```java String item = list.get(0);
set(int index, E e)
1 2 3 4 5 :替换指定索引处的元素。 ```java list.set(1, "Orange");
remove(int index)
1 2 3 4 5 :移除指定索引处的元素。 ```java list.remove(0);
remove(Object o)
1 2 3 4 5 :移除列表中的某个元素(首次出现)。 ```java list.remove("Apple");
size()
1 2 3 4 5 :返回列表的大小。 ```java int size = list.size();
contains(Object o)
1 2 3 4 5 :判断列表中是否包含某个元素。 ```java boolean hasApple = list.contains("Apple");
clear()
1 2 3 4 5 :清空列表。 ```java list.clear();
isEmpty()
1 2 3 4 5 :判断列表是否为空。 ```java boolean isEmpty = list.isEmpty();
Set 接口常用方法 (HashSet
, LinkedHashSet
, TreeSet
)
Set
不允许重复元素,元素没有顺序(LinkedHashSet
和 TreeSet
有特定的顺序)。
1 Set<String> set = new HashSet <>();
add(E e)
1 2 3 4 5 :添加元素到集合中,若元素已存在则不添加。 ```java set.add("Apple");
remove(Object o)
1 2 3 4 5 :从集合中移除元素。 ```java set.remove("Apple");
contains(Object o)
1 2 3 4 5 :判断集合中是否包含某个元素。 ```java boolean hasApple = set.contains("Apple");
size()
1 2 3 4 5 :返回集合的大小。 ```java int size = set.size();
clear()
1 2 3 4 5 :清空集合。 ```java set.clear();
isEmpty()
1 2 3 4 5 :判断集合是否为空。 ```java boolean isEmpty = set.isEmpty();
Map 接口常用方法 (HashMap
, LinkedHashMap
, TreeMap
, Hashtable
)
Map
是键值对映射,键不能重复,值可以重复。
1 Map<String, Integer> map = new HashMap <>();
put(K key, V value)
1 2 3 4 5 :向 Map中添加键值对。如果键已经存在,则覆盖旧的值。 ```java map.put("Apple", 1);
get(Object key)
1 2 3 4 5 :根据键获取对应的值。如果键不存在,则返回null ```java int count = map.get("Apple");
remove(Object key)
1 2 3 4 5 :根据键移除键值对。 ```java map.remove("Apple");
containsKey(Object key)
1 2 3 4 5 :判断 Map中是否包含某个键。 ```java boolean hasApple = map.containsKey("Apple");
containsValue(Object value)
1 2 3 4 5 :判断 Map 中是否包含某个值。 ```java boolean hasCount = map.containsValue(1);
size()
1 2 3 4 5 :返回 Map的大小(键值对数量)。 ```java int size = map.size();
clear()
1 2 3 4 5 :清空Map ```java map.clear();
keySet()
1 2 3 4 5 :返回 Map中所有键的集合。 ```java Set<String> keys = map.keySet();
values()
1 2 3 4 5 :返回 Map中所有值的集合。 ```java Collection<Integer> values = map.values();
Queue 接口常用方法 (LinkedList
, PriorityQueue
)
Queue
是先进先出(FIFO)的数据结构,通常用于队列操作。
1 Queue<String> queue = new LinkedList <>();
offer(E e)
1 2 3 4 5 6 7 :添加元素到队列的末尾,返回 true (如果队列有容量限制且插入失败则返回 false) ```java queue.offer("Apple");
poll()
1 2 3 4 5 :从队列的头部移除并返回元素。如果队列为空,返回 null ```java String item = queue.poll();
peek()
1 2 3 4 5 :获取队列头部的元素,但不移除。如果队列为空,返回null ```java String head = queue.peek();
size()
1 2 3 4 5 :返回队列的大小。 ```java int size = queue.size();
isEmpty()
1 2 3 4 5 :判断队列是否为空。 ```java boolean isEmpty = queue.isEmpty();
Deque 接口常用方法 (ArrayDeque
, LinkedList
)
Deque
是双端队列,可以在两端插入和删除元素。
1 Deque<String> deque = new ArrayDeque <>();
offerFirst(E e)
1 2 3 4 5 :在队列的头部插入元素。 ```java deque.offerFirst("Apple");
offerLast(E e)
1 2 3 4 5 :在队列的尾部插入元素。 ```java deque.offerLast("Banana");
pollFirst()
1 2 3 4 5 :从队列头部移除并返回元素。 ```java String first = deque.pollFirst();
pollLast()
1 2 3 4 5 :从队列尾部移除并返回元素。 ```java String last = deque.pollLast();
peekFirst()
1 2 3 4 5 :获取队列头部的元素,但不移除。 ```java String first = deque.peekFirst();
peekLast()
1 2 3 4 5 :获取队列尾部的元素,但不移除。 ```java String last = deque.peekLast();
Stack 类常用方法
Stack
是后进先出(LIFO)的数据结构,继承自 Vector
。
1 Stack<String> stack = new Stack <>();
push(E e)
1 2 3 4 5 :将元素压入栈顶。 ```java stack.push("Apple");
pop()
1 2 3 4 5 :移除并返回栈顶元素。 ```java String item = stack.pop();
peek()
1 2 3 4 5 :返回栈顶元素但不移除。 ```java String top = stack.peek();
isEmpty()
1 2 3 4 5 :判断栈是否为空。 ```java boolean isEmpty = stack.isEmpty();
总结
List :add
, get
, set
, remove
, size
, contains
, clear
等。
Set :add
, remove
, contains
, size
, clear
等。
Map :put
, get
, remove
, containsKey
, containsValue
, keySet
, values
等。
Queue :offer
, poll
, peek
, size
, isEmpty
等。
Deque :offerFirst
, offerLast
, pollFirst
, pollLast
, peekFirst
, peekLast
等。
Stack :push
, pop
, peek
, isEmpty
等。
每个容器类的方法都是围绕数据的存储、检索和修改来设计的。选择合适的方法和容器,能够提高代码的效率和可读性。
Java 基础——Scanner 类_java scanner-CSDN博客
Java的输入和输出_java输入语句怎么写-CSDN博客
面试真题 小米2023秋季
151. 手机流畅运行的秘密
151. 手机流畅运行的秘密 (kamacoder.com)
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); String input = scanner.next(); String[] s1 = input.split("," ); int [][] task = new int [s1.length][2 ]; for (int i = 0 ;i<task.length;i++){ String[] temp = s1[i].split(":" ); task[i][0 ] = Integer.valueOf(temp[0 ]); task[i][1 ] = Integer.valueOf(temp[1 ]); } Arrays.sort(task,(a,b)->{ return Math.abs(b[1 ]-b[0 ])-Math.abs(a[1 ]-a[0 ]); }); int result = 0 ,balance = 0 ; for (int i = 0 ;i<task.length;i++){ if (balance>=task[i][1 ]){ balance-=task[i][0 ]; }else { int temp = task[i][1 ]-balance; result+=temp; balance = balance+temp-task[i][0 ]; } } if (result>4800 ){ System.out.println(-1 ); }else { System.out.println(result); } } }
152. 小米手机通信校准
152. 小米手机通信校准 (kamacoder.com)
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int freq = scanner.nextInt(); List<String> list = new ArrayList <>(); while (scanner.hasNext()) { list.add(scanner.next()); } int [][] losses = new int [list.size()][2 ]; for (int i = 0 ; i < list.size(); i++) { String[] temp = list.get(i).split(":" ); losses[i][0 ] = Integer.valueOf(temp[0 ]); losses[i][1 ] = Integer.valueOf(temp[1 ]); } int closestIndex = 0 ; int left = 0 , right = losses.length - 1 ; double result = 0 ; while (left <= right) { int mid = left + (right - left) / 2 ; if (Math.abs(losses[mid][0 ] - freq) < Math.abs(losses[closestIndex][0 ] - freq)) { closestIndex = mid; } if (losses[mid][0 ] > freq) { right = mid - 1 ; } else if (losses[mid][0 ] < freq) { left = mid + 1 ; } else { System.out.printf("%.1f" , (double ) losses[mid][1 ]); return ; } } if (left < losses.length) { if (Math.abs(losses[left][0 ] - freq) < Math.abs(losses[closestIndex][0 ] - freq)) { closestIndex = left; } } if (right >= 0 ) { if (Math.abs(losses[right][0 ] - freq) < Math.abs(losses[closestIndex][0 ] - freq)) { closestIndex = right; } } if (left < losses.length && right >= 0 && Math.abs(losses[left][0 ] - freq) == Math.abs(losses[right][0 ] - freq)) { result = (losses[left][1 ] + losses[right][1 ]) / 2.0 ; } else { result = losses[closestIndex][1 ]; } System.out.printf("%.1f" , result); } }
美团2023秋季
128. 小美的排列询问
https://kamacoder.com/problempage.php?pid=1204
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); int [] list = new int [n]; for (int i = 0 ;i<n;i++){ list[i] = scanner.nextInt(); } int first = scanner.nextInt(); int second = scanner.nextInt(); for (int i = 1 ;i<n;i++){ if ((list[i-1 ]==first&&list[i]==second)||(list[i-1 ]==second&&list[i]==first)){ System.out.println("Yes" ); return ; } } System.out.println("No" ); } }
129. 小美走公路
129. 小美走公路 (kamacoder.com)
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 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); int [] need = new int [n + 1 ]; long sum = 0L ; for (int i = 1 ; i <= n; i++) { need[i] = scanner.nextInt(); sum+=need[i]; } int x = scanner.nextInt(); int y = scanner.nextInt(); if (x==y){ System.out.println(0 ); return ; } if (x>y){ int temp = x; x = y; y = temp; } long result = 0L ; while (x<y){ result+=need[x]; x++; } System.out.println(Math.min(result,sum-result)); } }
130. 小美的蛋糕切割
130. 小美的蛋糕切割 (kamacoder.com)
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int x = scanner.nextInt(),y =scanner.nextInt(); int [] rowSum = new int [x]; int [] columnSum = new int [y]; int [] sum = new int [y]; for (int i = 0 ;i<x;i++){ for (int j = 0 ;j<y;j++){ int temp = scanner.nextInt(); rowSum[i]+=temp; columnSum[j]+=temp; } } int total = 0 ; int [] rowDp = new int [x]; int [] columnDp =new int [y]; total+=rowSum[0 ]; rowDp[0 ] = rowSum[0 ]; columnDp[0 ] = columnSum[0 ]; for (int i = 1 ;i<x;i++){ rowDp[i] = rowDp[i-1 ]+rowSum[i]; total+=rowSum[i]; } for (int j = 1 ;j<y;j++){ columnDp[j] = columnDp[j-1 ]+columnSum[j]; } int result = Integer.MAX_VALUE; for (int i = 0 ;i<x;i++){ result = Math.min(result,Math.abs(total-rowDp[i]-rowDp[i])); } for (int j = 0 ;j<y;j++){ result = Math.min(result,Math.abs(total-columnDp[j]-columnDp[j])); } System.out.println(result); } }
131. 小美的字符串变换
131. 小美的字符串变换 (kamacoder.com)
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 import java.util.*;public class Main { public static void main (String[] args) { int result = Integer.MAX_VALUE; Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); String s = scanner.next(); char [] chars = s.toCharArray(); int len = chars.length; for (int row = 1 ;row<=len;row++){ int column = len/row; if (row*column==len){ char [][] graph = new char [row][column]; int flag = 0 ; for (int i = 0 ;i<row;i++){ for (int j = 0 ;j<column;j++){ graph[i][j] = chars[flag++]; } } result = Math.min(result,solve(graph,row,column)); } } System.out.println(result); } public static int solve (char [][]graph,int n,int m) { int result = 0 ; boolean [][] isVisited = new boolean [n][m]; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<m;j++){ if (!isVisited[i][j]){ result++; dfs(graph,isVisited,n,m,i,j); } } } return result; } public static int [][] dir = new int [][]{{1 ,0 },{-1 ,0 },{0 ,-1 },{0 ,1 }}; public static void dfs (char [][] graph,boolean [][] isVisited,int n,int m,int i,int j) { isVisited[i][j] = true ; for (int k = 0 ;k<4 ;k++){ int nextI = i+dir[k][0 ]; int nextJ = j+dir[k][1 ]; if (nextI>=0 &&nextJ>=0 &&nextI<n&&nextJ<m&&!isVisited[nextI][nextJ] &&graph[i][j]==graph[nextI][nextJ]){ dfs(graph,isVisited,n,m,nextI,nextJ); } } } }
132. 小美的树上染色
132. 小美的树上染色 (kamacoder.com)
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int count = scanner.nextInt(); List<List<Integer>>graph = new ArrayList <>(); for (int i = 0 ;i<=count;i++){ graph.add(new ArrayList <>()); } int [] points = new int [count+1 ]; for (int i = 1 ;i<=count;i++){ points[i] = scanner.nextInt(); } while (scanner.hasNextInt()){ int u = scanner.nextInt(); int v = scanner.nextInt(); graph.get(u).add(v); graph.get(v).add(u); } int [] result = new int []{0 }; boolean [] isVisited = new boolean [count+1 ]; dfs(result,isVisited,points,graph,1 ,-1 ); System.out.println(result[0 ]); } public static void dfs (int [] result,boolean [] isVisited,int []points,List<List<Integer>>graph,int u,int parent) { for (int v:graph.get(u)){ if (v!=parent){ dfs(result,isVisited,points,graph,v,u); if (!isVisited[v]&&!isVisited[u]){ int sqrt = (int )Math.sqrt(points[v]*points[u]); if (sqrt*sqrt==points[v]*points[u]){ isVisited[v] = true ; isVisited[u] = true ; result[0 ]+=2 ; } } } } } }
字节跳动2023秋季
147. 三珠互斥
147. 三珠互斥 (kamacoder.com)
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int count = scanner.nextInt(); int [] dis = new int [3 ]; while (count--!=0 ){ int n = scanner.nextInt(); int k = scanner.nextInt(); int a1 = scanner.nextInt(); int a2 = scanner.nextInt(); int a3 = scanner.nextInt(); if ((long )(k*3 )>n){ System.out.println(-1 ); continue ; } dis[0 ] = Math.min(Math.abs(a1-a2),n-Math.abs(a1-a2)); dis[1 ] = Math.min(Math.abs(a1-a3),n-Math.abs(a1-a3)); dis[2 ] = Math.min(Math.abs(a2-a3),n-Math.abs(a2-a3)); Arrays.sort(dis); int result = 0 ; if (dis[0 ]<k){ result+=(k-dis[0 ]); } if (dis[1 ]<k){ result+=(k-dis[1 ]); } System.out.println(result); } } }
148. 扑克牌同花顺
148. 扑克牌同花顺 (kamacoder.com)
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 65 66 67 68 69 70 71 72 73 74 75 76 77 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int count = scanner.nextInt(); HashMap<Integer,Integer>mapS = new HashMap <>(); HashMap<Integer,Integer>mapH = new HashMap <>(); HashMap<Integer,Integer>mapD = new HashMap <>(); HashMap<Integer,Integer>mapC = new HashMap <>(); for (int i = 0 ;i<count;i++){ int num = scanner.nextInt(); int size = scanner.nextInt(); String type = scanner.next(); if (type.equals("S" )){ mapS.put(num,mapS.getOrDefault(num,0 )+size); }else if (type.equals("H" )){ mapH.put(num,mapH.getOrDefault(num,0 )+size); }else if (type.equals("D" )){ mapD.put(num,mapD.getOrDefault(num,0 )+size); }else { mapC.put(num,mapC.getOrDefault(num,0 )+size); } } long res = 0L ; res+=solve(mapS); res+=solve(mapH); res+=solve(mapD); res+=solve(mapC); System.out.println(res); } public static long solve (HashMap<Integer,Integer>map) { long result = 0L ; for (int i1 : map.keySet()){ int i2 = i1+1 ; int i3 = i1+2 ; int i4 = i1+3 ; int i5 = i1+4 ; int minCount = map.getOrDefault(i1,0 ); minCount = Math.min(minCount,map.getOrDefault(i2,0 )); minCount = Math.min(minCount,map.getOrDefault(i3,0 )); minCount = Math.min(minCount,map.getOrDefault(i4,0 )); minCount = Math.min(minCount,map.getOrDefault(i5,0 )); if (minCount!=0 ){ result+=minCount; map.put(i1,map.get(i1)-minCount); map.put(i2,map.get(i2)-minCount); map.put(i3,map.get(i3)-minCount); map.put(i4,map.get(i4)-minCount); map.put(i5,map.get(i5)-minCount); } } return result; } }
149. 好数组
149. 好数组 (kamacoder.com)
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 65 66 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int count = scanner.nextInt(); int [] ints = new int [count]; for (int i = 0 ;i<count;i++){ ints[i] = scanner.nextInt(); } Arrays.sort(ints); if (ints[0 ]==ints[count-1 ]){ System.out.println(1 ); return ; } int [] ints1 = new int [count-1 ]; int [] ints2 = new int [count-1 ]; for (int i = 1 ;i<count;i++){ ints1[i-1 ] = ints[i]; } for (int i = 0 ;i<count-1 ;i++){ ints2[i] = ints[i]; } System.out.println(Math.min(solve(ints1),solve(ints2))); } public static long solve (int [] ints) { long result = 0L ; int len = ints.length; if (len%2 !=0 ){ int mid = ints[len/2 ]; for (int i = 0 ;i<len;i++){ result+= Math.abs(ints[i]-mid); } }else { int mid1 = ints[len/2 ]; int mid2 = ints[len/2 -1 ]; long res1 = 0L ,res2 = 0L ; for (int i = 0 ;i<len;i++){ res1+=Math.abs(ints[i]-mid1); res2+=Math.abs(ints[i]-mid2); } result = Math.min(res1,res2); } return result; } }
150. 极长连续段的权值
150. 极长连续段的权值 (kamacoder.com)
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 import java.util.*;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); String s = scanner.next(); long result = 1L ; long temp = 1L ; for (int i = 1 ;i<n;i++){ temp = temp+1 ; if (s.charAt(i)!=s.charAt(i-1 )){ temp+=i; } result+=temp; } System.out.println(result); } }
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 class Solution { public void reorderList (ListNode head) { int count = 0 ; ListNode node = head; while (node!=null ){ count++; node = node.next; } if (count%2 ==0 ){ count/=2 ; } else { count = count/2 +1 ; } node = head; while ((count--)!=0 ){ node = node.next; } ListNode next = node.next; node.next = null ; next = reverse(next); node = head; while (node!=null ){ ListNode temp = node.next; temp.next = next; ListNode temp2 = next.next; next.next = temp; next = temp2; node = temp; } } public ListNode reverse (ListNode head) { ListNode node = head,last = null ; while (node!=null ){ ListNode next = node.next; node.next = last; last = node; node = next; } return last; } }