hot100回归复习（算法总结1-38）
计划
时隔1个月（期末考试、黑马点评、八股、找实习）后的我终于回来啦🤭。重新开刷算法，虽然每天应该只有下班的时间才能刷题，但是还是要加快进度。
希望每天简单3道 or 中等2道 or 困难1题
回顾（1-38）
常用函数
常用集合函数
Collections.sort(collection)
列表转换数组：list.toArray(new int[list.size()][])
列表添加：list.add();
常用数组函数
排序：Array.sort（arr）;会改变原来的数组的值
元素为两个的排序：Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[] a ,int[] b){
return a[0] != b[0] ? a[0]-b[0] : a[1]-b[1];
}
});
数组复制：System.arraycopy(newArr, 0, nums, 0, n);
常见字符串函数
字符串与整数转换：char - 'a' 默认转换为整型；(char) char+ int 强制转换为char
字符与字符串转换：char_arr[] ca = str.toCharArray(); String str = new String(ca);
字符串位置i的字符：char c = str.charAt(i)
字符串长度：int len = str.length;
StringBuffer用法：
(1) 构建：StringBuffer sb =new StringBuffer();
(2)添加字符:sb.append(char c)
(3)转换字符串：String s = sb.toString();
哈希表
核心原理
利用HashMap与HashSet实现O(1)复杂度的查找。
常规操作就是能够去掉一层for循环
常用函数
构造实例HashMap：HashMap<K,V> map = new HashMap<>;
添加：map.put(key,value);
获取：map.get(key);
获取or新建 Object obj = getOrDefault（key，new Object）；
判断存在：map.containsKey(key);
获取全部值：map.values() 返回一个集合类型Collection；常用组合list.addAll（map.values()）
遍历：
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("Key: " + key + ", Value: " + value);
}
构造实例HashSet：HashSet<K> set= new HashSet<>;
添加：set.add()。HashSet.add() 方法在添加元素时，如果元素已存在，返回 false，否则返回 true
判断是否存在：set.contains(key)
遍历：for(int num : set){}
去重：如果是对引用类型可以实现内容去重，一般来说是先进行排序，排序后放入set种，相同则去重。例如内容去重：List、Set、Integer以及String
其他用途
HashMap可用来判断子串是否相等，存储每个子串的数目
经典题目
1. 两数之和 - 力扣（LeetCode）
15. 三数之和 - 力扣（LeetCode）
49. 字母异位词分组 - 力扣（LeetCode）
128. 最长连续序列 - 力扣（LeetCode）
560. 和为 K 的子数组 - 力扣（LeetCode）
41. 缺失的第一个正数 - 力扣（LeetCode）
160. 相交链表 - 力扣（LeetCode）存储链表的节点
141. 环形链表 - 力扣（LeetCode）
142. 环形链表 II - 力扣（LeetCode）
动态规划
核心思想
常用方法
dp[i]=f (dp[i-1]+num[i] , num[i])
经典题目
53. 最大子数组和 - 力扣（LeetCode）
队列
核心原理
优先队列（最大堆、最小堆）、单调队列（双端队列）
常用函数
1.优先队列（最大堆）：
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
添加元素：pq.offer(new int[]{nums[i], i})
pq.peek()[0]
pq.poll()
2.双端队列
Deque<Integer> deque = new LinkedList<Integer>()
deque.offerLast(i)
deque.pollLast()
deque.peekLast()
deque.peekFirst()
经典题目
239. 滑动窗口最大值 - 力扣（LeetCode）
双指针
用法
（1）优化空间复杂度（空间换时间）
核心原理
目前没有发现，但是有两种常用方式，一个是快慢指针，另一个是左右指针.
目前最大的感受是它是用来降低空间复杂度问题，优化动态规划。
常见方法
1.快慢指针：一个快指针，一个慢指针。两种移动速度不同（根据某个规则），但是方向相同。
边界条件：一般是快指针到达边界之前（也就是fast<n）。
2.左右指针：一个左指针，一个右指针。两种移动速度不同（根据某个规则），但是方向相反。
边界条件：一般是左指针与右指针相遇之前。
快慢指针常见题目
283. 移动零 - 力扣（LeetCode）：无侵入移动；
141. 环形链表 - 力扣（LeetCode）：找环
142. 环形链表 II - 力扣（LeetCode）：找到一开始进入环的节点
234. 回文链表 - 力扣（LeetCode）：找链表中间值
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
左右指针常见题目
11. 盛最多水的容器 - 力扣（LeetCode）：求面积；
42. 接雨水 - 力扣（LeetCode）：求面积，某个点左右两侧最大值的最小的
15. 三数之和 - 力扣（LeetCode）：有序数组求目标值，如果左右不符合，移动获得目标值。
滑动窗口
核心思想
收缩、扩展
滑动窗口：双指针、数组、队列
经典题目：字符串
字符串题目
不定长窗口：双指针维护不定长窗口；
3. 无重复字符的最长子串 - 力扣（LeetCode）
76. 最小覆盖子串 - 力扣（LeetCode）
定长窗口：数组定长，一般需要先单独构造
Arrays.equals(scount,pcount)
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
子串
常见方法
前缀和、滑动窗口
560. 和为 K 的子数组 - 力扣（LeetCode）
76. 最小覆盖子串 - 力扣（LeetCode）
数组
常见题目
56. 合并区间 - 力扣（LeetCode）
区间重叠的数组合并，思路：
（1）数组合并的方式：区间的右端点大于下一个左端点则可以合并。为了确保不漏，需要是连续的，所以要根据左端点进行排序。
（2）返回结果的方式。一个合并区可能包括多个区间，所以需要一个while无限循环，实时更新右侧端点的最大值。前提是确认好起点即可（for即可）
189. 轮转数组 - 力扣（LeetCode）
思路：
（1）新数组copy
（2）数组反转
41. 缺失的第一个正数 - 力扣（LeetCode）
思路：（1）最简单的就是hashSet，将数组存在哈希表中，从1到遍历即可
（2）如果不能用哈希表，就用打标签的方式，每个值在对应下标处修改为负数。还是遍历数组找到不为负数的位置。
矩阵
常见题目
54. 螺旋矩阵 - 力扣（LeetCode）
思路：模拟
核心：visited[][]访问数组 与 direction[][]方向数组
小技巧：directionIndex = (directionIndex + 1) % 4;循环4
48. 旋转图像 - 力扣（LeetCode）
思路：公式推导
核心：旋转90后，四次一个循环，推导公式，将一开始的matrix[i][j]存储一个临时数组，然会推导公式即可。
240. 搜索二维矩阵 II - 力扣（LeetCode）
思路：Z字搜索 / 二分查找
链表
思路
（1）复制法，获取所有节点的值，放到数组中，利用数组完成相关操作。
常见函数
哑节点：ListNode prehead = new ListNode(num);常用于比如合并链表、删除节点等，ps：一般num=-1
ListNode init = new ListNode(0,head);这个也是呀节点，但是直接指定下一个节点就算head，优化了之前的只是单单的一个节点。
常见题目
160. 相交链表 - 力扣（LeetCode）
思路：类似双指针
具体方法：a+m+b = b+m+a；a+b+= b+a；一个指针走到终点后指向下一个指针的头节点
206. 反转链表 - 力扣（LeetCode）
思路：
定义三个变量：pre、cur、nex
234. 回文链表 - 力扣（LeetCode）
思路：
（1）空间法：将值存在到一个数组中，双指针判断
（2）快慢指针找中点，反转链表再对比
21. 合并两个有序链表 - 力扣（LeetCode）
思路：
用一个创建新节点，比较两个链表的每个节点的大小，然后一个一个连接。
2. 两数相加 - 力扣（LeetCode）
思路：模拟法，每次sum=（jin+n1+n2）%10；jin=（jin+n1+n2）/10
循环结束的条件是两个链表都为空，如果一个提前为null，则将下一个值为val=0.
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
思路：
（1）算出来链表的长度，然后再长度的前一个节点直接跳到下一个节点
（2）双指针，一快快指针比慢指针快n+1步，当快指针指到null时，慢指针正好指向倒数第n+1个，正好向下指两个。
24. 两两交换链表中的节点 - 力扣（LeetCode）
思路：模拟法
（1）按照题干要求完成即可。3个点：cur、next1、next2，核心将这三个点交换位置即可
注意事项：
while循环条件pre.next！==null && pre.next.next！=null
25. K 个一组翻转链表 - 力扣（LeetCode）
思路：模拟法
整体流程：
（1）设计一个反转函数，请求参数（head，tail），返回参数（head，tail）
（2）pre连接head，然后pre=tail
注意事项：
while循环条件（head！=null）
138. 随机链表的复制 - 力扣（LeetCode）
思路：就是复制粘贴，新建一个链表与提高的链表完全相同。
方法1：按照逻辑遍历原链表，每次new个节点即可。
方法2：哈希表HashMap，key为原链表节点，value与新建的节点。这样好处是方便操作，要不然按照方法一，每次也都有新建一个节点。
148. 排序链表 - 力扣（LeetCode）
思路：
方法1：数组获取所有的节点值，然后用数组排序。确定空间复杂度O（N）
方法2与3：（自上而下、自下而上）归并排序，这个需要记忆一下。
23. 合并 K 个升序链表 - 力扣（LeetCode）
思路：
暴力法：遍历listnode，两两合并，时间复杂度高。
复制法：获取所有简单数组，然后排序，最后新建一个节点，给所有节点赋值。
优先队列：
方法1：将所有简单入队，然后每次都弹出最小值，放到一个新列表中。
方法2：将所有链表中最前面的节点入队，然后获得最小的加入答案链表，然后将该节点的下一个节点在入队。
二叉树
常见函数
构造栈与队列
Deque<TreeNode> stk = new LinkedList<TreeNode>();出入栈
stk.push(root);root = stk.pop();出入队列
Deque<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root); TreeNode node = queue.poll();常见题目
94. 二叉树的中序遍历 - 力扣（LeetCode）
思路：
方法1：利用栈。将该节点所有左节点入栈，然后获取该节点的值，之后成为该的右节点，重新开始。
方法2：递归。编写一个order函数，先坐节点、添加根节点、order右节点。
边界条件是root==nul return;
104. 二叉树的最大深度 - 力扣（LeetCode）
思路：
广度优先遍历：利用队列，边界条件是队列是否为null，然后每次循环再次将该层所有节点的数量记录，每出去一个节点，size减少1，直到为0，说明该层遍历完成，然后深度加1.
226. 翻转二叉树 - 力扣（LeetCode）
思路：
广度优先遍历：将节点的左右子节点入队，然后交换左右节点即可（也可以先交换节点再入队）。边界条件：队列不为空。
方法
空间（存储法）
73. 矩阵置零 - 力扣（LeetCode）：数组本身也可以优化
238. 除自身以外数组的乘积 - 力扣（LeetCode）：输入数组本身也可以优化
42. 接雨水 - 力扣（LeetCode）：二叉树可以优化
206. 反转链表 - 力扣（LeetCode）：将节点存在存储一个list中反向遍历即可
搜索算法
哈希表
二分查找
240. 搜索二维矩阵 II - 力扣（LeetCode）