leetcode算法总结 —— HOT 100分类整理_leetcode hot100

链表

easy

• 21. 合并两个有序链表
• 160. 相交链表（双指针，走完自己链表走另一个链表）
• 141. 环形链表（快慢指针，扣圈）
• 206. 反转链表（方法一：迭代，方法二：递归）
• 234. 回文链表（使用快慢指针，快指针走两步，慢指针走一步，慢指针并反转前半部分链表）
       middle
• 2. 两数相加（注意进位和判断链表为空）
• 148. 排序链表(归并模版，注意中间节点处理）
• 19. 删除链表的倒数第 N 个结点
• 406. 根据身高重建队列（先自定义排序，再使用list插入）
       hard

二叉树

• 617. 合并二叉树（前序遍历判断并构造，返回构造后的树）
• 104. 二叉树的最大深度（dfs向上返回深度，bfs记录深度）
• 543. 二叉树的直径（求最大深度，同上）
• 226. 翻转二叉树(前序遍历：每个节点都交换左右子树)
• 101. 对称二叉树（dfs和BFS）
• 96. 不同的二叉搜索树(根节点两边相乘，然后累加）
• 114. 二叉树展开为链表(dfs或者直接遍历）
• 94. 二叉树的中序遍历（栈模拟递归，标记）
• 236. 二叉树的最近公共祖先（后序遍历判断左右子树）
• 538. 把二叉搜索树转换为累加树（中序遍历倒序）
• 98. 验证二叉搜索树（中序遍历，记录前一个节点）
• 22. 括号生成（dfs，记录左右括号数）
• 105. 从前序与中序遍历序列构造二叉树

map

• 1. 两数之和（map）
• 49. 字母异位词分组（拍个序，然后放map）
• 253. 会议室 II（记录）

数组

• 461. 汉明距离（位运算a^b, n=n&(n-1)）
• 136. 只出现一次的数字（位运算）
• 169. 多数元素（摩尔投票法）
• 448. 找到所有数组中消失的数字（原数组操作对index标记）
• 155. 最小栈（辅助栈）
• 20. 有效的括号（辅助栈）

调度

621. 任务调度器

下一个排列

• 31. 下一个排列

DFS

• 200. 岛屿数量
• 79. 单词搜索

LRU缓存

-146. LRU 缓存机制（map+list）

二分查找

• 34. 在排序数组中查找元素的第一个和最后一个位置
• 33. 搜索旋转排序数组

双指针

• 283. 移动零
• 11. 盛最多水的容器
• 75. 颜色分类
• 581. 最短无序连续子数组

数组

• 238. 除自身以外数组的乘积
• 240. 搜索二维矩阵 II（空间缩减）
• 287. 寻找重复数（原数组标记）
• 15. 三数之和（两个排序数组之和思想）

贪心

• 55. 跳跃游戏

回溯

• 17. 电话号码的字母组合
• 46. 全排列（回溯）
• 39. 组合总和（回溯）
• 78. 子集（回溯）

位运算

• 338. 比特位计数（位运算）

单调栈和栈

• 739. 每日温度（单调栈）
• 394. 字符串解码（使用双栈）

排序

• 215. 数组中的第K个最大元素
• 347. 前 K 个高频元（最小堆）

前缀和

• 560. 和为K的子数组(map存储<前缀和，出现次数>)

字典树

• 208. 实现 Trie (前缀树)

dp （13）

完全背包

• 70. 爬楼梯（简单dp）
• 322. 零钱兑换
• 279. 完全平方数

最大子序

• 53. 最大子序和（DP）
• 152. 乘积最大子数组
• 300. 最长递增子序列（注意这里子序列可以非连续，上面两题为连续）

看当前位置的上方和左方

• 221. 最大正方形
• 62. 不同路径（动态转移方程：当前位置等于上面和左边的和）
• 64. 最小路径和（同62思想）

01背包

• 416. 分割等和子集
• 494. 目标和

买卖股票

• 121. 买卖股票的最佳时机（dp,然后优化一下空间）

打家劫舍

• 198. 打家劫舍（dp[i] = max(dp[i-1], dp[i-2]+nums[i]);）
• 337. 打家劫舍 III（树形，后序遍历）
• 3. 无重复字符的最长子串（滑动窗口）
• 4. 寻找两个正序数组的中位数(方法一：两路归并找中位数，方法二：待研究）
• 297. 二叉树的序列化与反序列化
• 239. 滑动窗口最大值（单调队列，插入删除和取最大值都是O(1)）