1、多线程顺序打印ABC
- 方式一：synchronized+wait+notify+state【悲观锁】
- 方式二：lock+state【悲观锁】
- 方式三：无锁的 volatile 方法
- 方式四：原子操作类：AtomicInteger
- 在Java里，我们熟悉的原子操作类AtomicInteger就是基于CAS实现的，可以用来保证Integer操作的原子性。
全方法参考：link https://zhuanlan.zhihu.com/p/570342860
2、五种单例
- 饿汉式-静态代码块
- 懒汉式-双重检查
- 懒汉式-静态内部类
- 饿汉式-枚举
3、反转链表s
牛客 78 反转链表：
4、快速排序
5、快乐数
6、丑数s
力扣 263 丑数：
思路：
- 循环分解 2、3、5，直到因子只剩 1 或 其他。
7、设计 LRU 缓存结构s
力扣 146/牛客 93 设计 LRU 缓存结构：
- https://leetcode.cn/problems/lru-cache/description/
- https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84?tpId=196
思路：
- 哈希表+链表
- 借助链表的有序性使得链表元素维持插入顺序，
- 同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。
- 提取 makeRecently 公共方法
8、设计 LFU 缓存结构 未通过
9、二叉树先中后遍历打印s
牛客 45 二叉树先中后打印：
思路：
- 前中后位置追加节点值
10、二叉搜索树与双向链表s
剑指 36 二叉搜索树与双向链表：
思路：
- 二叉搜索树中序遍历升序，中序位置做头节点和前驱指针的初始化以及前驱节点 right 和当前节点 left 的更新
11、数字在升序数组中出现的次数s
牛客 74 数字在升序数组中出现的次数：
思路：
- 目标值在升序数组最左侧的索引和最右侧的索引可以锁定次数，转换成左边界二分搜索和右边界二分搜索的问题。
12、最小的K个数 TODO
牛客119 最小的K个数：
思路：
- 使用大顶堆，堆顶保存最小数集合的最大值；构建堆完成后依次入堆，判断当前元素小于堆顶则置换，之后重新调整堆，使堆内数据均小于堆顶。
- 适合海量数据的处理
- 创建一个用于保存最小k个数的容器
- 第一步是放入k个元素，
- 第二步是比较容器中最大的数与当前数组遍历的那个数的大小
- 如果容器中最大的数比当前遍历的数大，就移除该数，并放入当前遍历的那个数
- 最大堆或红黑树都能实现这样的容器
13、二叉树的层序遍历s
牛客 15 二叉树的层序遍历：
思路：
- 构造一个队列存放当前层的节点
14、寻找第K大 TODO
牛客 88 寻找第K大：
思路：
- 快排进阶版 O(nlogn)
【其他解法】
15、两数之和s
力扣 1 两数之和/牛客 61 两数之和
16、合并两个排序的链表s
牛客 33 合并两个排序链表：
思路：
- 虚拟头节点、结果链表指针、表一指针、表二指针
17、用两个栈实现队列s
力扣 232/牛客 76 用两个栈实现队列
18、跳台阶s
牛客 68 跳台阶：
思路：
- 动态规划。
- f(0)=1, f(1)=1,f(2)=2
- 状态转移方程为：dp[i] = dp[i-1]+dp[i-2]
19、链表中的节点每k个一组翻转s
牛客 65 链表中的节点每k个一组翻转：
思路：
- 递归：
- 终止条件：走到最后一个分组；返回值：头节点；本级任务翻转链表
- 翻转后，翻转链表的头节点充当了翻转后的尾节点，直接连接下一段要翻转的链表，即子问题。
20、连续子数组最大和s
力扣 53/牛客 19
思路：
- 动态规划。
- 定义dp[i]为 以 nums[i] 为结尾的「最大子数组和」 。
- 状态转移方程：
- dp[i] = Math.max(nums[i], nums[i] + dp[i – 1]);
21、最长无重复子数组s
牛客 41 最长无重复子数组：
思路：
- 滑动窗口
22、判断链表中是否有环s
牛客 4 判断链表中是否有环：
思路：
- 快慢指针，快指针走两步，慢指针走一步，相遇则有环
23、合并两个有序的数组s
力扣 88/牛客22 合并两个有序数组：
- https://leetcode.cn/problems/merge-sorted-array/description/
- https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665?tpId=117
24、两个链表的第一个公共节点s
牛客 66 两个链表的第一个公共节点：
思路：
- 双指针，链表连起来移动
25、链表中环的入口节点s
牛客3 链表中环的入口节点：
思路：
- 找到环中相遇节点，然后前指针从头出发，再次相遇即入口节点
26、括号序列s
牛客52 有效括号序列：
思路：
- 栈。在有括号入栈是做合法性判断
27、删除链表的倒数第n个节点s
牛客 53 删除链表的倒数第n个节点：
思路：
- 快慢指针，快指针先移动 n 步，慢指针开始移动，快指针到头时慢指针移动了 len-n 步，即倒数的节点。
28、大数加法
29、大数乘法
30、按之字形顺序打印二叉树s
牛客 14 按之字形顺序打印二叉树
思路：
- 借助队列的层序遍历+偶数层翻转结果
31、最长公共子串 #
牛客 127 最长公共子串
思路：
- dp[i][j] 的含义是：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]。
32、最长公共子序列（二）#
33、两个链表生成相加链表s
牛客 40 链表相加：
思路：
- 链表反转+进位控制
34、二叉树的最近公共祖先s
力扣 236 二叉树的最近公共祖先：
思路：
- 后序位置处理
- 函数定义：返回以 root 为根，p和q的最近公共祖先
- 情况1：p、q都在root树里，返回就是p、q的最近公共祖先
- 情况2：p、q都不在root树里，返回null
- 情况3：p、q有一个在root树里，返回p或者q
35、螺旋矩阵s
力扣 54 /牛客 38 螺旋矩阵
- https://leetcode.cn/problems/spiral-matrix/description/
- https://www.nowcoder.com/practice/7edf70f2d29c4b599693dc3aaeea1d31?tpId=117
思路：
- 四个方向边界控制移动范围
36、斐波那契s
牛客 65 斐波那契：
思路：
- 带备忘录的递归
37、最长回文子串s
牛客17 最长回文子串
思路：
- 拆解成单字符为中心的回文串和双字符为中心的回文串求最长
- 回文串判定从中间向两边延伸，字符不等的时候取到最长回文串
38、三数之和s
力扣 15 /牛客 54 三数之和：
- https://leetcode.cn/problems/3sum/description/
- https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=188
思路：
- nSum问题，可以通过 twoSum 方法延伸。
39、重建二叉树s
牛客 12 重建二叉树：
思路：
- 画出前序和中序根、左子树、右子树的关系图
- 根节点在前序第一位，拿到根节点的值，可以锁定中序中根节点的索引
- 根据中序根节点索引，能锁定左子树的大小
- 进而锁定左右子树构建范围
40、最长连续递增序列 #
力扣 674 最长连续递增序列：
41、最长递增子序列 #
力扣 300 最长递增子序列：
思路：
- dp 数组的定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
- 那么 dp 数组中最大的那个值就是最长的递增子序列长度。
42、最长递增子序列的个数 #
力扣 673 最长递增子序列的个数：
- 代码参考
43、最长递增子序列(字典顺序) #
- 代码参考
44、数组中的最长连续子序列 $
牛客 95 数组中的最长连续子序列：
难度：
- 较难
参考代码
45、求平方根s
力扣 69/牛客 32 求平方根：
- https://leetcode.cn/problems/sqrtx/description/
- https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c?tpId=117
思路：
- 时间复杂度O(logx)，用二分法
46、在旋转过的有序数组中寻找目标值s
牛客 48 在旋转过的有序数组中寻找目标值：
思路：
- 找到k，分别在两侧左二分查找
47、包含min函数的栈s
牛客 90 包含min函数的栈：
思路：
- 构建最小值的栈
48、买卖股票的最好时机
牛客 7 买卖股票的最好时机：
思路：
- 股票类通用转移方程。
- i 为 哪一天，k 为交易数的上限，0或1代表是否持有股票
框架化简：
49、股票(无限次交易)
框架化简：
50、股票（一天两次）
牛客 135：买卖股票的最好时机（三）
51、合并K个升序链表s
力扣 23/牛客 51 合并K个升序链表：
- https://leetcode.cn/problems/merge-k-sorted-lists/description/
- https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=117
思路：
- 优先级队列
52、字符串的排列（全排列）s
牛客 121 字符串的排列：
思路：
- 排序 & 回溯框架 & 剪枝
53、数字字符串转化成IP地址(全排列)s
力扣 93 复原IP地址：
牛客 20 数字字符串转化成IP地址：
- https://leetcode.cn/problems/restore-ip-addresses/description/
- https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e?tpId=117
54、集合的所有子集(全排列)s
力扣 78/牛客 27 集合中所有子集：
- https://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9?tpId=117
- https://leetcode.cn/problems/subsets/description/
55、没有重复项数字(全排列)s
力扣 46 全排列
牛客 43 没有重复项数字的全排列
- https://leetcode.cn/problems/permutations/description/
- https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1?tpId=117
56、有重复项数字(全排列)s
力扣 47 全排列2：
牛客 42 有重复项数字的全排列
- https://leetcode.cn/problems/permutations-ii/description/
- https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=117
思路：
- 回溯+剪枝
57、输出二叉树的右视图s
力扣 199/牛客 136 输出二叉树的右视图：
- https://leetcode.cn/problems/binary-tree-right-side-view/
- https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=117
思路：
- 前序中序构建树+层序遍历的变形
58、岛屿数量s
牛客 109 岛屿数量：
思路：
- dfs，遇到岛屿加入结果，并用dfs把岛屿淹掉，即遇到1，就把周围的1变为0，
59、二叉树的最大深度s
力扣 104/牛客13 二叉树的最大深度：
- https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
- https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=117
回溯算法思路：
60、判断回文s
牛客 141 判断是否为回文字符串：
思路：
- 前后指针相向而行
61、单链表的排序s
牛客70 单链表的排序：
思路：
- 快慢指针找中点，拆成两个链表，合并
62、平衡二叉树s
力扣110/牛客 62 判断是否为平衡二叉树：
- https://leetcode.cn/problems/balanced-binary-tree/description/
- https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=117
思路：
- dfs，判断左子树为平衡树，判断右子树为平衡树，左子树深度和右子树深度差距小于等于1为平衡树
O(n)解法：
O(n2)解法：
63、数组中出现次数超过一半的数字s
牛客 73 数组中出现次数超过一半的数字：
思路：
- 排序取中位数
- 哈希表存数值到个数的映射
- 投票法。假设某个数是众数，则票数+1，遇到非嫌疑众数的数，票数-1，当票数为0则说明当前数不是众数
64、矩阵的最小路径和s
力扣 64/牛客 59 矩阵最小路径和：
- https://leetcode.cn/problems/minimum-path-sum/description/
- https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=117
思路：
- 动态规划：dp[i][j] = dp[i][j] + Min(matrix[i][j-1],matrix[i-1][j])
- dfs，要求空间复杂度为O(n)，则说明不能再新建 dp 矩阵，直接使用matrix
65、表达式求值s
牛客 137 表达式求值：
思路：
- 栈+递归
66、逆波兰表达式求值s
牛客 216 逆波兰表达式求值：
思路：
- 栈。遇到数字入栈，遇见符号弹出两个数字做运算，然后将结果入栈
67、最小的K个数s
牛客 119 最小的K个数：
思路：
- topk 问题求最小，建大顶堆
自建大顶堆的代码：
使用JDK优先级队列的代码：
68、字符串出现次数的TopK问题s
牛客97 字符串出现次数的TopK问题：
思路:
- 最大堆实现的优先级队列
69、进制转换s
牛客 112 进制转换：
思路：
- 除N取余，然后倒序排列，高位补零。
70、判断一个链表是否为回文结构s
牛客 96 判断一个链表是否为回文结构
思路：
- 找到中间节点，反转后半部分，两部分从头等值比对
71、二叉树中和为某一值的路径(是否存在)s
牛客 9 二叉树中和为某一值的路径(一)：
思路：
- 前序遍历，每走过一个节点更新 sum 值，sum 为0 且是叶子节点更新路径和标识，并退出
72、二叉树中和为某一值的路径(所有路径)s
牛客 8 二叉树中和为某一值的路径(二)：：
思路：
- 回溯的思路，在(一)的遍历基础上增加路径更新、结果追加、撤销选择的逻辑。
73、二叉树中和为某一值的路径(所有子路径)s
牛客 162 二叉树中和为某一值的路径(三)：
思路：
- 在(二)的基础上，再次进行树的遍历统计路径数
- 注意：路径不再要求叶子节点结束
74、链表内指定区间反转s
力扣 92 反转链表2：
牛客21 链表内指定区间反转：
75、不同路径的数目s
力扣 63/牛客 34 不同路径的数目：
- https://leetcode.cn/problems/unique-paths/description/
- https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=117
思路：
- dp 迭代 or 递归
76、合并区间s
力扣 56/牛客 37 合并区间：
- https://leetcode.cn/problems/merge-intervals/description/
- https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=117
思路：
- 对于几个相交区间合并后的结果区间 x，x.start 一定是这些相交区间中 start 最小的，x.end 一定是这些相交区间中 end 最大的
- 对 start 排序
77、排序数组中找到上中位数s
牛客 36 在两个长度相等的排序数组中找到上中位数：
思路：
- 双指针
78、搜索二叉树和完全二叉树s
牛客 60 判断一棵二叉树是否为搜索二叉树和完全二叉树
思路：
- 搜索二叉树，明确定义是 root为左子树的最大值，右子树的最小值，遍历参数引入双节点
- 完全二叉树，每一层不存在空节点。层序遍历，null值也入队。遍历遇到空节点，检查队列是否还有非空节点，存在说明二叉树不完全。
79、删除有序链表中重复的元素-II s
牛客 24 删除有序链表中重复的元素-II
思路：
- 双指针，隔一齐头并进，出现重复则只前进快指针，直到不相等的时候执行删除操作
80、将字符串转化为整数(已下线)
牛客 100 把字符串转换成整数(atoi)：
思路：
- 单指针，从头出发去掉前导空格，检查是否走到终点
- 处理正负号情况，设置符号标，检查是否走到终点
- 遇到非法字符，截断
- 处理越界
- 累加结果值
- res = res * 10 + sign * (c – ‘0’);
81、反转数字s
牛客 57 反转数字
思路：
- 注意不能引入 long 类型
- 通过求余倒着计算结果，每加入一个字符要判断下加入这个字符会不会超限
82、单链表对折s
题目：
- 给一个单链表，将链表两两首尾相连
- 原链表：1->2->3->4…..n->null
- 对折后链表：1->n->2->n-1->3->n-2…….->null
- 要求空间复杂度：O(1)
- 示例：1 2 3 4 5 6 编程 1 6 2 5 3 4
思路：
- 找到链表中点，反转后链表，遍历前链表插入后链表节点
83、矩阵元素查找s
牛客 86 矩阵元素查找：
思路：
- 行维度倒序剪枝
- 行维度从后往前，当前元素值比目标值大，意味着这一列都比它大，没必要循环
84、缺失的第一个正整数s
牛客 30 缺失的第一个正整数
思路：
- 排序，遍历时非正正数跳过，正整数和递增的目标数比对，一致目标数递增，不一致返回当前目标数
85、丢失的数字s
力扣 268 丢失的数字：
思路：
- 排序+遍历
- 进阶：排序+二分
86、链表的奇偶重排s
力扣 328/牛客 133 链表的奇偶重排：
- https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=196
- https://leetcode.cn/problems/odd-even-linked-list/description/
思路：
- 合并链表的思路，分别把奇数节点和偶数节点合并到新链表中
87、二叉树中的最大路径和s
力扣 124/牛客 6 二叉树中的最大路径和：
- https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a?tpId=196
- https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/
思路：
- 左右子树贡献求最大，注意负数情况的处理，函数返回节点贡献值选左子树或者由子树
88、对称二叉树s
力扣 101/牛客 16 对称的二叉树：
- https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=196
- https://leetcode.cn/problems/symmetric-tree/description/
思路：
- 二叉树后续遍历：
- 节点比较
- 层序遍历借助栈
89、括号生成s
牛客 26 括号生成
思路：
- 递归树，左子树处理左括号，右子树处理有括号
- left 为当前左括号个数，right 为当前右括号个数，n 对括号。递归树终止条件是 left==n&&left==right
90、顺时针旋转矩阵s
牛客 18 顺时针旋转矩阵
思路：
- 对角线置换+水平前后置换
91、重排链表（同 82、单链表对折）s
牛客 2 重排链表：
思路：
- 找到链表中点，反转后链表，遍历前链表插入后链表节点
92、删除有序链表中重复的元素-I s
力扣 83/牛客 25 删除有序链表中重复的元素-I
- https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
- https://www.nowcoder.com/practice/c087914fae584da886a0091e877f2c79?tpId=196
思路：
- 快慢指针。都初始化 head，遍历快指针，当快慢指针值不等时，慢指针直接连接不等值的快指针，此时慢指针再推进，达到跳过重复数字的效果。
- 注意循环结束要对慢指针跳过后面重复元素的连接： 2-3-3 的case。
93、滑动窗口的最大值 TODO
力扣 239/牛客 82 滑动窗口的最大值
- https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=196
- https://leetcode.cn/problems/sliding-window-maximum/description/
待修改代码
94、加起来和为目标值的组合s
牛客 238 加起来和为目标值的组合：
思路：
- 回溯法
95、最长的括号子串 TODO
牛客49 最长的括号
思路：
- 栈
96、最长公共前缀 TODO
力扣14/牛客 55 最长公共前缀：
- https://www.nowcoder.com/practice/28eb3175488f4434a4a6207f6f484f47?tpId=196
- https://leetcode.cn/problems/longest-common-prefix/description/
思路：
- 求最短字符串–>求长度为length的是否为公共子串–>二分查找
97、左边界二分查找s
牛客 105 二分查找-II：
思路：
- 等值时收缩右边界
98、丢棋子问题 TODO
牛客 87 丢棋子问题
99、序列化二叉树s
力扣 297/牛客 123 序列化二叉树
- https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/
- https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=196&tqId=37116
思路：
- 在相应位置做逻辑处理
【前序】
【层序】
100、字符串变形s
牛客 89 字符串变形：
思路：
- 空格拆子字符串，针对子字符串做大小写转换
101、环形链表的约瑟夫问题s
牛客 132 环形链表的约瑟夫问题：
思路：
- 构建一个环形链表，指针符合要求则删除节点
102、最大数s
牛客111 最大数：
思路：
- 整型转字符串，排序并拼接
103、验证 IP 地址s
牛客 113 验证 IP 地址：
思路：
- 根据 IP 特点做针对性检查
104、兑换零钱s
力扣 322/牛客 126 兑换零钱（一）：
- https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=196
- https://leetcode.cn/problems/coin-change/description/
思路：
- 动态规划 子问题
105、二维数组中的查找(同 83 矩阵元素查找)s
牛客 29 二维数组的查找：
思路：
- 倒序剪枝
106、数组中的逆序对s
牛客 118 数组中的逆序对：
思路：
- 归并排序过程中计算数量
107、最大正方形
牛客 108 最大正方形：
思路：
- 定义二维数组dp[m][n]，其中dp[i][j]表示的是在矩阵中以坐标(i,j)为右下角的最大正方形边长。
- dp[i][j] = Math.min(dp[i – 1][j], Math.min(dp[i – 1][j – 1], dp[i][j – 1])) + 1;
108、旋转数组
牛客 110 旋转数组
思路：
- 整体反转，再反转前半部分，再反转后半部分
109、数据流中的中位数
牛客 131 数据流中的中位数
思路：
- 插入排序
110、连续子数组最大乘积
牛客 83 连续子数组的最大乘积：
111、把数字翻译成字符串
牛客 116 把数字翻译成字符串：
思路：
- 用辅助数组dp表示前i个数的译码方法有多少种
- 注意 10 和 20 的特殊处理
112、二叉树的镜像
牛客 72 二叉树的镜像：
思路：
- 后续遍历，调换左右节点
113、相同的子树
牛客 98 判断t1树中是否有与t2树完全相同的子树：
思路：
- 先序遍历序列化，然后包含匹配
114、调整数组顺序使奇数位于偶数前面(一)
牛客 77 调整数组顺序使奇数位于偶数前面(一)：
思路：
- 遍历统计奇数个数，锁定偶数指针，双指针一路向前
115、合并二叉树
牛客 117 合并二叉树：
思路：
- 前序遍历，new 新的根节点承接和，并设置左右子树
116、矩阵最长递增路径 TODO
牛客 138 矩阵最长递增路径：
思路：
- dfs，同 58 岛屿数量
117、扑克牌顺子
牛客 63 扑克牌顺子：
思路：
- max-min<5，且无重复
