给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

贪心：

class Solution {public boolean canJump(int[] nums) {int n = nums.length;int farthest = 0;for (int i = 0; i < n - 1; i++) {// 不断计算能跳到的最远距离farthest = Math.max(farthest, i + nums[i]);// 可能碰到了 0，卡住跳不动了if (farthest <= i) {return false;}}return true;}
}

• 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
• 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
• 如果可以一直跳到最后，就成功了
  链接：https://leetcode.cn/problems/jump-game/solutions/24322/55-by-ikaruga/

心得：

• 转变思路，去求能到达的最远距离，如果最远距离大于最大长度，则说明可以跳到最后，否则不可以！

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

• 使用内置函数substring（）

class Solution {public int strStr(String haystack, String  ) {int len1 = haystack.length(), len2 = needle.length();for (int i = 0; i <= len1 - len2; i++) {String temp = haystack.substring(i, i + len2);if (temp.equals(needle)) {return i;}}return -1;}
}

• 使用内置函数indexOf（）

class Solution {public int strStr(String haystack, String needle) {return haystack.indexOf(needle);}
}

• 使用KMP标准思想

//经典KMP算法，好好体会过程！KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
class Solution {public int strStr(String haystack, String needle) {int n = haystack.length();int m = needle.length();if (m == 0) {return 0;}if (n == 0) {return -1;}int i = 0, j = 0;while (i < n - m + 1) {while (i < n && haystack.charAt(i) != needle.charAt(j)) {i++;}if (i == n) { //两个都是字符串，没有首字母相等！return -1;}i++;j++;while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {i++;j++;}if (j == m) {return i - j; //找到相等得字符串了，回退到相等得初始位置！}else {   //这里就是利用到了回退，i回退到初始位置得下一个位置，j回退到初始位置！！好好理解雅！i -= j - 1;j = 0;}}return -1;}
}

心得：

• 好好体会KMP，要能手撕出来！这种while书写方式真的很优雅，很舒服！

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

双指针判断降重方法：（三个数分别在不同位置去重）

class Solution {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans = new ArrayList();int len = nums.length;if(nums == null || len < 3) return ans;Arrays.sort(nums); // 排序for (int i = 0; i < len ; i++) {if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环if(i > 0 && nums[i] == nums[i-1]) continue; // 去重int L = i+1;int R = len-1;while(L < R){int sum = nums[i] + nums[L] + nums[R];if(sum == 0){ans.add(Arrays.asList(nums[i],nums[L],nums[R]));while (L<R && nums[L] == nums[L+1]) L++; // 去重while (L<R && nums[R] == nums[R-1]) R--; // 去重L++;R--;}else if (sum < 0) L++;else if (sum > 0) R--;}}        return ans;}
}

HashSet方式降重：

class Solution {public List<List<Integer>> threeSum(int[] nums) {if (nums == null || nums.length < 3) {return new ArrayList<>();}Arrays.sort(nums);Set<List<Integer>> set = new HashSet<>();for (int i = 0; i < nums.length; ++i){int left = i + 1, right = nums.length - 1; //这里用的两个指针来缩短时间复杂度while (left < right){int add_nums = nums[i] + nums[left] + nums[right];if (add_nums == 0){set.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));//这里比较巧妙，在List里添加元素时外面还要套上new ArrayList，因为asList后不能对里边内容进行修改了！（后面有一个set添加的操作）这样做是一种习惯，当然不new一个list也能正常ac，但是执行时间和内存消耗都降低了一点，反正这种方式自己后面养成习惯吧！left ++;right --;}else if (add_nums < 0){left ++;}else{right --;}}}List<List<Integer>> lists = new ArrayList<>(set); //ArrayList只有在实例化（new）时才用，正常表示列表时用的抽象（List）表示！return lists;}
}

心得：

• 去重的方法和位置很巧妙，这种方法要好好掌握！

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

class Solution {public boolean isPalindrome(String s) {s = s.toLowerCase();StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (Character.isLetterOrDigit(c)) {sb.append(c);}}int left = 0, right = sb.length() - 1;while (left < right ) {if (sb.charAt(left) == sb.charAt(right)) {left++;right--;}else {return false;}}return true;}
}

心得：

• 记住字符串几个方法：String s; char c;
s.toLowerCase()、Character.toLowerCase(c)、Character.isLetterOrDigit()、Character.isLetter()、Character.isDigit();

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

class Solution {public boolean isSubsequence(String s, String t) {int l = 0, r = 0;while (l <= s.length() - 1 && r <= t.length() - 1) {if (s.charAt(l) != t.charAt(r)) {r++; }else {l++;r++;}}if (l == s.length()) {return true;}else {return false;}}
}

心得：

• 针对子序列，灵活运用双指针求解！！

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

class Solution {public int[] twoSum(int[] numbers, int target) {int left = 0, right = numbers.length - 1;while (left <= right) {int sum = numbers[left] + numbers[right];if (sum == target) {return new int[]{left + 1, right + 1}; //注意看题目，下标是从1开始的！}else if (sum < target) {left++;}else if (sum > target) {right--;}}return new int[]{-1, -1};}
}

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

class Solution { //滑动窗口方法！public int minSubArrayLen(int target, int[] nums) {int len = nums.length;int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < len; ++right) {sum += nums[right];while (sum >= target) {result = Math.min(result, right - left + 1);sum = sum - nums[left];left++;}}return result == Integer.MAX_VALUE ? 0 : result;}
}

心得：

• 滑动窗口双指针的方法！

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

class Solution {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> window = new HashMap<>();int left = 0, right = 0;int res = 0;while (right < s.length()) {char c = s.charAt(right);right++;window.put(c, window.getOrDefault(c, 0) + 1);while (window.get(c) > 1) {char d = s.charAt(left);window.put(d, window.get(d) - 1);left++;}//注意这个位置是right -left，而不是right - left + 1， 因为虽然right++了，但是取的c是加之前的值！res = Math.max(res, right - left);}return res;}
}

心得：

• **熟记滑动窗口的基本框架，labuladong的方法！**同时注意边界条件！

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

class Solution {
/*** 求字符串 s 中包含字符串 t 所有字符的最小子串* @param s 源字符串* @param t 给定字符串* @return 满足条件的最小子串*/
public String minWindow(String s, String t) {// 用于记录需要的字符和窗口中的字符及其出现的次数Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();// 统计 t 中各字符出现次数for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);int left = 0, right = 0;int valid = 0; // 窗口中满足需要的字符个数// 记录最小覆盖子串的起始索引及长度int start = 0, len = Integer.MAX_VALUE;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 扩大窗口right++;// 进行窗口内数据的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.get(c).equals(need.get(c)))valid++; // 只有当 window[c] 和 need[c] 对应的出现次数一致时，才能满足条件，valid 才能 +1}// 判断左侧窗口是否要收缩while (valid == need.size()) {// 更新最小覆盖子串if (right - left < len) {start = left;len = right - left;}// d 是将移出窗口的字符char d = s.charAt(left);// 缩小窗口left++;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.get(d).equals(need.get(d)))valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时，才能 -1window.put(d, window.get(d) - 1);}}}// 返回最小覆盖子串return len == Integer.MAX_VALUE ?"" : s.substring(start, start + len);
}
}

心得：

• 最小字串问题，果断滑动窗口！

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

class Solution {public int[] twoSum(int[] nums, int target) {int[] res = new int[2];if (nums.length == 0 || nums == null) return res;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];if (map.containsKey(temp)) {res[0] = i;res[1] = map.get(temp);}map.put(nums[i], i);}return res;}
}

心得：

• 空间换时间，巧妙利用hashmap的方式存储

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

class LRUCache {LinkedHashMap<Integer, Integer> map;int capacity;public LRUCache(int capacity) {this.capacity = capacity;map = new LinkedHashMap<>();}public int get(int key) {if (map.containsKey(key)) {makeNew(key);return map.get(key);}else {return -1;}}public void put(int key, int value) {if (map.containsKey(key)) {map.put(key, value);makeNew(key);return;}if (map.size() >= capacity) {int oldKey = map.keySet().iterator().next(); //链表头最久未使用keymap.remove(oldKey);}map.put(key, value);}public void makeNew(int key) {int value = map.get(key);map.remove(key);map.put(key, value);}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

百度一面手撕
①LinkedHashMap的妙用
②oldestKey = map.keySet().iterator().next();// 链表头部就是最久未使用的 key

心得：

• LinkedHashMap的妙用就是用于建立LRU这种数据结构，应为其内部是双向链表，保证了插入的顺序，所以可以保证利用类似makeNew的函数使用更新！
• map.keySet().iterator().next(); 的妙用！

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

class Solution {public boolean isValid(String s) {int n = s.length();if(n % 2 == 1){return  false;}Map<Character, Character> map = new HashMap<Character, Character>() {{// 将 })] 作为keyput('}', '{');put(']', '[');put(')', '(');}};// 新建一个栈Stack<Character> stack = new Stack<>();for (int i = 0; i < n; i++) {char c = s.charAt(i);// 如果c是 })], 则判断， 否则说明是({[ , 直接入栈if(map.containsKey(c)){// stack.peek() 获取栈顶元素if(stack.isEmpty() || stack.peek() != map.get(c)){return false;}// 将栈顶移除(先进后出，栈顶是最接近 c 的左括号)stack.pop();}else{// 说明c是({[ , 直接入栈stack.push(c);}}return stack.isEmpty();}
}

心得：

• 碰到匹配相关的操作，想到栈这个数据结构！！
• 遇到“( { ["入栈，否则利用哈希表的存储映射来判断”）} ]“是否存在以及是否匹配！

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能 以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。 

示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

class Solution {public String simplifyPath(String path) {String[] names = path.split("/");StringBuilder res = new StringBuilder();Deque<String> que = new LinkedList<>();for (String name: names) {if ("..".equals(name)) {if (!que.isEmpty()) {que.pollLast();}}else if (!".".equals(name) && name.length() > 0) {que.offerLast(name);}}if (que.isEmpty()) {res.append("/");}else {while (!que.isEmpty()) {res.append("/");res.append(que.pollFirst());}}return res.toString();}
}

心得：

• 针对这种匹配的问题，多去考虑用栈stack来解决问题！！

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

class MinStack {Stack<Integer> stack;Stack<Integer> minStack;public MinStack() {stack = new Stack<Integer>();minStack = new Stack<Integer>();}public void push(int val) {stack.push(val);if (minStack.isEmpty() || minStack.peek() > val) {minStack.push(val);}else {minStack.push(minStack.peek());}}//或者也可以用下边的方式，都一样，但是下边感觉好一点，思路清晰！多用Math.min()这种内置函数简化程序！public void push(int val) {stack.push(val);if (minStack.isEmpty()) {minStack.push(val);}else {minStack.push(Math.min(val, minStack.peek()));}}public void pop() {stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

心得：

• 用两个栈来实现最小栈，最小栈的顶部一直维护当前栈的最小值！
• 多用Math.min()这种内置函数简化程序！

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<Integer>();for (String token : tokens) {if ("+-*/".contains(token)) {int a = stack.pop();int b = stack.pop();switch (token) {case "+":stack.push(a + b);break;case "-":stack.push(b - a);break;case "*":stack.push(a * b);break;case "/":stack.push(b / a);}}else {stack.push(Integer.parseInt(token)); //String转int的方法为：Integer.parseInt()，注意函数的拼法！}}return stack.pop();}
}

心得：

• 这个题目比较常见，比较经典的方法就是碰见数字入栈，碰见 加减乘除 运算，并将结果再入栈！
• switch-case语句的使用。

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head, slow = head;//这里一定要写两个情况，以为万一fast指向最后一个数，他走两步的话会出现空指针异常！while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (fast == slow) {return true;}}return false;}
}

心得：

• 判断双指针，经典双指针方法！

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode p1 = l1, p2 = l2;ListNode dummy = new ListNode(-1);ListNode p = dummy;int carry = 0;while (p1 != null || p2 != null || carry != 0) {int val = carry;if (p1 != null) {val += p1.val;p1 = p1.next;}if (p2 != null) {val += p2.val;p2 = p2.next;}carry = val / 10;int num = val % 10;p.next = new ListNode(num);p = p.next;}return dummy.next;}
}

心得：

• 注意dummy指针的用法
• 对于这种加法用这种写法很优雅！注意学习！

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode p1 = list1, p2 = list2;ListNode dummy = new ListNode(-1);ListNode p = dummy;while (p1 != null && p2 != null) {if (p1.val > p2.val) {p.next = p2;p2 = p2.next;}else {p.next = p1;p1 = p1.next;}p = p.next;}if (p1 != null) {p.next = p1;}if (p2 != null) {p.next = p2;}return dummy.next;}
}

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {Map<Node, Node> map = new HashMap<>();for (Node p = head; p != null; p = p.next) { //利用HashMap先构建映射if (!map.containsKey(p)) {map.put(p, new Node(p.val));}}for (Node p = head; p != null; p = p.next) { //利用HashMap再构建链接if (p.next != null) {   //默认的构造函数，p的next和random都是null，所以对于null的next和random不用理会即可！map.get(p).next = map.get(p.next);}if (p.random != null) {map.get(p).random = map.get(p.random);}}return map.get(head); }
}

心得：

• 巧妙地利用HashMap，先利用其构造映射关系，再利用其构造连接关系！

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

递归方式：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode last = reverseList(head.next);head.next.next = head;head.next = null;return last;}
}

双指针方式：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode left = null, right = head;while (right != null) {ListNode temp = right.next;right.next = left;left = right;right = temp;}return left;}
}

心得：

• 递归的方式真奇妙，好好体会，好好用！后序遍历方式！

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head == null) return null;ListNode a = head, b = head;for (int i = 0; i < k; i++) {if (b == null) return head;b = b.next;}ListNode newHead = reverse(head, a, b);a.next = reverseKGroup(b, k);return newHead;}//注意是左闭右开public ListNode reverse(ListNode head, ListNode a, ListNode b) {ListNode pre, cur, next;pre = null;cur = a;next = a;while (cur != b) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}}

翻转部分也可以用递归的方式：

    //ListNode successor = null;public ListNode reverse(ListNode head, ListNode left, ListNode right) {if (head.next == right) {//successor = right;return head;}ListNode last = reverse(head.next, left, right);head.next.next = head;// head.next = successor;head.next = right;return last;}

心得：

• 纯递归的方式进行！难度不大，思路要理解好，注意区间边界！

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}
public class Solution {int res = 0;int count = 0;public int kthSmallest(TreeNode root, int k) {if (root == null) return 0;traverse(root, k);return res;}public void traverse(TreeNode root, int k) {if (root == null) return;traverse(root.left, k);count++;if (count == k) {res = root.val;return;}traverse(root.right, k);}
}

心得：

• 遇到二叉搜索树，最先想到其中序遍历的结果就是从小到大排序，对这个要敏感！！

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int left = maxDepth(root.left);int right = maxDepth(root.right);return Math.max(left, right) + 1;}}

心得：

• 经典递归问题，分解问题，同时注意边界条件！

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}else if (p != null && q == null) {return false;}else if (p == null && q != null) {return false;}else if (p.val != q.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}

心得：

• 纯递归问题，想一想每一步的操作是怎样的，把每一步的思维打通，那么所有的步骤就是一样的！

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

递归方式：

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) return null;TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left);invertTree(root.right);    return root;}
}

或者：

class Solution {public TreeNode invertTree(TreeNode root) {traverse(root);return root;}public void traverse(TreeNode root) {if (root == null) return;TreeNode temp = root.left;root.left = root.right;root.right = temp;traverse(root.left);traverse(root.right);}
}

BFS方式：

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) return null;Queue<TreeNode> que = new LinkedList<>();que.offer(root);while (!que.isEmpty()) {int len = que.size();while (len > 0) {TreeNode node = que.poll();TreeNode temp = node.left;node.left = node.right;node.right = temp;if (node.left != null) que.offer(node.left);if (node.right != null) que.offer(node.right);len--;}}return root;}
}

心得：

• 深度递归DFS和层序遍历BFS！

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

class Solution {public boolean isSymmetric(TreeNode root) {boolean check = getResult(root.left, root.right);return check;}public boolean getResult(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;}if (left != null && right == null) {return false;}if (left == null && right != null) {return false;}if (left.val != right.val) {return false;}boolean check = getResult(left.left, right.right) && getResult(left.right, right.left);return check;}
}

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> map;public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开}public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {// 参数里的范围都是前闭后开if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开，说明没有元素，返回空树return null;}int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定前序数列的个数root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,inorder, inBegin, rootIndex);root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,inorder, rootIndex + 1, inEnd);return root;}
}

心得：

• 递归千万不要忘了base case，即边界条件！除此之外左闭右开这个也要原则要保持不变！
• 每一次递归的本质是找到左边的下一个根节点和右边的下一个根节点，重复往返即可！
• 确定一个唯一二叉树，可以用中序+后序，或者是前序+中序，重点是先去确定根节点，再根据根节点找左右子树！

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> map;public TreeNode buildTree(int[] inorder, int[] postorder) {int inEnd = inorder.length, postEnd = postorder.length;map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return traverse(inorder, 0, inEnd, postorder, 0, postEnd); //左闭右开}public TreeNode traverse(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {if (inBegin >= inEnd || postBegin >= postEnd) {return null;}TreeNode root = new TreeNode(postorder[postEnd - 1]);int index = map.get(postorder[postEnd - 1]);int lenOfRight = inEnd - index;root.left = traverse(inorder, inBegin, index, postorder, postBegin, postEnd - lenOfRight);root.right = traverse(inorder, index + 1, inEnd, postorder, postEnd - lenOfRight, postEnd - 1);return root;}
}

或者：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> map;public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; ++i) {map.put(inorder[i], i);}return constructTree(inorder, 0, inorder.length, postorder, 0, postorder.length);}public TreeNode constructTree(int[] inorder, int inbegin, int inend, int[] postorder, int pobegin, int poend) {if (inbegin >= inend || pobegin >= poend) {return null;}int rootIndex = map.get(postorder[poend - 1]);TreeNode root = new TreeNode(inorder[rootIndex]);int lenOfLeft = rootIndex - inbegin;root.left = constructTree(inorder, inbegin, rootIndex, postorder, pobegin, pobegin + lenOfLeft);root.right = constructTree(inorder, rootIndex + 1, inend, postorder, pobegin + lenOfLeft, poend - 1);return root;}
}

这两个区别就在于看你相求lenOfLeft还是lenOfRight的长度！

心得：

• 利用中序+后序的方式解决，注意好边界条件即可！

给定一个二叉树：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {if (root == null) return null; //这个不能丢！要有这个判断！！Queue<Node> que = new LinkedList<>();que.offer(root);while (!que.isEmpty()) {int len = que.size();Node pre = null; //这个用的很妙！放的位置也很好！while (len > 0) {Node node = que.poll();if (pre != null) {pre.next = node;}pre = node;if (node.left != null) que.offer(node.left);if (node.right != null) que.offer(node.right);len--;}}return root;}
}

心得：

• BFS去遍历！采用标准BFS遍历模板！
  注意：让每一层的遍历之间增加指针连接，所以在层遍历地方增加代码，然后增添一个指针pre，用来指向每层的每个位置，初始的时候每个节点next已经置为null，所以不需要再给每个节点置为null，只关心让他们之间产生连接就可以！
• 这个pre指针用的很妙，放的位置很好！

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public void flatten(TreeNode root) {if (root == null) return;//整体思路有点像归并排序的递归！都是利用的“后序遍历”解决的！！好好体会！flatten(root.left);flatten(root.right);//这个时候左右子树都已经flatten了，只去考虑最后一步就行！（后序遍历就只去考虑最后一步，前序遍历只去考虑第一步！）TreeNode left = root.left;TreeNode right = root.right;root.left = null;root.right = left;TreeNode p = root;while (p.right != null) {p = p.right;}p.right = right;}
}

心得：

• 整体思路有点像归并排序的递归！都是利用的“后序遍历”解决的！！好好体会！ flatten(root.left);
  flatten(root.right);
  //这个时候左右子树都已经flatten了，只去考虑最后一步就行！（后序遍历就只去考虑最后一步，前序遍历只去考虑第一步！）
• 后续遍历方式解决问题！！碰到递归这种问题很好解决！

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new LinkedList<>();LinkedList<Integer> track = new LinkedList<>();backtrack(n, res, track, k, 1);return res;}public void backtrack(int n, List<List<Integer>> res, LinkedList<Integer> track, int k, int start) {if (track.size() == k) {res.add(new LinkedList<>(track));return;}for (int i = start; i <= n; i++) {track.add(i);backtrack(n, res, track, k, i + 1);track.removeLast();}}
}

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new LinkedList<>();LinkedList<Integer> track = new LinkedList<>();backtrack(nums, res, track, 0);return res;}public void backtrack(int[] nums, List<List<Integer>> res, LinkedList<Integer> track, int start) {res.add(new LinkedList<>(track));for (int i = start; i < nums.length; i++) {track.add(nums[i]);backtrack(nums, res, track, i + 1);track.removeLast();}}
}

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();List<Integer> track = new ArrayList<>();boolean[] used = new boolean[nums.length];backtrack(res, track, used, nums);return res;}public void backtrack(List<List<Integer>> res, List<Integer> track, boolean[] used, int[]nums) {if (track.size() == nums.length) {res.add(new ArrayList<>(track));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) {continue;}track.add(nums[i]);used[i] = true;backtrack(res, track, used, nums);track.remove(track.size() - 1);used[i] = false;}}
}

心得：

• 排列问题就要用到used数组解决！

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> res = new LinkedList<>();LinkedList<Integer> track = new LinkedList<>();int trackSum = 0;  //利用trackSum记录得到的元素之和Arrays.sort(candidates);//子集问题看到元素有重复，想到要对其排序进行剪纸backtrack(candidates, target, res, track, 0, trackSum);return res;}public void backtrack(int[] candidates, int target, List<List<Integer>> res, LinkedList<Integer> track, int start, int trackSum) {// base case，等于目标和，加入元素直接结束 if (trackSum == target) {res.add(new LinkedList<>(track));return;}// base case，超过目标和，直接结束if (trackSum > target) {return;}for (int i = start; i < candidates.length; i++) {if (i > start && candidates[i - 1] == candidates[i]) {//对于横向遍历重复元素的筛选问题continue; }track.add(candidates[i]);trackSum += candidates[i];backtrack(candidates, target, res, track, i + 1, trackSum);track.removeLast();trackSum -= candidates[i];}}
}

心得：

• 注意引入trackSum这个变量来计算总和！