这篇文章主要是记录刷过的题以及里面一些需要注意的关键点(https://www.programmercarl.com/ )
1.做题记录
2.一些java用法 put+remove(HashMap),add+remove(List)
数学函数 平方根函数：
1 double f = Math.sqrt(n);
数组 数组排序：
打印数组：
1 System.out.println(Arrays.toString(array));
数组初始化：
数组获得复制数组（并不指向同一地址）：
1 int [] num = Arrays.copyOf(nums, len);
int[]数组自定义排序规则：
1 2 3 4 5 6 7 8 return Arrays.stream(arr).boxed().sorted(new Comparator <Integer>() { @Override public int compare (Integer num1, Integer num2) { int a = count1(num1); int b = count1(num2); return (a == b) ? Integer.compare(num1, num2) : Integer.compare(a, b); } }).mapToInt(Integer::intValue).toArray();
这段代码使用了Java 8及以上版本的Stream API来处理一个整数数组（假设这个数组名为arr），尽管初始代码段中并没有直接显示arr的声明和类型，但从上下文可以推断出arr是一个int[]类型的数组。接下来，我将逐步解释这段代码的作用：
Arrays.stream(arr).boxed():
Arrays.stream(arr)将int[]数组arr转换为一个IntStream，这是Java Stream API的一部分，专门用于处理基本数据类型int的序列。.boxed()方法将IntStream转换为Stream<Integer>。这是因为IntStream处理的是基本类型int，而Stream<Integer>处理的是对象类型Integer。这一步骤是必要的，因为接下来的排序和比较操作需要Integer对象，因为它们依赖于Comparator接口，该接口是为对象类型设计的。
.sorted(new Comparator<Integer>(){...}):
.sorted(...)方法接收一个Comparator<Integer>作为参数，用于定义排序逻辑。在这个Comparator中，compare方法被重写以定义排序规则。它首先调用一个假定的cntInt(Integer)方法（该方法在代码段中没有给出，但我们可以假设它接受一个Integer并返回一个整数值，这个值可能表示该整数在另一个集合中出现的次数或某种与整数相关联的计数）。
然后，它比较两个整数的cntInt返回值（cnt1和cnt2）。如果这两个计数相同，则使用Integer.compare(o1, o2)来按整数的自然顺序（即数值大小）进行排序。如果计数不同，则根据计数的大小进行排序。
.mapToInt(Integer::intValue):
.mapToInt(Integer::intValue)将Stream<Integer>转换回IntStream。这是因为排序和比较完成后，可能希望将结果转换回基本类型的数组以节省内存或出于其他性能考虑。Integer::intValue是一个方法引用，它引用了Integer对象的intValue()方法，该方法返回Integer对象封装的int值。
.toArray():
最后，.toArray()方法将IntStream转换回int[]数组。这是整个链式调用的结果，现在是一个按照自定义排序逻辑（基于cntInt方法的返回值和整数的自然顺序）排序的整数数组。
栈Stack 栈的初始化：
1 Stack<TreeNode> myStack = new Stack <>();
栈的基本操作：
1 2 3 myStack.push(cur); cur = myStack.pop(); cur = myStack.peek();
队列Queue 使用LinkedList实现Queue 队列的初始化：
1 Queue<TreeNode> myQueue = new LinkedList <>();
队列的基本操作（因为上述Queue的初始化是通过LinkedList实现的，所以此队列的操作函数与LinkedList一致）：
1 2 3 4 5 6 myQueue.add(root); TreeNode cur = myQueue.removeLast();TreeNode cur = myQueue.poll();TreeNode cur = myQueue.peek();int size = myQueue.size();while (!myQueue.isEmpty())
堆PriorityQueue PriorityQueue 默认是小根堆，大顶堆定义：（基本操作和队列一致）
1 Queue<Integer> bigHeap = new PriorityQueue <>((o1, o2) -> o2 - o1);
链表List 链表的实现分为ArrayList和LinkedList
ArrayList LinkedList LinkedList链表的初始化：
1 2 List<Integer> me = new LinkedList <>(); List<List<Integer>> result = new LinkedList <>();
LinkedList链表的基本操作：
1 2 3 4 result.add(me); Collections.reverse(result); for (Node child : cur.children)int size = list.size()
关于链表删除：list.remove()的问题：
1 2 3 4 5 ArrayList<Integer> randomNumbers = new ArrayList <>(); randomNumbers.remove(Integer.valueOf(13 )); randomNumbers.remove(13 );
字符串 String char[]转String:
1 String str = new String (charArray);
字符串长度：
关于数组Array的长度获取是arr.length，但是字符串String的长度获取是str.length()的原因：
数组在Java中是一种基础数据类型，但也被视为对象（因为它们有引用类型的特性）。数组一旦被创建，其长度就是固定的，并且这个长度信息是作为数组对象的一部分直接存储的 。因此，当你访问array.length时，实际上是在直接访问这个数组对象的内置属性（或者说元数据），而不是在调用一个方法。这就是为什么不需要括号的原因——因为这不是一个函数调用，而是一个直接访问操作。
字符串（String）在Java中是一个类（java.lang.String），而不是基础数据类型。这意味着字符串是一个对象，拥有属性和方法。String类的length()方法是一个实例方法，用于返回字符串的长度。 由于这是一个方法调用，所以需要使用括号来包围参数（尽管length()方法不接受任何参数，但括号是必须的，以区分于属性访问）。
获取字符串某个位置的元素：
遍历字符串：使用for+str.charAt()
String转char[]:
1 char [] array = str.toCharArray();
注：String对象一旦创建，实体是不可以变化的，即内容不能再修改
判断相等：
==判断的是否为同一对象，str.equals(“abc”)判断的是内容
子串切割：注意切割之后的子串是[i,j)
1 str = str.substring(i,j);
StringBuilder 字符串String倒置：
1 return new StringBuffer (str).reverse().toString();
集合Set(Collections) 集合的初始化：
1 Set<String> set = new HashSet <String>();
集合的遍历：
1 2 3 4 5 6 7 8 9 通过foreach for (String s:set) { System.out.println(s); } 遍历，通过迭代器 Iterator<String> it = set.iterator(); while (it.hasNext()){ System.out.println(it.next()); }
集合添加元素：
集合删除元素：
集合是否包含元素：
1 2 3 if (set.contains(“one”)){ ; }
集合转数组：
需要注意，new String[0]新建了一个String数组，但是它的长度是0。其作用是，1.告诉toArray方法你期望的数组类型是什么，这对于泛型集合尤为重要，因为泛型信息在运行时会被擦除，所以toArray方法需要某种方式来知道它应该创建什么类型的数组。 2.触发新数组分配 ：由于数组的长度为0，显然不足以存储集合中的任何元素（除非集合本身就是空的）。因此，toArray方法会意识到需要分配一个新的数组来存储所有元素。
当然，如果你知道集合的大小（或至少有一个合理的估计），传入一个足够大的数组可能会更有效率。如果传入的数组足够大以容纳集合中的所有元素，toArray方法就会直接在这个数组中填充元素，而不是分配一个新的数组。然而，这要求你能够提前知道或估计集合的大小，这在很多情况下是不可行的。
1 String[] strings = hashSet.toArray(new String [0 ]);
另外：
1 2 Set<Integer> result = new HashSet <>(); Integer[] integers = result.toArray(new Integer [0 ]);
这种方法只能直接转成Integer[ ]，而不能直接转成int[ ]，可以使用下面的思路：
1 2 3 return result.stream() .mapToInt(Integer::intValue) .toArray();
映射Map(Collections) HashMap 初始化：
1 Map<String, Integer> map = new HashMap <>();
增加元素：
查找元素：
1 System.out.println(map.get("one" ));
移除元素：
是否包含元素：
如果找不到元素，返回默认值：
1 map.getOrDefault(1 , "Not Found" );
Map的遍历：
1 for (int num : me.keySet())
3.做题笔记 数组 704.二分查找 二分的特征：升序+无重复
大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量 。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量 规则。
定义target在[left, right]区间 ：
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
防止溢出：
1 int middle = left + ((right - left) / 2 ); 防止溢出 等同于(left + right)/2
27.移除元素 区间的定义是[left,right]:
while(left<=right)
left++;right–;
因为while的过程当中可能会超出限制，所以要while (left <= nums.length - 1 && nums[left] != val)，而且要if (left <= right)再交换
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 removeElement (int [] nums, int val) { int left = 0 ; int right = nums.length - 1 ; while (left <= right) { while (left<=nums.length-1 &&nums[left] != val) { left++; } while (right>=0 &&nums[right] == val) { right--; } if (left <= right ) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } return left; } }
977. 有序数组的平方 双指针，绝对值最大的数字一定是在两边，结果数组的最后一位由双指针确定，结果数组从后往前依次确定
209.长度最小的子数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int minSubArrayLen (int target, int [] nums) { int left = 0 ; int sum = 0 ; int result = nums.length + 1 ; for (int right = left; right < nums.length; right++) { sum += nums[right]; while (sum >= target) { result = Math.min(result, right - left + 1 ); sum = sum - nums[left]; left++; } } return result == nums.length + 1 ? 0 : result; } }
59.螺旋矩阵II 需要注意：
确定好每一次的填充都是左闭右开的填充
奇数的矩阵要比偶数的矩阵再多一个填充中间位置的元素的步骤
1365.有多少小于当前数字的数字 排序，map记录( nums[i] , 几个比它小的数 )
最后按照原来数组的顺序依次在map当中寻找结果
941.有效的山脉数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public boolean validMountainArray (int [] arr) { int len = arr.length; if (len < 3 ) { return false ; } if (arr[1 ] < arr[0 ]) { return false ; } boolean isTop = false ; for (int i = 1 ; i < len; i++) { if (arr[i] == arr[i - 1 ]) { return false ; } if (arr[i] < arr[i - 1 ] && isTop == false ) { isTop = true ; } if (isTop && arr[i] >= arr[i - 1 ]) { return false ; } } return isTop; int len = arr.length; int left = 0 ; int right = len - 1 ; while (left + 1 < len && arr[left] < arr[left + 1 ]) { left++; } while (right - 1 >= 0 && arr[right] < arr[right - 1 ]) { right--; } return left == right && left != 0 && right != len - 1 ; } }
1207.独一无二的出现次数 使用map记录每一个元素的出现次数，最后依次把出现次数放到set当中，如果set已经存在这个次数了就返回false
283. 移动零 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 ; int fast = 0 ; for (; fast < nums.length; fast++) { if (nums[fast] != 0 ) { nums[slow] = nums[fast]; slow++; } } for (int i = slow; i < nums.length; i++) { nums[i] = 0 ; } } }
189. 旋转数组 1.倒序前len-k个元素，倒序后k个元素，倒序整个数组
2.双指针：右轮转k次，每一次轮转都有：记录nums[0], slow=0, fast=slow+1, nums[slow]=nums[fast]
3.暴力解法，O(n)的空间，先把后k个元素复制到新的数组当中，再把剩下的复制
724.寻找数组的中心下标 遍历数组求出总和，第二次遍历再计算leftSum和rightSum是否相等。
其中，leftSum的定义是从0到i为止(包括i的sum)，rightSum也是包括i的sum。这样可以少很多特殊条件的判断
922. 按奇偶排序数组II 双指针，slow只关心偶数位置，fast只关心奇数位置
75. 颜色分类 分别记录0，1，2有多少个即可
26. 删除有序数组中的重复项 快慢指针
448. 找到所有数组中消失的数字 可以考虑原地修改数组（这种方法在力扣一些题当中会用到，但是不提倡，因为会修改原有数组，工作当中不常用）：
把[0,n-1]位置作为[1,n]数字的映射，数组当中出现数字x，就把nums[x-1]的位置赋为负数
35. 搜索插入位置 二分查找即可
287. 寻找重复数 把[0,n-1]的位置作为数字[1,n]的映射，遇到数字x，就把x-1位置的元素赋为负数
73. 矩阵置零 记录需要赋值为0的行和列即可
74. 搜索二维矩阵 定位到哪一行再二分查找即可
34. 在排序数组中查找元素的第一个和最后一个位置 二分查找,再向左向右探索即可
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 class Solution { public int lengthOfLongestSubstring (String s) { int len = s.length(); if (len == 0 ) { return 0 ; } int result = 1 ; int left = 0 ; int right = -1 ; Set<Character> set = new HashSet <>(); while (left < len) { if (left - 1 >= 0 ) { set.remove(s.charAt(left - 1 )); } left++; while (right + 1 < len && !set.contains(s.charAt(right + 1 ))) { set.add(s.charAt(right + 1 )); right = right + 1 ; } result = Math.max(result, set.size()); } return result; } }
153. 寻找旋转排序数组中的最小值 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 findMin (int [] nums) { int len = nums.length; int left = 0 ; int right = len - 1 ; if (nums[0 ] <= nums[len - 1 ]) { return nums[0 ]; } while (left < right) { int mid = (right - left) / 2 + left; if (nums[mid] >= nums[0 ]) { left = mid + 1 ; } else { right = mid; } } return nums[left]; } }
33. 搜索旋转排序数组 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 search (int [] nums, int target) { int minIndex = findMIn(nums); if (minIndex == 0 ) { return bSearch(nums, target, 0 , nums.length - 1 ); } if (nums[0 ] == target) { return 0 ; } else if (nums[0 ] < target) { return bSearch(nums, target, 0 , minIndex - 1 ); } else { return bSearch(nums, target, minIndex, nums.length - 1 ); } } public int findMIn (int [] nums) { int len = nums.length; if (nums[0 ] < nums[len - 1 ]) { return 0 ; } int left = 0 ; int right = len - 1 ; while (left < right) { int mid = (right - left) / 2 + left; if (nums[mid] >= nums[0 ]) { left = mid + 1 ; } else { right = mid; } } return left; } public int bSearch (int [] nums, int target, int begin, int end) { int left = begin; int right = end; while (left <= right) { int mid = (right - left) / 2 + left; if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { right = mid - 1 ; } else { left = mid + 1 ; } } return -1 ; } }
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 m = matrix.length; int n = matrix[0 ].length; List<Integer> result = new ArrayList <>(); for (int k = 0 ; k < m / 2 && k < n / 2 ; k++) { for (int i = k; i < n - k - 1 ; i++) { result.add(matrix[k][i]); } for (int i = k; i < m - k - 1 ; i++) { result.add(matrix[i][n - k - 1 ]); } if (m - k - 1 > k) { for (int i = n - k - 1 ; i > k; i--) { result.add(matrix[m - k - 1 ][i]); } } if (n - k - 1 > k) { for (int i = m - k - 1 ; i > k; i--) { result.add(matrix[i][k]); } } } if (m % 2 == 0 && n % 2 == 0 ) { return result; } if (m == n) { if (m % 2 == 1 ) { result.add(matrix[m / 2 ][n / 2 ]); } } else if (m / 2 < n / 2 ) { for (int i = m / 2 ; i <= m / 2 + (n - m); i++) { result.add(matrix[m / 2 ][i]); } } else if (m / 2 > n / 2 ) { for (int i = n / 2 ; i <= n / 2 + (m - n); i++) { result.add(matrix[i][n / 2 ]); } } return result; } }
48. 旋转图像 [i,j]->[j,n-1-i]->[n-1-i,n-1-j]->[n-1-j,i]，注意n为奇偶数时需要处理的i和j的范围
240. 搜索二维矩阵 II 从右上角开始查找，如果target>matrix[i] [j]，那么就往下，反之则往左
31. 下一个排列 举例：2 4 5 3(i) 4 4(j) 2 1->2 4 5 4 1 2 3 4
考察最右侧的递减序列：从右到左查找到3(i)，把比3大的最小值4(j)交换：2 4 5 4(i) 4 3(j) 2 1，之后把4 3(j) 2 1进行排序
由于原本4 4(j) 2 1是递减序列，并且交换的3是比4更小的值，因此交换之后的序列仍然是递减序列，这里排序只需倒转即可
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 void nextPermutation (int [] nums) { int len = nums.length; int i = len - 1 ; while (i - 1 >= 0 && nums[i - 1 ] >= nums[i]) { i--; } i--; if (i >= 0 ) { int j = len - 1 ; while (j >= 0 && nums[j] <= nums[i]) { j--; } swap(nums, i, j); } reverse(nums, i + 1 , len - 1 ); } public void swap (int [] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public void reverse (int [] nums, int i, int j) { for (int k = i; k <= (i + j) / 2 ; k++) { swap(nums, k, i + j - k); } } }
643. 子数组最大平均数 I 即寻找一个长度为k且加和sum最大的连续子数组
1431. 拥有最多糖果的孩子 先遍历一遍candies，确定如果要成为最多糖果的孩子，至少需要多少糖果
605. 种花问题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public boolean canPlaceFlowers (int [] flowerbed, int n) { int times = 0 ; int len = flowerbed.length; for (int i = 0 ; i < len; i++) { if (flowerbed[Math.max(i - 1 , 0 )] == 0 && flowerbed[i] == 0 && flowerbed[Math.min(i + 1 , len - 1 )] == 0 ) { flowerbed[i] = 1 ; times++; } } return times >= n; } }
2215. 找出两数组的不同 使用HashSet即可
链表 203.移除链表元素 这类问题最重要的是在草稿上画出节点变动的过程，否则写起来会很麻烦。以及需要注意，while的条件到底是 cur!=null 还是 cur.next!=null ，以及遇到 cur.next.next 的时候要注意判断 cur.next==null。
这道题比较简单，需要注意删除cur节点的时候，pre和cur的处理。以及要新建结果链表的新的头节点result，因为结果链表的头节点有可能不是head
206.反转链表 这道题比较简单，头插法：cur摘掉（cur一直在head后面），插在result和result.next中间
24. 两两交换链表中的节点 这道题需要对每两个一组的cur1，cur2以及pre的操作在草稿上面画的清楚。并且需要注意，一开始pre的定义是pre.next=head，那么要把这个时候pre的位置记下来，返回这个位置的next才是最后的头节点
19.删除链表的倒数第N个节点 快慢指针，快指针比慢指针先走N-1个位置，fast走到最后的时候，slow就是倒数N个节点，再记录slow前一个节点pre，通过pre吧slow删除
160. 相交链表 快慢指针，在短链表里面的慢指针每次走一步，从头节点开始走。在长链表里面的快指针每次走一步，但是从第abs(m-n)个节点开始走
142.环形链表II 快慢指针，快指针走两步，慢指针走一步。当快慢相遇的时候，再派一个慢指针slow2，slow2和slow1相遇的位置就是入口
2. 两数相加 把当前进位带到下一位即可，别忘了最后一个进位有可能新建节点，tail指向最后一个确定val的节点
148. 排序链表 把所有val放到数组当中排列再新建链表
23. 合并 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 33 34 35 36 37 38 39 40 41 42 class Solution { public ListNode mergeKLists (ListNode[] lists) { ListNode head = null ; ListNode tail = head; while (isVaild(lists)) { int val = 100001 ; int j = -1 ; for (int i = 0 ; i < lists.length; i++) { if (lists[i] != null && val > lists[i].val) { j = i; val = lists[j].val; } } if (j != -1 ) { if (head == null ) { head = new ListNode (val); tail = head; } else { tail = add(tail, val); } lists[j] = lists[j].next; } } return head; } public ListNode add (ListNode tail, int val) { ListNode node = new ListNode (val, null ); tail.next = node; tail = tail.next; return tail; } public boolean isVaild (ListNode[] lists) { for (int i = 0 ; i < lists.length; i++) { if (lists[i] != null ) { return true ; } } return false ; } }
138. 随机链表的复制 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public Node copyRandomList (Node head) { Map<Node, Node> map = new HashMap <>(); Node curHead = head; while (curHead != null ) { map.put(curHead, new Node (curHead.val)); curHead = curHead.next; } curHead = head; while (curHead != null ) { map.get(curHead).next = map.get(curHead.next); map.get(curHead).random = map.get(curHead.random); curHead = curHead.next; } return map.get(head); }
哈希表 242.有效的字母异位词 什么时候使用哈希法 ，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
使用数组存储26个字母的出现频率，构造简易的哈希表
349. 两个数组的交集 输出结果中的每个元素一定是唯一的，所以考虑HashSet当作哈希表
202.快乐数 不符合要求的n会无限循环，也就是结果会重复出现。因此需要使用set来记录每一次的结果，如果重复出现了就不是快乐数
1.两数之和 1.排序+快慢指针
2.数组中同一个元素在答案里不能重复出现，想到使用HashMap。这里需要注意，为什么不是HashSet呢，因为我们最后需要返回元素的下标，那么哈希表就需要存放元素和下标位置，使用HashMap可以轻松解决。
并且需要注意的是，我们需要在哈希表当中寻找元素是否出现过，那么key得是元素。
383. 赎金信 使用数组存储26个字母的出现频率，构造简易的哈希表即可
15.三数之和 先排序，固定slow1，对接下来的数组使用快慢指针来寻找target==0-nums[slow1]的两个元素
需要注意的是，答案返回组成三元组的元素数值，并且当中不可以有重复的三元组，那么就需要去重：
1 2 3 4 5 6 7 8 9 10 11 while (slow1 - 1 >= 0 && slow1 < nums.length - 1 && nums[slow1] == nums[slow1 - 1 ]){ slow1++; } while (slow2 + 1 < fast && nums[slow2] == nums[slow2 + 1 ]) { slow2++; } while (slow2 < fast - 1 && nums[fast] == nums[fast - 1 ]) { fast--; }
注：Set无法直接去重，因为list1:{1,2,3}和list2:{2,1,3}不会被认为是重复的
18.四数之和 对于去重的操作如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 while (i - 1 >= 0 && i + 1 <= nums.length - 1 && nums[i] == nums[i - 1 ]) { i++; } while (j - 1 >= i + 1 && j + 1 <= nums.length - 1 && nums[j] == nums[j - 1 ]) { j++; } while (slow + 1 < fast && nums[slow] == nums[slow + 1 ]) { slow++; } while (slow < fast - 1 && nums[fast] == nums[fast - 1 ]) { fast--; }
另外，这道题可能会涉及到int溢出的问题，所以要强转成long：
1 2 long myTarget = target - (long ) nums[i] - (long ) nums[j];if ((long ) nums[slow] + nums[fast] == myTarget)
454.四数相加II 三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，有很多细节需要处理。这道题和三数相加、四数相加的思路都不一样，是使用哈希法的经典题目，应该使用HashMap。
思路是：统计两个数组AB中的元素之和，同时统计出现的次数，放入map。再统计剩余的两个元素CD的和，在map中找是否存在相加为0的情况，同时记录次数。
146. LRU 缓存 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 class LRUCache { int capacity = 0 ; Node head = new Node (); Node tail = new Node (); Map<Integer, Node> LRU = new HashMap <>(); public LRUCache (int capacity) { this .capacity = capacity; head.next = tail; tail.pre = head; } public int get (int key) { if (LRU.containsKey(key)) { Node node = LRU.get(key); moveHead(node); return node.value; } else { return -1 ; } } public void put (int key, int value) { if (LRU.containsKey(key)) { Node node = LRU.get(key); node.value = value; moveHead(node); return ; } if (LRU.size() == capacity) { LRU.remove(tail.pre.key); delTail(); } Node node = new Node (key, value, null , null ); addHead(node); LRU.put(key, node); } public void addHead (Node node) { node.next = head.next; node.pre = head; head.next.pre = node; head.next = node; } public void delTail () { Node newTail = tail.pre.pre; newTail.next = tail; tail.pre = newTail; } public void moveHead (Node node) { node.pre.next = node.next; node.next.pre = node.pre; addHead(node); } } class Node { Node pre; Node next; int key; int value; public Node (int key, int value, Node pre, Node next) { this .key = key; this .pre = pre; this .next = next; this .value = value; } public Node () { } }
438. 找到字符串中所有字母异位词 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> findAnagrams (String s, String p) { Map<Character, Integer> sMap = new HashMap <>(); Map<Character, Integer> pMap = new HashMap <>(); List<Integer> result = new ArrayList <>(); int sLen = s.length(); int pLen = p.length(); if (sLen < pLen) { return result; } for (int i = 0 ; i < pLen; i++) { pMap.put(p.charAt(i), pMap.getOrDefault(p.charAt(i), 0 ) + 1 ); sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0 ) + 1 ); } for (int i = 0 ; i + pLen - 1 < s.length(); i++) { if (compare(sMap, pMap)) { result.add(i); } if (i + pLen < s.length()) { char c = s.charAt(i); if (sMap.get(c) == 1 ) { sMap.remove(c); } else { sMap.put(c, sMap.get(c) - 1 ); } sMap.put(s.charAt(i + pLen), sMap.getOrDefault(s.charAt(i + pLen), 0 ) + 1 ); } } return result; } public boolean compare (Map<Character, Integer> sMap, Map<Character, Integer> pMap) { Map<Character, Integer> map = new HashMap <>(); map.putAll(sMap); for (char c : pMap.keySet()) { map.remove(c, pMap.get(c)); } return map.size() == 0 ; } }
字符串 344.反转字符串 使用左右指针即可
541. 反转字符串II 这道题需要稍微注意以下两个条件的判断即可：
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
以及String对象一旦创建，实体是不可以变化的，即内容不能再修改。所以应该将String转成char[]再操作
165. 比较版本号 一个个比较即可
13. 罗马数字转整数 依次遍历，只需处理每一位是加还是减的逻辑即可
345. 反转字符串中的元音字母 使用双指针left和right指向元音的位置,反转left和right位置即可
动态规划 相关知识 动态规划中每一个状态一定是由上一个状态推导出来的，而贪心是局部直接选最优的。
动态规划方法论：
确定dp[i]数组的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
写动规题目，代码出问题很正常！找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
01背包：
1.dp[i] [j]：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
2.dp[i] [j] = max ( dp[i - 1] [j]不加入物品i , dp[i - 1] [j - weight[i]] + value[i] 加入了物品i );
3.dp[0] [j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0] [j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0] [j] 应该是value[0]，因为背包容量放足够放编号0物品。
如果背包容量j为0的话，即dp[i] [0]，无论是选取哪些物品，背包价值总和一定为0。
4.从推导公式可以看出，每一次dp[i] [j]的确定都需要dp[i - 1] [j]和dp[i - 1] [j - weight[i]]的确定，都在左上角和正上方的方向，所以先i（物品）后j（容量），或者先j后i都可以，推荐使用先i物品后j容量，更加符合我们平时的习惯，而且一定不会错。
进阶：把二维压缩成一维数组： 在使用二维数组的时候，递推公式：
1 dp[i][j] = max(dp[i - 1 ][j], dp[i - 1 ][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i] [j] = max(dp[i] [j], dp[i] [j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了 ，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
1.dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2.那么递推公式为：
1 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3.dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？
看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了 。
那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。
4.遍历顺序：
1 2 3 4 5 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]); } }
倒序遍历是为了保证物品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
再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？
不可以！
因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。
完全背包 而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：
1 2 3 4 5 for (int i = 0 ; i < weight.size(); i++) { for (int j = weight[i]; j <= bagWeight ; j++) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
其中i和j的嵌套顺序是可以改变的
注意！任何一个问题当中，有限的资源/要达到的限制条件是背包的容量，最大化的目标是背包的价值
完全背包的进阶：排列组合问题 如果求组合数就是外层for循环遍历物品，内层for遍历背包
如果求排列数就是外层for遍历背包，内层for循环遍历物品
具体说明：
我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。
代码如下：
1 2 3 4 5 for (int i = 0 ; i < coins.size(); i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } }
假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：
1 2 3 4 5 for (int j = 0 ; j <= amount; j++) { for (int i = 0 ; i < coins.size(); i++) { if (j - coins[i] >= 0 ) dp[j] += dp[j - coins[i]]; } }
背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
509. 斐波那契数 1.dp[i]=斐波那契i位置的数值
2.dp[i]=dp[i-1]+dp[i-2]
3.dp[0]=0,dp[1]=1
4.从左到右遍历
70. 爬楼梯 1.dp[i]爬到i阶梯有多少方法爬到
2.dp[i]=dp[i-1]+dp[i-2]
3.dp[0]=1 dp[1]=1
4.从左到右遍历
746. 使用最小花费爬楼梯 1.dp[i]是爬到楼梯i的最小花费
2.dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3.dp[0]=0 dp[1]=0
4.从左到右遍历
62.不同路径 1.dp[i] [j]到达(i,j)位置有多少路径
2.dp[i] [j]=dp[i-1] [j]+dp[i] [j-1]
3.dp[0] [j]=1 dp[i] [0]=1
4.从左到右，从上到下
63. 不同路径 II 1.dp[i] [j]为到达i,j位置的路径总数
2.dp[i] [j]=dp[i-1] [j]+dp[i] [j-1] dp[障碍物]=0
3.dp[0] [j]=1(如果这一列都没有障碍物，否则在障碍物之后都是0) dp[i] [0]=1（同理）
4.从左向右，从上向下
343. 整数拆分 1.dp[i]表示拆分数字i可以获得的最大乘积
2.dp[i]=max(dp[i-1]×1 , dp[i-2]×2 , , , , dp[1]×(i-1) , (i-1)×1 , (i-2)×2 , , , 1×i)
这里需要注意：==j * (i - j) 是单纯的把整数拆分为两个数相乘==，而 j * dp[i - j]是拆分成两个以及两个以上的个数相乘
3.dp[1]=1
4.i从左到右
96.不同的二叉搜索树 1.dp[i]是i个节点构成的二叉树的个数
2.把任何一个由i个节点构成的二叉树都看成是左+右子树，左子树可以有的节点是0到i-1个，右子树也同理，该树的构成种类是左子树构成种类*右子树构成种类。dp[i]=sum( dp[i-1]×dp[0] , dp[i-2]×dp[1] , , , , )
3.dp[0]=1
4.i从小到大
416. 分割等和子集 01背包问题，背包的容量是sum/2。每个数字的价值是num[j]，每个数字占有容量nums[j]，最后查看sum/2==nums[sum/2]
1.dp[j]是背包容量为j的背包，可以获得的最多的价值
2.dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
3.dp[j]都是0
4.i从小到大，j从大到小
1049.最后一块石头的重量II 转化成sum/2的01背包问题，最后返回sum - 2 * dp[dp.length - 1]
1.dp[i]表示容量为i的背包装下的最大值
2.递推公式是dp[i]=max(dp[i],dp[i-weight]+weight)
3.初始化都是0
4.递推顺序是stone正向,背包反向
279.完全平方数 1.dp[i]表示组成数字i的完全平方数的最小的数量
2.dp[i]=min(dp[i-1],dp[i-4],,,,)+1
3.dp[小于n的完全平方数]=1
4.i从小到大
121. 买卖股票的最佳时机 1.dp[i] [0]表示第i天是不持有股票的状态，所具有的资金
dp[i] [1]表示的是持有股票的状态所具有的资金，初始资金是0
2.dp[i] [0]=max(dp[i-1] [1]+prices[i],dp[i-1] [0])
dp[i] [1]=max(-prices[i],dp[i-1] [1])，题里面只要求买卖一次，所以无论何时购买，资金都是-prices[i]
3.dp[0] [0]=0 dp[0] [1]=-prices[0]
4.i从左到右
122.买卖股票的最佳时机II 1.dp[i] [0]表示第i天不持有股票所持有的最大资金
dp[i] [1]表示第i天持有股票所持有的最大资金
2.dp[i] [0]=max(dp[i-1] [0] , dp[i-1] [1]+prices[i])
dp[i] [1]=max(dp[i-1] [1],dp[i-1] [0]-prices[i])
3.dp[0] [0]=0 dp[0] [1]=-prices[0]
4.i从小到大
123.买卖股票的最佳时机III 1.dp[i] [0]第i天不持有股票，1第一次持有股票，2第一次不持有股票，3第二次持有股票，4第二次不持有股票
2.dp[i] [0]=dp[i-1] [0]
dp[i] [1]=max(dp[i-1] [1],dp[i-1] [0]-prices[i])
dp[i] [2]=max(dp[i-1] [2],dp[i-1] [1]+prices[i])
dp[i] [3]=max(dp[i-1] [3],dp[i-1] [2]-prices[i])
dp[i] [4]=max(dp[i-1] [4],dp[i-1] [3]+prices[i])
3.dp[0] [0]=0 dp[0] [1]=-prices[0] dp[0] [2]=0 dp[0] [3]=-prices[0] dp[0] [4]=0
4.i从小到大
188.买卖股票的最佳时机IV 1.dp[i] [0]是第i天不持有股票，1是第一次持有，2是第一次不持有，，，
2.dp[i] [0]=dp[i-1] [0]
dp[i] [2×k+1]=max(dp[i] [2×k]-prices[i],dp[i-1] [2×k+1])
dp[i] [2×k+2]=max(dp[i] [2×k+1]+prices[i],dp[i-1] [2×k+2])
3.dp[0] [2×k+1]=-prices[0]
dp[0] [2×k]=0
4.i从小到大
714.买卖股票的最佳时机含手续费 1.dp[i] [0]在第i天不持有股票所拥有的资金，1持有
2.dp[i] [0]=max(dp[i-1] [0],dp[i-1] [1]+prices[i]-fee)
dp[i] [1]=max(dp[i-1] [1],dp[i-1] [0]-prices[i])
3.dp[0] [0]=0
dp[0] [1]=-prices[0]
4.i从小到大
647. 回文子串 1.dp[i] [j]表示s当中[i,j]是否是回文串
2.dp[i] [j]= 0(false)；
1(true)当且仅当s[i]=s[j]&&dp[i+1] [j-1]=true，或j=i+1的时候s[i]==s[j]也可以（“aa”）
3.dp[i] [i]=1
4.根据递推公式可以得出，dp[i] [j]根据左下角的值dp[i+1] [j-1]，j从左往右，i从下往上
198.打家劫舍 1.dp[i]表示截止到第i家位置所获得的最大金额
2.dp[i]=max(dp[i-2]+nums[i],dp[i-1])
3.dp[0]=nums[0] dp[1]=max(nums[0],nums[1])
4.i从小到大
213.打家劫舍II 1.dp[i]表示截止到第i家位置所获得的最大金额
2.dp[i]=max(dp[i-2]+nums[i],dp[i-1])
3.dp[0]=nums[0] dp[1]=max(nums[0],nums[1])
4.==i考虑首元素不考虑尾元素来一遍打劫，考虑尾元素不考虑首元素来一遍打劫==
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 class Solution { public int rob (TreeNode root) { int [] dp = robNode(root); return Math.max(dp[0 ], dp[1 ]); } public int [] robNode(TreeNode cur) { if (cur == null ) { return new int [] { 0 , 0 }; } int [] left = robNode(cur.left); int [] right = robNode(cur.right); int [] dp = new int [2 ]; dp[0 ] = Math.max(left[0 ], left[1 ]) + Math.max(right[0 ], right[1 ]); dp[1 ] = cur.val + left[0 ] + right[0 ]; return dp; } }
376. 摆动序列 1.dp[i]表示截止到i位置，当前的摆动序列的最长子序列的长度，[0]表示i作为低位置，[1]表示i作为高位置
2.dp[i] [0]=(nums[i]<nums[i-1])dp[i-1][1]+1 else dp[i-1][0]
dp[i] [1]=(nums[i]>nums[i-1])dp[i-1][0]+1 else dp[i-1][1]
3.dp[0] [0]=1 dp[0] [1]=1
4.i从小到大
53. 最大子序和 1.dp[i]表示截止到i位置(包括i位置)，连续子数组的最大和
2.dp[i]=max(dp[i-1]+nums[i],nums[i])
3.dp[0]=nums[0]
4.i从小到大
注意根据dp[i]的定义，最终结果应该是dp当中的max，而不是dp[len-1]
300.最长递增子序列 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
为什么一定表示 “以nums[i]结尾”的最长递增子序，因为我们在做递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么如何可以算作递增呢。
1.dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
2.dp[i]=(for j<i if(num[j]<num[i]){dp[i]=max(dp[j])+1;})
3.dp[i]=1
4.i从小到大
674. 最长连续递增序列 1.dp[i]表示截至到i位置最长的连续递增子序列（包括i位置）
2.dp[i]=(nums[i]>nums[i-1] dp[i-1]+1) else 1
3.dp[0]=1
4.i从小到大
1143.最长公共子序列 1.dp[i] [j]表示text1的i为止和text2的j为止，最长的公共子序列长度
2.dp[i] [j]=dp[i-1] [j-1]+1(text1[i]==text2[j])/max(dp[i-1] [j],dp[i] [j-1])
3.dp[0] [j]=0,等到text1[0]==text2[j]之后都是1,dp[i] [0]也是同理
4.i从小到大，j从小到大
1035.不相交的线 线的个数就是最长公共子序列的长度，这道题同1143题
718. 最长重复子数组 1.dp[i] [j]表示nums1到i为止，nums2到j为止，最长的公共子数组长度(子数组都是连续的)
2.dp[i] [j]=dp[i-1] [j-1]+1(nums1[i]==nums2[j])，dp[i][j]只能通过这种方式累计
3.dp[0] [j]只有nums1[0]==nums2[j]才是1
4.i从小到大，j从小到大
494.目标和 target=x-(sum-x),x=(target+sum)/2,x是背包的容量
把问题转化成容量为x的背包，装满这个背包的方法有多少
1.dp[j]为把容量为i的背包装满的方式个数
2.dp[j]=+dp[j-nums[i]]
3.dp[0]=1
4.i正向，j逆向
474.一和零 1.dp[i] [j]表示对0是容量m，对1是容量n的背包可以最多装多少字符串
2.dp[i] [j]=max(1+dp[i-char0[k]] [j-char1[k]],dp[i] [j])
3.dp[0] [0]=0
4.i,j都倒序，k遍历字符串在最外面正序
518.零钱兑换II 完全背包问题
1.dp[j]表示容量为j的背包装满的方式有多少
2.dp[j]+=dp[j-coins[i]]
3.dp[0]=1
4.i遍历硬币正向，j遍历背包容量正向
377. 组合总和 Ⅳ 完全背包
1.dp[j]表示容量为j的背包可以装满的方式个数
2.dp[j]+=dp[j-nums[i]]
3.dp[0]=1
4.i正向遍历数字在里面，j正向遍历背包在外面
如果求组合数就是外层for循环遍历物品，内层for遍历背包
如果求排列数就是外层for遍历背包，内层for循环遍历物品
322. 零钱兑换 完全背包问题
1.dp[j]表示装满容量为j的背包的所需要的最小的硬币个数
2.dp[j]=min(dp[j],dp[j-coins[i]]+1),dp[0]=0
3.dp[j]都初始化成amount+1
4.i正向外面，j正向里面
309.最佳买卖股票时机含冷冻期 1.dp[i]表示第i天：0不持有股票且不在冷静期，1不持有股票且在冷静期，2持有股票
2.dp[i] [0]=max(dp[i-1] [0],dp[i-1] [1])
dp[i] [1]=dp[i-1] [2]+prices[i]
dp[i] [2]=max(dp[i-1] [0]-prices[i],dp[i-1] [2])
3.dp[0] [0]=0,dp[0] [1]=0,dp[0] [2]=-prices[0]
4.i从1开始
392.判断子序列 即判断s和t的最长公共子序列的长度是否为s的长度即可
1.dp[i] [j]表示s考虑到i为止，t考虑到j位置的最长公共子序列的长度
2.dp[i] [j]=dp[i-1] [j-1]+1(s.charAt(i)==t.charAt(j)) / Math.max(dp[i] [j-1],dp[i-1] [j])
3.dp[0] [j]=1(s.charAt(0)==t.charAt(j)及以后),dp[i] [0]同理
4.i正向，j正向
115.不同的子序列 s是t的子序列 <=> t删除一些字符之后就是s
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 int numDistinct (String s, String t) { int len1 = s.length(); int len2 = t.length(); int [][] dp = new int [len1][len2]; char s0 = s.charAt(0 ); char t0 = t.charAt(0 ); dp[0 ][0 ] = (s0 == t0) ? 1 : 0 ; for (int i = 1 ; i < len1; i++) { char cur = s.charAt(i); if (cur == t0) { dp[i][0 ] = dp[i - 1 ][0 ] + 1 ; } else { dp[i][0 ] = dp[i - 1 ][0 ]; } } for (int i = 1 ; i < len1; i++) { for (int j = 1 ; j < len2; j++) { if (s.charAt(i) == t.charAt(j)) { dp[i][j] = dp[i - 1 ][j] + dp[i - 1 ][j - 1 ]; } else { dp[i][j] = dp[i - 1 ][j]; } } } return dp[len1 - 1 ][len2 - 1 ]; } }
583. 两个字符串的删除操作 1.dp[i] [j]表示word1考虑到i位置，word2考虑到j位置，使得word1和word2相同所需的最少删除次数
2.if(word1.charAt(i)==word2.charAt(j)) dp[i] [j]=dp[i-1] [j-1]
else dp[i] [j]=min(dp[i-1] [j]+1(删除word1的i位置),
dp[i] [j-1]+1(删除word2的j位置),
dp[i-1] [j-1]+2(删除word1的i位置和word2的j位置，其实这一项是多余的，前两项可以覆盖这个情况))
3.dp[i] [0]是word1考虑到i和word2第一个字符的最小删除操作,dp[0] [j]同理
4.i正向，j正向
72. 编辑距离 1.dp[i] [j]表示word1考虑到i为止，word2考虑到j为止，最少的操作数
2.if(word1.charAt(i)==word2.charAt(j)) dp[i] [j]=dp[i-1] [j-1]
else dp[i] [j]=min
增：不需要额外考虑，对word1的删除，就是对word2的添加，因此删除和添加的操作是等价的
删：删除i位置，dp[i-1] [j]+1；删除j位置，dp[i] [j-1]+1；删除i和j位置都被包括了，可以不考虑了
换：把i位置换成和j一样的(反过来也一样)，那么if(word1.charAt(i)==word2.charAt(j))成立，所以dp[i-1] [j-1]+1
3.dp[0] [j]表示word1第一个字符和word2考虑到j为止，最小的操作数
如果0位置和j相等，dp[0] [j]=j(j这个位置不动，其他位置都要删除)，
如果不相等，dp[0] [j]=j+1(如果目前为止没有一个位置和0位置相等) or
j(否则，删除其他j个位置，只保留和0位置相等的那个地方)
dp[i] [0]同理
4.i正向，j正向
516.最长回文子序列 1.dp[i] [j]表示i到j的最长回文子序列的长度
2.dp[i] [j]=(if s.charAt(i)==s.charAt(j))dp[i+1] [j-1]+2
else max(dp[i-1] [j],dp[i] [j-1])
3.dp[i] [i]=1
4.i逆向，j正向
42. 接雨水 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 trap (int [] height) { int len = height.length; int [] leftDp = new int [len]; int [] rightDp = new int [len]; rightDp[len - 1 ] = height[len - 1 ]; leftDp[0 ] = height[0 ]; for (int i = 1 ; i < len; i++) { leftDp[i] = Math.max(leftDp[i - 1 ], height[i]); } for (int i = len - 2 ; i >= 0 ; i--) { rightDp[i] = Math.max(rightDp[i + 1 ], height[i]); } int size = 0 ; for (int i = 0 ; i < len; i++) { size += Math.min(leftDp[i], rightDp[i]) - height[i]; } return size; } }
64. 最小路径和 1.dp[i] [j]表示走到（i，j）位置的最小路径和
2.dp[i] [j]=min(dp[i-1] [j],dp[i] [j-1])+grid[i] [j]
3.dp[0] [j]=sum(grid[0] [0]到grid[0] [j])，dp[i] [0]同理
4.从上到下，从左到右
45. 跳跃游戏 II 1.dp[i]表示从0跳到i这个位置所需的最少跳跃次数
2.dp[i]=min(dp[j])+1,其中nums[j]>=(i-j)
3.dp[0]=0,dp[i]=Integer.MAX_VALUE
4.i从小到大
560.和为 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 33 34 35 36 37 38 39 class Solution { public int subarraySum (int [] nums, int k) { Map<Integer, Integer> map = new HashMap <>(); int len = nums.length; int result = 0 ; int sum = 0 ; map.put(0 , 1 ); for (int i = 0 ; i < len; i++) { sum += nums[i]; result += map.getOrDefault(sum - k, 0 ); map.put(sum, map.getOrDefault(sum, 0 ) + 1 ); } return result; } }
139. 单词拆分 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 wordBreak (String s, List<String> wordDict) { int len = s.length(); Set<String> wordSet = new HashSet <>(wordDict); boolean [] dp = new boolean [len + 1 ]; dp[0 ] = true ; for (int i = 1 ; i < len + 1 ; i++) { for (int j = 0 ; j <= i - 1 ; j++) { if (dp[j] && check(wordSet, s, j, i - 1 )) { dp[i] = true ; break ; } } } return dp[len]; } public boolean check (Set<String> wordSet, String s, int i, int j) { String str = s.substring(i, j + 1 ); if (wordSet.contains(str)) { return true ; } else { return false ; } } }
5. 最长回文子串 1.dp[i] [j]表示i到j位置是否是回文子串
2.dp[i] [j]=dp[i+1] [j-1]&&s[i]==s[j]
3.dp[i] [i]=true dp[i] [i+1]=s[i]==s[i+1]
4.i从大到小，j从小到大
221. 最大正方形 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public int maximalSquare (char [][] matrix) { int m = matrix.length; int n = matrix[0 ].length; int r = 0 ; int [][] dp = new int [m][n]; dp[0 ][0 ] = matrix[0 ][0 ] == '0' ? 0 : 1 ; r = Math.max(r, dp[0 ][0 ]); for (int i = 1 ; i < m; i++) { if (matrix[i][0 ] == '1' ) { dp[i][0 ] = 1 ; } r = Math.max(r, dp[i][0 ]); } for (int i = 1 ; i < n; i++) { if (matrix[0 ][i] == '1' ) { dp[0 ][i] = 1 ; } r = Math.max(r, dp[0 ][i]); } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { if (dp[i][j - 1 ] > 0 && dp[i - 1 ][j] > 0 && dp[i - 1 ][j - 1 ] > 0 && matrix[i][j] == '1' ) { dp[i][j] = Math.min(Math.min(dp[i - 1 ][j], dp[i][j - 1 ]), dp[i - 1 ][j - 1 ]) + 1 ; } else if (matrix[i][j] == '1' ) { dp[i][j] = 1 ; } else if (matrix[i][j] == '0' ) { dp[i][j] = 0 ; } r = Math.max(r, dp[i][j]); } } return r * r; } }
1137. 第 N 个泰波那契数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int tribonacci (int n) { if (n == 0 ) { return 0 ; } else if (n == 1 || n == 2 ) { return 1 ; } int result = 0 ; int num0 = 0 ; int num1 = 1 ; int num2 = 1 ; for (int i = 3 ; i <= n; i++) { result = num0 + num1 + num2; num0 = num1; num1 = num2; num2 = result; } return result; }
120. 三角形最小路径和 1.dp[i] [j]表示到达第i个链表（第i行）的j下标位置的最小路径和
2.dp[i] [j]=(if j<=i-1)min(dp[i-1] [j],dp[i-1] [j-1])+triangle[i] [j]
else dp[i] [i]=dp[i-1] [i-1]+triangle.get(i).get(i);
3.dp[i] [0]=sum(triangle[0] [0]到triangle[i] [0])
4.i从1到n，j从1到i
931. 下降路径最小和 1.dp[i] [j]表示到达位置(i,j)所需的最小路径和
2.dp[i] [j]=min(dp[i-1] [j-1],dp[i-1] [j],dp[i-1] [j+1])+matrix[i] [j]
dp[i] [0]=min(dp[i-1] [0],dp[i-1] [1])+matrix[i] [0]
dp[i] [n-1]=min(dp[i-1] [n-2],dp[i-1] [n-1])+matrix[i] [n-1]
3.dp[0] [j]=matrix[0] [j]
4.i从1到n，j从0到n-1
673. 最长递增子序列的个数 1.dp0[i]表示到i为止的最长递增子序列的长度
2.dp0[i]=max(dp0[j])+1 (if nums[j]<nums[i])
3.dp0[i]=1
4.i从小到大
1.dp1[i]表示到i为止的最长递增子序列的个数
2.dp1[i]=sum(dp1[j]) (if nums[j]<nums[i]&& dp0[j]==dp0[i]-1) 如果dp1[i]为0，赋值为1
3.dp1[0]=1
4.i从小到大
91. 解码方法 1.dp[i]表示到i为止，编码方法的总数
2.(if s[i]>’0’) dp[i]+=dp[i-1]
(if s[i-1] == ‘1’ or s[i-1] == ‘2’ && s[i]<=’6’ && s[i]>=’0’) dp[i]+=dp[i-2]
else:return 0
3.dp[0]=1
4.i从小到大
1218. 最长定差子序列 1.dp[i]表示到i为止的最长定差子序列的长度
2.dp[i]= (if exists arr[j]==arr[i]-difference) dp[j]+1 else 1
3.dp[0]=1
4.i从小到大
646. 最长数对链 1.dp[i]表示考虑到i为止，最长的数对链的长度
2.dp[i]=max(dp[j])+1,(if pairs[j] [1]<pairs[i] [0])
3.dp[i]=1
4.i从小到大
2466. 统计构造好字符串的方案数 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 countGoodStrings (int low, int high, int zero, int one) { final int MOD = 1_000_000_007 ; int [] dp = new int [high + 1 ]; dp[0 ] = 1 ; for (int i = 1 ; i <= high; i++) { if (i - one >= 0 ) { dp[i] = (dp[i] + dp[i - one]) % MOD; } if (i - zero >= 0 ) { dp[i] = (dp[i] + dp[i - zero]) % MOD; } } int result = 0 ; for (int i = low; i <= high; i++) { result = (result + dp[i]) % MOD; } return result; } }
740. 删除并获得点数 构造数组me,me[i]=nums当中出现数字i的次数*数字i
1.dp[i]表示考虑到数字i为止获得的最大点数
2.dp[i]=max(dp[i-2]+me[i],dp[i-1])
3.dp[1]=me[1],dp[2]=max(me[1],me[2])
4.i从小到大
790. 多米诺和托米诺平铺 1.dp[i]表示考虑第i列的多米诺排列情况（其中前i-1列都是排满的）
标号：[0] (上空下空) [1] (上·下空) [2] (上空下·) [3] (上·下·)
2.dp[i] [0]=dp[i-1] [3]
dp[i] [1]=dp[i-1] [0]+dp[i-1] [2]
dp[i] [2]=dp[i-1] [0]+dp[i-1] [1]
dp[i] [3]=dp[i-1] [3]+dp[i-1] [1]+dp[i-1] [2]+dp[i-1] [0]
3.dp[0] [0]=0,dp[0] [1]=0,dp[0] [2]=0,dp[0] [3]=1
4.i从小到大
712. 两个字符串的最小ASCII删除和 1.dp[i] [j]表示s1考虑到i，s2考虑到j的最小删除ASCII的最小值
注意：这道题当中我们认为范围是左闭右开，即dp[0] [0]表示的是s1和s2都是空串（这样是方便dp[0][j]和dp[i][0]）
2.dp[i] [j]=(if s1[i]==s2[j]) dp[i-1] [j-1]
dp[i] [j]=else min(dp[i] [j-1]+ascii(s2[j]),dp[i-1] [j]+ascii(s1[i]))
3.dp[0] [0]= 0 因为s1和s2都是空串，一定相等
s1是空串，s2是[0,,j)也就是[0,,j-1]，为了让s2变成空串(s1)，那么s2之内全都删除
dp[0] [j]=dp[0] [j-1]+s2[j]
dp[i] [0]=dp[i-1] [0]+s1[i]
4.i从小到大，j从小到大
983. 最低票价 1.dp[i]表示考虑到第i天为止，所需的最低消费
注意：定义最后一天付费，即如果购买为期7天的通行证，希望从1天到7天无限通行，那么不在1天付钱，而是在7天付钱
2.dp[i]=(if days包含i)min(dp[i-1]+costs[0],dp[i-7]+costs[1],dp[i-30]+costs[2])
else dp[i]=dp[i-1]
3.dp[0]=0
4.i从小到大
栈与队列 20. 有效的括号 构建一个栈，只有栈顶是左括号，要加入的是右括号的时候，让栈弹出，否则就push进去。最后查看栈是否是空栈
1047. 删除字符串中的所有相邻重复项 构建一个栈，只有栈顶元素和要加入的元素相同的时候，让栈弹出，否则就push进去。也可以使用快慢指针（转成字符数组，用快指针处的元素覆盖慢指针处的怨怒是），或者直接在字符串上进行修改（转成StringBuilder或者StringBuffer，直接删除元素）
150. 逆波兰表达式求值 遇到加减乘除就连续pop两次，计算结果之后再压栈
347.前 K 个高频元素 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int [] topKFrequent(int [] nums, int k) { Map<Integer, Integer> me = new HashMap <>(); for (int i = 0 ; i < nums.length; i++) { me.put(nums[i], me.getOrDefault(nums[i], 0 ) + 1 ); } Queue<int []> qu = new PriorityQueue <>((o1, o2) -> o2[1 ] - o1[1 ]); for (int num : me.keySet()) { qu.add(new int [] { num, me.get(num) }); } int [] result = new int [k]; for (int i = 0 ; i < k; i++) { result[i] = qu.poll()[0 ]; } return result; } }
394. 字符串解码 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 class Solution { public String decodeString (String s) { Stack<String> stack = new Stack <>(); for (int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == ']' ) { String str = stack.pop(); while (!stack.peek().equals("[" )) { str = stack.pop() + str; } stack.pop(); int times = Integer.valueOf(stack.pop()); stack.push(str.repeat(times)); } else { if (s.charAt(i) >= '0' && s.charAt(i) <= '9' ) { int num = 0 ; num = 10 * num + s.charAt(i) - '0' ; i++; while (s.charAt(i) >= '0' && s.charAt(i) <= '9' ) { num = 10 * num + s.charAt(i) - '0' ; i++; } stack.push(num + "" ); System.out.print(stack.peek() + ";" ); if (s.charAt(i) < '0' || s.charAt(i) > '9' ) { stack.push(s.charAt(i) + "" ); } } else { stack.push(s.charAt(i) + "" ); } } } String result = "" ; while (!stack.isEmpty()) { result = stack.pop() + result; } System.out.println(result); return result; } }
贪心算法 455.分发饼干 把最大的饼干给最饿的孩子，如果满足不了最饿的孩子，就给第二饿的孩子
860.柠檬水找零 只需要记录5的零钱个数，和10的零钱个数即可。需要注意，给20找零15元的时候，有两种找零方式：10+5或者5*3
135. 分发糖果 动态规划:
1.dp[i]表示第i个孩子分到多少糖
2.dp[i]=if(ratings[i]>ratings[i-1])dp[i-1]+1 else 1
3.dp[i]=1,dp[0]和dp[1]单独赋值
4.i从小到大来一遍，从大到小来一遍
55. 跳跃游戏 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 boolean canJump (int [] nums) { int len = nums.length; int target = len - 1 ; int i = len - 2 ; while (i >= 0 ) { while (i >= 0 && nums[i] < target - i) { i--; } if (i < 0 ) { return false ; } target = i; i--; } return true ; } }
1005.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 class Solution { public int largestSumAfterKNegations (int [] nums, int k) { nums = IntStream.of(nums) .boxed() .sorted((o1, o2) -> Math.abs(o1) - Math.abs(o2)) .mapToInt(Integer::intValue).toArray(); for (int i = nums.length - 1 ; i >= 0 ; i--) { if (nums[i] < 0 && k > 0 ) { nums[i] *= -1 ; k--; } } if (k % 2 == 1 ) { nums[0 ] *= -1 ; } int result = 0 ; for (int num : nums) { result += num; } return result; } }
452. 用最少数量的箭引爆气球 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int findMinArrowShots (int [][] points) { Arrays.sort(points, (a, b) -> { return Integer.compare(a[0 ], b[0 ]); }); int result = 0 ; for (int i = 0 ; i < points.length; i++) { while (i + 1 < points.length && points[i + 1 ][0 ] <= points[i][1 ]) { points[i + 1 ][1 ] = Math.min(points[i + 1 ][1 ], points[i][1 ]); i++; } result++; } return result; } }
435. 无重叠区间 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int eraseOverlapIntervals (int [][] intervals) { Arrays.sort(intervals, (a, b) -> { return a[0 ] - b[0 ]; }); int result = 0 ; for (int i = 0 ; i < intervals.length; i++) { while (i + 1 < intervals.length && intervals[i][1 ] > intervals[i + 1 ][0 ]) { intervals[i+1 ][1 ] = Math.min(intervals[i][1 ], intervals[i + 1 ][1 ]); result++; i++; } } return result; } }
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 31 class Solution { public List<Integer> partitionLabels (String s) { int [] me = new int [26 ]; Arrays.fill(me, -1 ); for (int i = 0 ; i < s.length(); i++) { char c = s.charAt(i); me[c - 'a' ] = Math.max(me[c - 'a' ], i); } List<Integer> result = new ArrayList <>(); int start = 0 ; int end = 0 ; for (int i = 0 ; i < s.length();) { char c = s.charAt(i); end = Math.max(end, me[c - 'a' ]); i++; while (i <= end) { char d = s.charAt(i); end = Math.max(end, me[d - 'a' ]); i++; } result.add(end - start + 1 ); start = i; end = i; } return result; } }
56. 合并区间 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int [][] merge(int [][] intervals) { List<int []> result = new ArrayList <>(); Arrays.sort(intervals, (a, b) -> a[0 ] - b[0 ]); for (int i = 0 ; i < intervals.length; i++) { int start = intervals[i][0 ]; int end = intervals[i][1 ]; while (i + 1 < intervals.length && end >= intervals[i + 1 ][0 ]) { end = Math.max(end, intervals[i + 1 ][1 ]); i++; } result.add(new int [] { start, end }); } return result.toArray(new int [result.size()][]); } }
738.单调递增的数字 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 monotoneIncreasingDigits (int n) { String numStr = n + "" ; int len = numStr.length(); int [] num = new int [len]; int flag = len; for (int i = len - 1 ; i >= 0 ; i--) { num[i] = n % 10 ; n = n / 10 ; } for (int i = len - 1 ; i > 0 ; i--) { if (num[i - 1 ] > num[i]) { num[i - 1 ]--; flag = i; } } int result = 0 ; for (int i = 0 ; i < len; i++) { if (i >= flag) { num[i] = 9 ; } result = 10 * result + num[i]; } return result; } }
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 40 41 42 43 44 class Solution { int result = 0 ; public int minCameraCover (TreeNode root) { if (3 == minCamera(root)) { result++; } return result; } public int minCamera (TreeNode root) { if (root.left == null && root.right == null ) { return 3 ; } int state = 0 ; int leftState = 0 ; int rightState = 0 ; if (root.left != null ) { leftState = minCamera(root.left); } if (root.right != null ) { rightState = minCamera(root.right); } if (leftState == 3 || rightState == 3 ) { result++; state = 2 ; } else if (leftState == 2 || rightState == 2 ) { state = 1 ; } else { state = 3 ; } return state; } }
回溯算法 相关知识 回溯本质上是一种纯暴力搜索算法，常用来解决排列组合、子集问题、切割字符串、棋牌问题。
这里注意一定要画出树，再写代码。 树的宽度是回溯处理的集合的大小，树的深度就是递归的深度。
伪代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 void backtracking (参数) { if (终止条件/叶子节点){ 收集结果; return ; } for (集合的元素集){ 处理每一层的节点; 递归函数; 回溯操作/撤销递归的效果; } }
回溯三部曲：
1.递归函数的参数和返回值
2.终止条件
3.单层递归/搜索的逻辑
77.组合 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> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> combine (int n, int k) { backtracking(k, n, 1 ); return result; } public void backtracking (int k, int n, int start) { if (path.size() == k) { result.add(new ArrayList <>(path)); return ; } for (int i = start; i <= n; i++) { path.add(i); backtracking(k, n, i + 1 ); path.remove(Integer.valueOf(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 class Solution { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> combine (int n, int k) { backtracking(k, n, 1 ); return result; } public void backtracking (int k, int n, int start) { if (path.size() == k) { result.add(new ArrayList <>(path)); return ; } for (int i = start; i <= n - (k - path.size()) + 1 ; i++) { path.add(i); backtracking(k, n, i + 1 ); path.remove(Integer.valueOf(i)); } } }
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 class Solution { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> combinationSum3 (int k, int n) { backtracking(k, n, 1 , 0 ); return result; } public void backtracking (int k, int n, int start, int sum) { if (path.size() == k && sum == n) { result.add(new ArrayList (path)); return ; } for (int i = start; i <= 9 ; i++) { if (path.size() + 9 - i + 1 < k) { return ; } path.add(i); backtracking(k, n, i + 1 , sum + i); path.removeLast(); } } }
17.电话号码的字母组合 这道题需要注意，每一个for处理的都是每一层的元素的共性操作 ，需要注意backtracking的操作要分的清楚：
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 { String path = "" ; List<String> result = new ArrayList <>(); String[] me = { "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz" }; public List<String> letterCombinations (String digits) { if (digits.length() == 0 ) { return result; } backtracking(digits, 0 ); return result; } public void backtracking (String digits, int i) { if (i >= digits.length()) { result.add(new String (path)); return ; } String data = me[digits.charAt(i) - '2' ]; for (int j = 0 ; j < data.length(); j++) { path += data.charAt(j) + "" ; backtracking(digits, i + 1 ); path = path.substring(0 , path.length() - 1 ); } } }
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 44 45 46 47 48 49 50 51 52 class Solution { List<String> path = new ArrayList <>(); List<List<String>> result = new ArrayList <>(); public List<List<String>> partition (String s) { int [][] dp = huiwen(s); backtracking(s, 0 , dp); return result; } public void backtracking (String s, int start, int [][] dp) { if (start >= s.length()) { result.add(new ArrayList (path)); return ; } for (int i = start; i < s.length(); i++) { if (dp[start][i] == 1 ) { path.add(s.substring(start, i + 1 )); backtracking(s, i + 1 , dp); path.removeLast(); } else { continue ; } } } public int [][] huiwen(String s) { int len = s.length(); int [][] dp = new int [len][len]; for (int i = 0 ; i < len; i++) { dp[i][i] = 1 ; } for (int i = len - 1 ; i >= 0 ; i--) { for (int j = i + 1 ; j < len; j++) { if (s.charAt(i) == s.charAt(j)) { if (j == i + 1 ) { dp[i][j] = 1 ; } else { dp[i][j] = dp[i + 1 ][j - 1 ]; } } } } return dp; } }
39. 组合总和 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> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> combinationSum (int [] candidates, int target) { Arrays.sort(candidates); backtracking(0 , 0 , target, candidates); return result; } public void backtracking (int sum, int start, int target, int [] candidates) { if (sum == target) { result.add(new ArrayList <>(path)); return ; } for (int i = start; i < candidates.length && sum + candidates[i] <= target; i++) { path.add(candidates[i]); backtracking(sum + candidates[i], i, target, candidates); path.removeLast(); } } }
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 class Solution { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> combinationSum2 (int [] candidates, int target) { Arrays.sort(candidates); backtracking(candidates, target, 0 , 0 ); return result; } public void backtracking (int [] candidates, int target, int start, int sum) { if (sum == target) { result.add(new ArrayList <>(path)); return ; } for (int i = start; i < candidates.length && sum + candidates[i] <= target; i++) { if (i > start && candidates[i] == candidates[i - 1 ]) { continue ; } path.add(candidates[i]); backtracking(candidates, target, i + 1 , sum + candidates[i]); path.removeLast(); } } }
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 class Solution { String path = "" ; List<String> result = new ArrayList <>(); public List<String> restoreIpAddresses (String s) { backtracking(s, 0 , 1 ); return result; } public void backtracking (String s, int start, int index) { if (index == 5 && start >= s.length()) { result.add(new String (path.substring(0 , path.length() - 1 ))); return ; } for (int i = start; i < s.length() && i <= start + 3 ; i++) { String str = s.substring(start, i + 1 ); if (index > 4 ) { return ; } if (valid(str) == false || s.length() - i - 1 > (4 - index) * 3 ) { continue ; } String nowPath = path; path = path + str + "." ; backtracking(s, i + 1 , index + 1 ); path = nowPath; } } public boolean valid (String str) { if (str.length() >= 4 ) { return false ; } if (str.charAt(0 ) == '0' && str.length() > 1 ) { return false ; } int num = Integer.valueOf(str); if (num > 255 || num < 0 ) { return false ; } return true ; } }
78.子集 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 { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> subsets (int [] nums) { backtracking(nums, 0 ); return result; } public void backtracking (int [] nums, int start) { if (start <= nums.length) { result.add(new ArrayList <>(path)); } if (start == nums.length) { return ; } for (int i = start; i < nums.length; i++) { path.add(nums[i]); backtracking(nums, i + 1 ); path.removeLast(); } } }
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 { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> subsetsWithDup (int [] nums) { Arrays.sort(nums); backtracking(nums, 0 ); return result; } public void backtracking (int [] nums, int start) { if (start <= nums.length) { result.add(new ArrayList <>(path)); } if (start == nums.length) { return ; } for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i - 1 ]) { continue ; } path.add(nums[i]); backtracking(nums, i + 1 ); path.removeLast(); } } }
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 class Solution { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> findSubsequences (int [] nums) { backtracking(nums, 0 , -101 ); return result; } public void backtracking (int [] nums, int start, int compare) { if (path.size() >= 2 ) { result.add(new ArrayList <>(path)); } if (start == nums.length) { return ; } HashSet<Integer> set = new HashSet <>(); for (int i = start; i < nums.length; i++) { if (nums[i] < compare) { continue ; } if (set.contains(nums[i])) { continue ; } set.add(nums[i]); path.add(nums[i]); backtracking(nums, i + 1 , nums[i]); path.removeLast(); } } }
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 class Solution { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> permute (int [] nums) { int [] used = new int [nums.length]; backtracking(nums, used); return result; } public void backtracking (int [] nums, int [] used) { if (path.size() == nums.length) { result.add(new ArrayList <>(path)); return ; } for (int i = 0 ; i < nums.length; i++) { if (used[i] == 1 ) { continue ; } path.add(nums[i]); used[i] = 1 ; backtracking(nums, used); path.removeLast(); used[i] = 0 ; } } }
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 class Solution { List<Integer> path = new ArrayList <>(); List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> permuteUnique (int [] nums) { Arrays.sort(nums); int [] used = new int [nums.length]; backtracking(nums, used); return result; } public void backtracking (int [] nums, int [] used) { if (path.size() == nums.length) { result.add(new ArrayList <>(path)); return ; } for (int i = 0 ; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1 ] && used[i - 1 ] == 0 ) { continue ; } if (used[i] == 1 ) { continue ; } used[i] = 1 ; path.add(nums[i]); backtracking(nums, used); used[i] = 0 ; path.removeLast(); } } }
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 class Solution { public void solveSudoku (char [][] board) { backtracking(board); } public boolean backtracking (char [][] board) { for (int i = 0 ; i < 9 ; i++) { for (int j = 0 ; j < 9 ; j++) { if (board[i][j] == '.' ) { for (int k = 1 ; k <= 9 ; k++) { if (vaild(board, i, j, k)) { board[i][j] = (char ) (k + '0' ); boolean success = backtracking(board); if (success) { return true ; } board[i][j] = '.' ; } } return false ; } } } return true ; } public boolean vaild (char [][] board, int i, int j, int k) { char charK = (char ) (k + '0' ); for (int m = 0 ; m < 9 ; m++) { if (board[m][j] == charK) { return false ; } if (board[i][m] == charK) { return false ; } } int newI = (i / 3 ) * 3 ; int newJ = (j / 3 ) * 3 ; for (int m = newI; m < newI + 3 ; m++) { for (int n = newJ; n < newJ + 3 ; n++) { if (board[m][n] == charK) { return false ; } } } return true ; } }
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 62 63 64 65 66 67 68 class Solution { List<List<String>> result = new ArrayList <>(); public List<List<String>> solveNQueens (int n) { int [][] board = new int [n][n]; backtracking(board, n, 0 ); return result; } public void backtracking (int [][] board, int n, int i) { if (i == n) { result.add(convert(board, n)); return ; } for (int j = 0 ; j < n; j++) { if (board[i][j] == 1 ) { continue ; } if (vaild(board, i, j, n)) { board[i][j] = 1 ; backtracking(board, n, i + 1 ); board[i][j] = 0 ; } } } public List<String> convert (int [][] board, int n) { List<String> result = new ArrayList <>(); for (int i = 0 ; i < n; i++) { String str = "" ; for (int j = 0 ; j < n; j++) { if (board[i][j] == 1 ) { str = str + "Q" ; } else { str = str + "." ; } } result.add(str); } return result; } public boolean vaild (int [][] board, int i, int j, int n) { for (int m = 0 ; m < n; m++) { if (board[m][j] == 1 ) { return false ; } } for (int newI = i, newJ = j; newI >= 0 && newJ >= 0 ; newI--, newJ--) { if (board[newI][newJ] == 1 ) { return false ; } } for (int newI = i, newJ = j; newI >= 0 && newJ < n; newI--, newJ++) { if (board[newI][newJ] == 1 ) { return false ; } } return true ; } }
332.重新安排行程 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 class Solution { private List<String> res = new ArrayList <>(); private Map<String, Map<String, Integer>> map = new TreeMap <String, Map<String, Integer>>(); private boolean backTracking (int ticketNum) { if (res.size() == ticketNum + 1 ) { return true ; } String last = res.getLast(); if (map.containsKey(last)) { for (Map.Entry<String, Integer> target : map.get(last).entrySet()) { int count = target.getValue(); if (count > 0 ) { res.add(target.getKey()); target.setValue(count - 1 ); if (backTracking(ticketNum)) return true ; res.removeLast(); target.setValue(count); } } } return false ; } public List<String> findItinerary (List<List<String>> tickets) { for (List<String> t : tickets) { Map<String, Integer> temp = new TreeMap <>(); if (map.containsKey(t.get(0 ))) { temp = map.get(t.get(0 )); temp.put(t.get(1 ), temp.getOrDefault(t.get(1 ), 0 ) + 1 ); } else { temp.put(t.get(1 ), 1 ); } map.put(t.get(0 ), temp); } res.add("JFK" ); backTracking(tickets.size()); return res; } }
79. 单词搜索 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 { boolean result = false ; public boolean exist (char [][] board, String word) { int m = board.length; int n = board[0 ].length; int [][] isUsed = new int [m][n]; for (int i = 0 ; i < m; i++) { for (int j = 0 ; j < n; j++) { func(board, i, j, word, 0 , isUsed); } } return result; } public void func (char [][] board, int i, int j, String word, int k, int [][] isUsed) { if (i >= board.length || j >= board[0 ].length || i < 0 || j < 0 ) { return ; } if (isUsed[i][j] == 1 ) { return ; } if (k == word.length() - 1 && board[i][j] == word.charAt(k)) { result = true ; return ; } isUsed[i][j] = 1 ; if (board[i][j] == word.charAt(k)) { func(board, i + 1 , j, word, k + 1 , isUsed); func(board, i - 1 , j, word, k + 1 , isUsed); func(board, i, j + 1 , word, k + 1 , isUsed); func(board, i, j - 1 , word, k + 1 , isUsed); } else { isUsed[i][j] = 0 ; return ; } isUsed[i][j] = 0 ; } }
数学 1356. 根据数字二进制下 1 的数目排序 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 [] sortByBits(int [] arr) { return Arrays.stream(arr).boxed().sorted(new Comparator <Integer>() { @Override public int compare (Integer num1, Integer num2) { int a = count1(num1); int b = count1(num2); return (a == b) ? Integer.compare(num1, num2) : Integer.compare(a, b); } }).mapToInt(Integer::intValue).toArray(); } public int count1 (int num) { int count = 0 ; while (num != 0 ) { num = num & (num - 1 ); count++; } return count; } }
7. 整数反转 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int reverse (int x) { int flag = x >= 0 ? 1 : -1 ; int result = 0 ; x = Math.abs(x); while (x > 0 ) { int i = x % 10 ; if (result > Integer.MAX_VALUE / 10 ) { return 0 ; } result = result * 10 + i; x = x / 10 ; } return flag * result; } }
136. 只出现一次的数字 异或即可
461. 汉明距离 先按位异或，再通过z和(z-1)与来判断有多少个1
338. 比特位计数 使用x&(x-1)来确定1的个数
66. 加一 如果是99..9，那么结果数组就要多一位
单调栈 739. 每日温度 我们在遍历到i位置的时候，需要查看i之前的元素有没有比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 class Solution { public int [] dailyTemperatures(int [] temperatures) { int len = temperatures.length; int [] result = new int [len]; Stack<Integer> stack = new Stack <>(); for (int i = 0 ; i < len; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int j = stack.pop(); result[j] = i - j; } stack.push(i); } while (!stack.isEmpty()) { result[stack.pop()] = 0 ; } return result; } }
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 26 27 28 29 class Solution { public int [] nextGreaterElement(int [] nums1, int [] nums2) { Stack<Integer> stack = new Stack <>(); stack.push(nums2[0 ]); int len1 = nums1.length; int len2 = nums2.length; int [] result = new int [len1]; Arrays.fill(result, -1 ); Map<Integer, Integer> map = new HashMap <>(); for (int i = 0 ; i < len1; i++) { map.put(nums1[i], i); } int j = 1 ; while (j < len2) { while (!stack.isEmpty() && stack.peek() < nums2[j]) { int num = stack.pop(); if (map.containsKey(num)) { result[map.get(num)] = nums2[j]; } } stack.push(nums2[j]); j++; } return result; } }
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) { Stack<Integer> stack = new Stack <>(); int len = nums.length; int [] result = new int [len]; Arrays.fill(result, -1 ); stack.add(0 ); for (int j = 1 ; j < len * 2 ; j++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[j % len]) { int num = stack.pop(); result[num] = nums[j % len]; } stack.push(j % len); } return result; } }
84.柱状图中最大的矩形 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 int largestRectangleArea (int [] heights) { int len = heights.length; int [] right = new int [len]; int [] left = new int [len]; Arrays.fill(right, len); Arrays.fill(left, -1 ); Stack<Integer> rightStack = new Stack <>(); Stack<Integer> leftStack = new Stack <>(); for (int i = 0 ; i < len; i++) { while (!rightStack.isEmpty() && heights[rightStack.peek()] > heights[i]) { int index = rightStack.pop(); right[index] = i; } rightStack.push(i); } for (int i = len - 1 ; i >= 0 ; i--) { while (!leftStack.isEmpty() && heights[leftStack.peek()] > heights[i]) { int index = leftStack.pop(); left[index] = i; } leftStack.push(i); } int [] size = new int [len]; int result = 0 ; for (int i = 0 ; i < len; i++) { size[i] = (right[i] - left[i] - 1 ) * heights[i]; System.out.print(size[i] + " " ); result = Math.max(result, size[i]); } return result; } }
二叉树 94.二叉树的中序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public List<Integer> inorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); Stack<TreeNode> stack = new Stack <>(); TreeNode cur = root; while (!stack.isEmpty() || cur != null ) { if (cur != null ) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); result.add(cur.val); cur = cur.right; } } return result; } }
144.二叉树的前序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public List<Integer> preorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); Stack<TreeNode> stack = new Stack <>(); stack.add(root); while (!stack.isEmpty()) { TreeNode temp = stack.pop(); if (temp == null ) { continue ; } result.add(temp.val); stack.push(temp.right); stack.push(temp.left); } return result; } }
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 <>(); Stack<TreeNode> stack = new Stack <>(); stack.add(root); while (!stack.isEmpty()) { TreeNode temp = stack.pop(); if (temp == null ) { continue ; } result.add(temp.val); stack.push(temp.left); stack.push(temp.right); } Collections.reverse(result); return result; } }
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 28 29 30 class Solution { public List<List<Integer>> levelOrder (TreeNode root) { Deque<TreeNode> queue = new LinkedList <>(); List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); if (root == null ) { return result; } queue.add(root); TreeNode last = root; while (!queue.isEmpty()) { TreeNode temp = queue.removeFirst(); path.add(temp.val); if (temp.left != null ) { queue.add(temp.left); } if (temp.right != null ) { queue.add(temp.right); } if (temp == last) { last = queue.peekLast(); result.add(path); path = new ArrayList <>(); } } return result; } }
107. 二叉树的层序遍历 II 层序遍历加入result之后，再把result翻转即可
199. 二叉树的右视图 即返回每一层的最后一个节点
637. 二叉树的层平均值 维护一个变量累计每一层的val即可
这里注意关于Double的处理。题目当中TreeNode.val是整数，如果sum也定义成int再double(sum)强转的话，sum可能会溢出。所以不如直接把sum设为Double：
429. N 叉树的层序遍历 只需要注意遍历n叉树的子节点和二叉树的不同即可，具体要看题目里面是怎么定义子节点的
515. 在每个树行中找最大值 层序遍历，每一层只需要维护一个最大值即可
注意max的初始化：
1 int max = Integer.MIN_VALUE;
116.填充每个节点的下一个右侧节点指针 这个函数的意思是把以root为根节点的子树的next指针都处理完毕，最后返回root。
需要维护pre指针指向当前节点temp的前序节点，并且规定每一层第一个节点为temp时，pre是空
117. 填充每个节点的下一个右侧节点指针 II 同上题
104. 二叉树的最大深度 可以通过层序遍历，记录层数即可
111. 二叉树的最小深度 可以通过层序遍历，最先遇到叶子节点的层数就是最小深度
226. 翻转二叉树 前序遍历，递归写法即可
101. 对称二叉树 前序遍历，递归比较的是compare(root1.left, root2.right) && compare(root1.right, root2.left);
559. N 叉树的最大深度 递归写法即可
222. 完全二叉树的节点个数 递归即可
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 class Solution { List<String> result = new ArrayList <>(); String path = "" ; public List<String> binaryTreePaths (TreeNode root) { paths(root); return result; } public void paths (TreeNode root) { if (root.left == null && root.right == null ) { path = path + root.val; result.add(path); return ; } path = path + root.val + "->" ; String temp = path; if (root.left != null ) { paths(root.left); } path = temp; if (root.right != null ) { paths(root.right); } } }
404. 左叶子之和 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 { int result = 0 ; public int sumOfLeftLeaves (TreeNode root) { sum(root); return result; } public void sum (TreeNode root) { if (root == null ) { return ; } if (root.left != null && root.left.left == null && root.left.right == null ) { result += root.left.val; } if (root.left != null ) { sum(root.left); } if (root.right != null ) { sum(root.right); } } }
513. 找树左下角的值 层序遍历，每到新的一层更新最左下的节点即可
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 class Solution { public boolean hasPathSum (TreeNode root, int targetSum) { if (root == null ) { return false ; } return has(root, targetSum); } public boolean has (TreeNode root, int target) { if (root.left == null && root.right == null ) { return root.val == target; } boolean left = false ; if (root.left != null ) { left = has(root.left, target - root.val); } boolean right = false ; if (root.right != null ) { right = has(root.right, target - root.val); } return left || right; } }
110. 平衡二叉树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public boolean isBalanced (TreeNode root) { if (root == null ) { return true ; } if (Math.abs(compute(root.left) - compute(root.right)) >= 2 ) { return false ; } else { return isBalanced(root.left) && isBalanced(root.right); } } public int compute (TreeNode root) { if (root == null ) { return 0 ; } return Math.max(compute(root.left), compute(root.right)) + 1 ; } }
617. 合并二叉树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public TreeNode mergeTrees (TreeNode root1, TreeNode root2) { return merge(root1, root2); } public TreeNode merge (TreeNode root1, TreeNode root2) { if (root1 == null ) { return root2; } if (root2 == null ) { return root1; } TreeNode result = new TreeNode (0 ); result.val = root1.val + root2.val; result.left = merge(root1.left, root2.left); result.right = merge(root1.right, root2.right); return result; } }
236. 二叉树的最近公共祖先 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) { if (root == p || root == q || root == null ) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null ) { return root; } else if (left == null && right != null ) { return right; } else { return left; } } }
501. 二叉搜索树中的众数 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 { List<Integer> list = new ArrayList <>(); public int [] findMode(TreeNode root) { search(root); int count = 0 ; int maxCount = 0 ; int pre = list.get(0 ); List<Integer> result = new ArrayList <>(); for (int i = 0 ; i < list.size(); i++) { int temp = list.get(i); if (temp == pre) { count++; } else { count = 1 ; } if (count > maxCount) { result.clear(); result.add(temp); maxCount = count; } else if (count == maxCount) { result.add(temp); } pre = temp; } return result.stream().mapToInt(Integer::intValue).toArray(); } public void search (TreeNode root) { if (root.left != null ) { search(root.left); } list.add(root.val); if (root.right != null ) { search(root.right); } } }
530. 二叉搜索树的最小绝对差 中序遍历，获得递增序列，再比较得出最小的差值即可
98. 验证二叉搜索树 中序遍历得到递增链表
235. 二叉搜索树的最近公共祖先 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { if (root.val < p.val && root.val < q.val) { return lowestCommonAncestor(root.right, p, q); } if (root.val > p.val && root.val > q.val) { return lowestCommonAncestor(root.left, p, q); } return root; } }
701. 二叉搜索树中的插入操作 前序遍历，把所有插入的节点全放到叶子位置即可
538. 把二叉搜索树转换为累加树 右中左的顺序遍历即可
108. 将有序数组转换为二叉搜索树 为什么形如以下的写法不会建立一个完整的树：在递归调用中，你虽然创建了新的 TreeNode 并将它赋值给 root，但这个 root 只在当前递归调用的栈帧中有效。一旦递归返回，这个 root 的改变并不会反映到原始调用者或上一层的递归调用中。因此，你需要通过其他方式（如返回新创建的节点 ）来确保树的构建是连续的。
1 2 3 4 5 6 7 8 9 public void add (int [] nums, TreeNode root, int start, int end) { if (end < start) { return ; } int mid = (end - start) / 2 + start; root = new TreeNode (nums[mid]); add(nums, root.left, start, mid - 1 ); add(nums, root.right, mid + 1 , end); }
正确写法：
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 add(nums, 0 , nums.length - 1 ); } public TreeNode add (int [] nums, int start, int end) { if (end < start) { return null ; } int mid = (end - start) / 2 + start; TreeNode root = new TreeNode (nums[mid]); root.left = add(nums, start, mid - 1 ); root.right = add(nums, mid + 1 , end); return root; } }
106. 从中序与后序遍历序列构造二叉树 找到inorder的[inStart,inEnd]这些元素当中哪一个元素位于postOrder的最后，这个元素就是root
为了降低时间复杂度，把postOrder转为map
105. 从前序与中序遍历序列构造二叉树 inorder[inStart,inEnd]的元素当中位于preOrder里面最前面的就是root
为了减少查找的时间度，把preOrder转成map
700. 二叉搜索树中的搜索 递归查找即可
654. 最大二叉树 按照题目意思即可，注意考察nums的区间的开闭
655. 输出二叉树 按照题目叙述即可
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 class Solution { public TreeNode deleteNode (TreeNode root, int key) { return delete(root, key); } public TreeNode delete (TreeNode root, int key) { if (root == null ) { return null ; } if (root.val == key) { if (root.left == null && root.right == null ) { root = null ; } else if (root.left == null && root.right != null ) { root = root.right; } else if (root.left != null && root.right == null ) { root = root.left; } else { TreeNode min = root.right; while (min.left != null ) { min = min.left; } min.left = root.left; root = root.right; } } if (root.val < key) { root.right = delete(root.right, key); } if (root.val > key) { root.left = delete(root.left, key); } return root; } }
669. 修剪二叉搜索树 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 TreeNode trimBST (TreeNode root, int low, int high) { if (root == null ) { return null ; } root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); if (root.val > high || root.val < low) { if (root.right != null ) { TreeNode cur = root.right; while (cur.left != null ) { cur = cur.left; } cur.left = root.left; root = root.right; return root; } else { return root.left; } } return root; } }
114. 二叉树展开为链表 后序遍历，把右子树放到左子树的最右孩子上，再把左子树放到右子树上
129. 求根节点到叶节点数字之和 前序遍历即可
103. 二叉树的锯齿形层序遍历 层序遍历之后再翻转即可
543. 二叉树的直径 递归求取root的深度，其直径即左子树深度+右子树深度
230. 二叉搜索树中第 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 class Solution { public int kthSmallest (TreeNode root, int k) { return search(root, k); } public int search (TreeNode root, int k) { int leftNodes = countNodes(root.left); if (k == 1 + leftNodes) { return root.val; } else if (k < 1 + leftNodes) { return search(root.left, k); } else { return search(root.right, k - leftNodes - 1 ); } } public int countNodes (TreeNode root) { if (root == null ) { return 0 ; } int leftNodes = countNodes(root.left); int rightNodes = countNodes(root.right); return leftNodes + rightNodes + 1 ; } }
437. 路径总和 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 class Solution { int result = 0 ; public int pathSum (TreeNode root, int targetSum) { search(root, targetSum, false ); return result; } public void search (TreeNode root, long targetSum, boolean is) { if (root == null ) { return ; } if (targetSum == root.val) { result++; } if (is == false ) { search(root.left, targetSum - root.val, true ); search(root.left, targetSum, false ); search(root.right, targetSum - root.val, true ); search(root.right, targetSum, false ); } else { search(root.left, targetSum - root.val, true ); search(root.right, targetSum - root.val, true ); } } }
95. 不同的二叉搜索树 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<TreeNode> generateTrees (int n) { return generate(1 , n); } public List<TreeNode> generate (int start, int end) { List<TreeNode> result = new ArrayList <>(); if (start > end) { result.add(null ); return result; } for (int i = start; i <= end; i++) { List<TreeNode> leftTrees = generate(start, i - 1 ); List<TreeNode> rightTrees = generate(i + 1 , end); for (TreeNode leftNode : leftTrees) { for (TreeNode rightNode : rightTrees) { TreeNode root = new TreeNode (i); root.left = leftNode; root.right = rightNode; result.add(root); } } } return result; } }
872. 叶子相似的树 中序遍历即可
注意使用 != 操作符来比较两个 Integer 对象时，实际上是在比较它们是否引用了同一个对象Integer 对象
对于小数值（通常是-128 到127 之间的整数）会被缓存，这样相同数值的 Integer 对象实际上是相同的对象实例
但对于较大的数值，例如200，每个 Integer 对象都会是独立创建的，即使它们的值相同
这里list的元素，即list2.get(i)是Integer，更加可靠的方式是通过对象的比较方法，即equals，如下：
1 if (!list1.get(i).equals(list2.get(i)))
