算法

image.png

1. 数组

1.1 删除

题	解题思路
26. 删除排序数组中的重复项	使用 O(1)的空间复杂度。时间复杂度低,使用双指针法,头指针 i 指向将被替换的元素，尾指针 j 指向用来替换的元素，j替换 i 的下一位,直到 j 遍历到底。
80. 删除排序数组中的重复项 II	删除排序数组中的重复项，使每个元素的频率不超过2，使用 O(1)的空间复杂度。使用双指针法，i 指针指向待替换的前一位元素,j 指针用来替换的元素，当相同元素使用了两次时，第三次跳出。
27. 移除元素	依次使用后面的元素替换重复元素，替换后的元素可能依旧需要被替换。

1.2 修改

题	解题思路
31. 下一个排列	从后往前遍历，如果发现非递增的，则在已遍历数组中寻找刚好大于该值的元素(二分查找)，替换两值，将数组 reverse。
189. 旋转数组
88. 合并两个有序数组	从后往前遍历，从后往前插入，避免移动操作。

1.3 查找

1.3.1 二分查找

1.3.1.2 操作步骤

若中间值小于目标值，左端点等于中间值的右一位，若中间值小于目标值，右端点等于中间值的左一位。若左右端点相等，且该值不等于目标值，则数组中不包括目标值。

1.3.1.3 思想

每次舍弃掉不合要求的元素，直至找到目标值相等的元素（多个返回一个）。

题	解题思路
33. 搜索旋转排序数组	（1）如果是全局有序数组的话（第一个数小于最后一个），使用二分查找；（2）在两段的情况下，根据 nums[left]、nums[right]、nums[mid]、target 值来查找。
4. 寻找两个有序数组的中位数	双指针法：使用 count 记录访问节点个数，count < (len1+len2)/2 时，使用两个指针分别指向排序数组，将元素值较小的指针右移。
	使用双指针初始值指向两个数组的中间元素，并且选择较长的数组根据指针指向值的大小，进行二分移动，直到两指针指向的元素相邻。
34. 在排序数组中查找元素的第一个和最后一个位置

1.4.2 双指针法

又名对撞指针或夹逼问题。
思想是对于当前数组，选取左右指针以及其之间的所有元素中的任意两个元素，计算目标值，根据结果舍弃左（或右）指针元素和当前数组中其他元素的组合。

题	解题思路
11. 盛最多水的容器	右节点左移，最右节点和数组中其他节点的组合不满足条件，舍弃。
3. 无重复字符的最长子串	i、j 记录收尾位置,map<value,index>
42. 接雨水
15. 三数之和	首先将数组排序排序，倒序遍历数组 nums 中的元素 nums[i]，并跳过重复值，使用双指针nums[left],nums[right] 取索引 i 后的元素组合。两数之和大于目标值时，右边值和其他任何数的组合无效；小于目标值，左边值和其他任何数的组合无效；等于目标值时，根据第二大元素判重。
	在以上的基础上，去重，并使用 Map 记录元素值出现的频率。当索引值相等时，根据频率判断是否合法。
	使用 map 记录数组中每一位元素值的位置，使用双重 for 循环计算第三个值，若存在。
16. 最接近的三数之和	排序，i = [0,n-1] , j = [i+1,n-1],findNearest(j+1,n-13)
209. 长度最小的子数组	滑动窗口原理，在上次循环的计算结果基础上进行计算。

1.4 动态数组

2. 链表

2.1 遍历

题	解题思路
2. 两数相加	使用 flag 记录上一位是否进一，注意不等长问题。
445. 两数相加 II	在以上 2 例的基础上结合栈使用。
109. 有序链表转换二叉搜索树	递归找中点，O(nlogn),使用数组存储 ListNode 地址,O(n)

2.2 修改

选择 cur 节点。
保存下一个 cur 节点。
对 cur 节点进行操作。
注意边界。

题	解题思路
206. 反转链表	针对当前节点进行操作，注意边界。
92. 反转链表 II
24. 两两交换链表中的节点	如果头节点为空或只有一个节点，则返回头节点。否则返回值第二个节点，并将 cur.next.next = cur , cur.next = q.next , q 为下一个 q 。
25. K 个一组翻转链表	使用栈实现。
61. 旋转链表	将尾节点指向头节点
143. 重排链表	从前往后，插入从后往前，使用栈实现。
328. 奇偶链表	依次将奇偶链表重连
234. 回文链表	将后半段反转

2.3 删除

题	解题思路
203. 移除链表元素
82. 删除排序链表中的重复元素 II	删除全部重复元素，若 prev 指针后的元素重复，则将 prev 指针指向下一个值的元素。
83. 删除排序链表中的重复元素	如果下一个元素等于当前元素，则删除下一个元素。

2.5 特殊链表

题	解题思路
141. 环形链表	判断链表是否有环。快指针每次移动两个节点，慢指针每次移动一个节点。如果有环，当慢指针进入环时，快指针必然在慢指针从后追赶慢指针，并且每次超越一个节点。
142. 环形链表 II	使用 HashSet 记录。
160. 相交链表	相交必同尾。
817. 链表组件	链表中连续一段在数组中，将数组转为集合

栈和队列

题	解题思路
1047. 删除字符串中的所有相邻重复项(待完成)	使用栈实现。
225. 用队列实现栈
232. 用栈实现队列

3. 树

3.1 二叉树遍历

3.1.1 前中后次遍历

题	解题思路
105. 从前序与中序遍历序列构造二叉树	根据前序确定根节点，在中序中找到根节点，前面是左子树，后面是右子树，再对左右子树进行递归。
106. 从中序与后序遍历序列构造二叉树	根据后序确定根节点（链表最后一位），在中序中找到根节点，前面是左子树，后面是右子树，再对左右子树进行递归。

3.1.2 层次遍历

题	解题思路
200. 岛屿数量	普通层次遍历采用单个队列即可，首先将跟节点入队列，出队列时依次将左右孩子入队列。
102. 二叉树的层次遍历
107. 二叉树的层次遍历
429. N叉树的层序遍历	使用 Queue<Integer> 实现。Root 入队列，添加 null 。遍历（将节点写入List）队列中的所有节点，并将子节点入队列，碰到 null新建List ，向队列中添加 null。然后依次将元素出队列，碰到标志元素则表示上层元素遍历完成，本层元素入队完成，此时添加标注元素。
103. 二叉树的锯齿形层次遍历	交替，使用栈替换临时队列来存储，使用 flag 记录从左或从右。
117. 填充每个节点的下一个右侧节点指针 II	参考层序遍历,将刚出队列的 next 指针指向队列的首位元素。

3.1.3 深度遍历

题	解题思路
104. 二叉树的最大深度	二叉树的最大深度，取左右子数的最大深度的最大值加1，若为 null，深度取 0。
111. 二叉树的最小深度	二叉树的最小深度，取左右子树深度较小值加 1，若为 null，深度取 0。
112. 路径总和
113. 路径总和 II
129. 求根到叶子节点数字之和
257. 二叉树的所有路径	如果遍历到叶子节点，则将路径插入链表，否则分别对左右节点进行递归。

3.1.4 其他问题

题	解题思路
124. 二叉树中的最大路径和	路径被定义为一条从树中任意节点出发，达到任意节点的序列。
101. 对称二叉树	根节点对称，则根节点的左子树和另一个根节点的右子树对称。
687. 最长同值路径	路径被定义为一条从树中任意节点出发，达到任意节点的序列。两个节点之间的路径长度由它们之间的边数表示。longestFromRoot 方法计算从根节点出的最长线长度，root.val==left.val,res=1+longestFromRoot(root.left),若 root.val==right.val,res=1+longestFromRoot(root.right),取 res 和 max的最大值。

3.2 二叉搜索树

题	解题思路
98. 验证二叉搜索树
783. 二叉搜索树结点最小距离
938. 二叉搜索树的范围和
99. 恢复二叉搜索树	二叉搜索树两个位置互换,中序遍历俩次，第一次记录小于前面值的节点 count 值，第二次相第一小于前面值节点的前一个节点和第二个小于前面值互换。若没有第二个点，则将第一个小于前面点和前面点互换。
173. 二叉搜索树迭代器	中序遍历。先找右子树最左，再向上遍历，再找父节点。先将最左边一列节点入栈，然后，使用指针记录最后一个节点，使用 map 记录下每层最右节点，刚好大于。
315. 计算右侧小于当前元素的个数

3.3 平衡二叉树

3.3.1 AVL

即是二叉树搜索树，又是平衡二叉树。实现方法：当前节点的平衡因子的绝对值大于 1 时，存在 LL、RR、LR、RL 四种情况：分别采取右旋、左旋、先对左子树左旋再对节点右旋、先对右子树右旋再对节点左旋对方式，是当前节点是平衡二叉树。

3.3.2 红黑树

题	解题思路
110. 平衡二叉树	判断二叉树是否为平衡二叉树，自身的深度等于左右子树较深的一个加1，求出左右子树深度同时作差，若大于1，则将 flag 设置为 false。若 flag 为 fasle,则函数终止。
108. 将有序数组转换为二叉搜索树	找到中间节点（偶数偏左），再将中心节点左边的数组转为二叉搜索树，为根节点的左子树；再将中心节点右边的数组转为二叉搜索树，为根节点的右子树。

3.4 其他

297. 二叉树的序列化与反序列化

4. 哈希表

题	解题思路
706. 设计哈希映射	插入，将新增节点插入链表头部。删除，同链表删除。
242. 有效的字母异位词
49. 字母异位词分组	使用 map 统计每个字符串的词频，再进行比较。
1. 两数之和(return index)	使用 map 记录数组中每一位元素的值和位置，遍历数组，若 map 中存在 target-num[i]，且 value 不为 i,时间复杂度为 O(n)。
726. 原子的数量(待实现)	插1：如果大写字母后不是数字或者小写字母，则插入1。乘倍数：找到右括号索引对称的左括号索引，然后其间的数乘以右括号右一位的数字。使用栈实现。进行 wordcount

5. 图

题	解题思路
547. 朋友圈	连通图：图的深度优先或者广度优先遍历。
210. 课程表 II	有向图。
802. 找到最终的安全状态
329. 矩阵中的最长递增路径
310. 最小高度树

6. 字符串匹配

6.1 单模式匹配

6.1.1 朴素匹配

6.1.2 BM & KMP

其本质是根据模式串预处理和当前匹配情况找到 next 指针，BM 算法从模式串尾开始匹配，有坏后缀原则和好前缀原则，寻找最近一个匹配子串，KMP 算法从前往后匹配，本质上是构建每个子串的最大前后对等。

6.2 多模式匹配

6.2.1 字典树

关键词	解题思路
208. 实现 Trie (前缀树)
720. 词典中最长的单词,同样长时按字典序排序	（1）构造线段树（2）遍历字典树，记录当前最长长度，如果有的长度大于当前的话，则进行替换。
211. 添加与搜索单词 - 数据结构设计
212. 单词搜索 II
127. 单词接龙

6.2.2 AC 自动机。

AC 自动机是 KMP 算法和 Tire 树的结合， next 指针构造，将首节点的 next 指针指向根节点，如果 a 的 next 为b，且，那么 a 的子节点等于 b 的子节点，则 a 的子节点的 next 指针为 b 的子节点。

7. 算法

7.1 贪心

题	解题思路
455. 分发饼干

7.2 递归

题	解题思路
101. 对称二叉树
236. 二叉树的最近公共祖先
529. 扫雷游戏
50. Pow(x, n)

7.3 回溯

题	解题思路
46. 全排列
784. 字母大小写全排列	类似打印括号组合。
78. 子集
77. 组合
51. N皇后
22. 括号生成	右括号数 <=左括号数 <= 括号对数
147. 对链表进行插入排序
18. 四数之和

7.4 分治

题	解题思路
240. 搜索二维矩阵 II
169. 求众数

7.5 动态规划

题	解题思路
53. 最大子序和	dp[i]= arr[i]+max(dp[i],0)
62. 不同路径
63. 不同路径 II	dp[i][j]=dp[i-1][j]+dp[j-1][i]
70. 爬楼梯	dp[i] = dp[i-1]+dp[i-2]
746. 使用最小花费爬楼梯	dp[i]=min(dp[i-2]+arr[i-2],dp[i-1]+arr[i-1])，表示从 i-2 过来或者从 i-1 过来。dp[i] 表示 i 之前的选择完毕。dp[0] = 0,dp[1]=0
零钱兑换	dp[i]=1+min(dp[i-j]),所有大数都能使用更多小数的组合时，则可以使用贪心。
714. 买卖股票的最佳时机含手续费	卖出时扣手续费 dp[i][1] = max(dp[i-1],prices[i]-fee+
123. 买卖股票的最佳时机 III
188. 买卖股票的最佳时机 IV
309. 最佳买卖股票时机含冷冻期	状态:0,持有；1，不持有不可买；2，不持有可买。选择：如下图。
198. 打家劫舍(链)	dp[i] =max(dp[i-2]+arr[i],dp[i-1])
213. 打家劫舍 II	在 198 的基础上，分两种情况分别进行动态规划：抢劫第一家和不抢劫第一家。
337. 打家劫舍 III	dp(node)=max(dp(node.left)+dp(node.right)，node.val+dp(node.left.left)+dp(node.left.right)+dp(node.right.left)+dp(node.right.right)，left.val+dp(node.right.left)+dp(node.right.right),right.val+dp(node.left.left)+dp(node.left.right))
174. 地下城游戏
背包问题

0 ---> 1 ---> 2 --->2
|                   |
0                   0

8. 排序算法