高频算法题 · Dayup

刷题方式

1.初次
+ 5-10分钟审题：有想法直接做，没有就去看题解
+ 记忆默写优质解法、了解时间复杂度、空间复杂度

2. 再遇
+ 完整做题
+ 多解法比较、优化

3. 次日回顾
+ 原题的不同解法答题
+ 类似题练习 * 2

4. 一周后回顾
+ 做题、专项训练*3

5. 面试前一周
+ 查漏补缺
+ 回顾及热身

LeetcodeTop汇总各大互联网公司容易考察的高频leetcode题：https://github.com/afatcoder/LeetcodeTop
用动画的形式呈现解LeetCode题目的思路：https://github.com/MisterBooo/LeetCodeAnimation

知识点：

1.排序算法：快速、归并、计数算法
2.搜索算法：回溯、递归、剪枝
3.动态规划：背包问题、最长子序列、计数问题
4.图论：最短路径、最小生成树、网络流建模
5.基础技巧：分治、倍增、二分法、贪心算法

数据结构：
数组、链表
栈、队列
树、图
哈希表
大小根堆，可并堆
字符串：字典树、后缀树

知识点	难度	题目	题号
二叉树	简单	二叉树的中序遍历	94
二叉树	简单	二叉树的前序遍历	144
二叉树	简单	对称二叉树	101
二叉树	简单	二叉树的直径	543
二叉树	简单	翻转二叉树	226
二叉树	中等	二叉树的层序遍历	102
二叉树	中等	二叉树的锯齿形层次遍历	103
二叉树	中等	二叉树的最近公共祖先	236
二叉树	中等	验证二叉搜索树	98
二叉树	中等	路径总和②	113
二叉树	困难	二叉树中的最大路径和	124
链表	简单	反转链表	206
链表	简单	环形链表	141
链表	简单	相交链表	160
链表	中等	反转链表②	92
链表	中等	环形链表②	142
链表	中等	重排链表	143
链表	中等	删除链表的倒数第N个节点	19
链表	中等	排序链表	148
链表	中等	两数相加	2
链表	困难	K个一组翻转链表	25
栈&单调栈&队列	简单	有效的括号	20
栈&单调栈&队列	简单	最小栈	155
栈&单调栈&队列	困难	接雨水	42
栈&单调栈&队列	困难	滑动窗口最大值	239
栈&单调栈&队列	困难	最长有效括号	32
哈希表	简单	多数元素	169
二分查找	简单	x的平方根	69
二分查找	中等	搜索旋转排序数组	33
二分查找	中等	搜索二维矩阵②	240
动态规划DP	简单	买卖股票的最佳时机	121
动态规划DP	简单	爬楼梯	70
动态规划DP	中等	最长上升子序列	300
动态规划DP	中等	最小路径和	64
动态规划DP	中等	最长重复子数组	718
动态规划DP	中等	最大正方形	221
动态规划DP	中等	零钱兑换	322
回溯/DFS	中等	岛屿数量	200
回溯/DFS	中等	全排列	46
回溯/DFS	中等	组合总和	39
堆（优先队列）	中等	数组中的第K个最大元素	215
堆（优先队列）	困难	合并K个排序链表	23
排序&归并	中等	手撕快速排序	补充题4
字符串处理	简单	字符串相加	415
字符串处理	简单	比较版本号	165
字符串处理	中等	翻转字符串里的单词	151
字符串处理	中等	字符串相乘	43
字符串/滑动窗口	中等	重复字符的最长子串	3
字符串/动态规划	中等	最长回文子串	5
数组&双指针	简单	合并两个有序数组	88
数组&双指针	中等	三数之和	15
数组&双指针	中等	螺旋矩阵	54
数组&双指针	中等	合并区间	56
数组&双指针	中等	下一个排列	31
数组&双指针	中等	旋转图像	48
数组&双指针	困难	缺失的第一个正数	41

知识点	难度	题目	链接
二叉树	简单	二叉树的最大深度	https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
二叉树	简单	平衡二叉树	https://leetcode-cn.com/problems/balanced-binary-tree/
二叉树	简单	路径总和	https://leetcode-cn.com/problems/path-sum/
二叉树	简单	求根节点到叶节点数字之和	https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
二叉树	中等	完全二叉树的节点个数	https://leetcode-cn.com/problems/count-complete-tree-nodes/
二叉树	中等	二叉搜索树的第k大节点	https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
二叉树	中等	二叉树的右视图	https://leetcode-cn.com/problems/binary-tree-right-side-view/
二叉树	中等	从前序与中序遍历序列构造二叉树	https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
二叉树	中等	从中序与后序遍历序列构造二叉树	https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
链表	简单	合并两个有序链表	https://leetcode-cn.com/problems/merge-two-sorted-lists/
链表	简单	删除链表的节点	https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
链表	简单	链表中倒数第k个节点	https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
链表	简单	从尾到头打印链表	https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
链表	简单	回文链表	https://leetcode-cn.com/problems/palindrome-linked-list/
链表	中等	删除排序链表中的重复元素 II	https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
栈&单调栈&队列	简单	用栈实现队列	https://leetcode-cn.com/problems/implement-queue-using-stacks/
栈&单调栈&队列	简单	设计循环队列	https://leetcode-cn.com/problems/design-circular-queue/
栈&单调栈&队列	中等	简化路径	https://leetcode-cn.com/problems/simplify-path/
栈&单调栈&队列	中等	基本计算器 II	https://leetcode-cn.com/problems/basic-calculator-ii/
栈&单调栈&队列	中等	扁平化嵌套列表迭代器	https://leetcode-cn.com/problems/flatten-nested-list-iterator/
栈&单调栈&队列	中等	移掉 K 位数字	https://leetcode-cn.com/problems/remove-k-digits/
栈&单调栈&队列	中等	去除重复字母	https://leetcode-cn.com/problems/remove-duplicate-letters/
栈&单调栈&队列	困难	直方图的水量	https://leetcode-cn.com/problems/volume-of-histogram-lcci/
栈&单调栈&队列	困难	柱状图中最大的矩形	https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
栈&单调栈&队列	困难	计算器	https://leetcode-cn.com/problems/calculator-lcci/
哈希表	简单	两数之和	https://leetcode-cn.com/problems/two-sum/
哈希表	简单	数组中重复的数字	https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
哈希表	中等	连续数组	https://leetcode-cn.com/problems/contiguous-array/
哈希表	中等	森林中的兔子	https://leetcode-cn.com/problems/rabbits-in-forest/
哈希表	中等	字母异位词分组	https://leetcode-cn.com/problems/group-anagrams/
二分查找	简单	二分查找	https://leetcode-cn.com/problems/binary-search/
二分查找	中等	寻找旋转排序数组中的最小值	https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
二分查找	中等	寻找旋转排序数组中的最小值 II	https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
二分查找	困难	分割数组的最大值	https://leetcode-cn.com/problems/split-array-largest-sum/
二分查找	困难	寻找两个正序数组的中位数	https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
动态规划DP	简单	最大子数组和	https://leetcode-cn.com/problems/maximum-subarray/
动态规划DP	中等	乘积最大子数组	https://leetcode-cn.com/problems/maximum-product-subarray/
动态规划DP	中等	打家劫舍 II	https://leetcode-cn.com/problems/house-robber-ii/
动态规划DP	中等	目标和	https://leetcode-cn.com/problems/target-sum/
动态规划DP	中等	整数拆分	https://leetcode-cn.com/problems/integer-break/
动态规划DP	中等	最长公共子序列	https://leetcode-cn.com/problems/longest-common-subsequence/
动态规划DP	困难	吃掉 N 个橘子的最少天数	https://leetcode-cn.com/problems/minimum-number-of-days-to-eat-n-oranges/
动态规划DP	困难	编辑距离	https://leetcode-cn.com/problems/edit-distance/
动态规划DP	困难	不同的子序列	https://leetcode-cn.com/problems/distinct-subsequences/
动态规划DP	困难	正则表达式匹配	https://leetcode-cn.com/problems/regular-expression-matching/
动态规划DP	困难	统计全 1 子矩形	https://leetcode-cn.com/problems/count-submatrices-with-all-ones/
回溯/DFS	中等	子集	https://leetcode-cn.com/problems/subsets/
回溯/DFS	中等	括号生成	https://leetcode-cn.com/problems/generate-parentheses/
回溯/DFS	中等	复原 IP 地址	https://leetcode-cn.com/problems/restore-ip-addresses/
回溯/DFS	中等	字符串的排列	https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
回溯/DFS	中等	被围绕的区域	https://leetcode-cn.com/problems/surrounded-regions/
回溯/DFS	困难	24 点游戏	https://leetcode-cn.com/problems/24-game/
回溯/DFS	困难	八皇后	https://leetcode-cn.com/problems/eight-queens-lcci/
堆（优先队列）	简单	最小K个数	https://leetcode-cn.com/problems/smallest-k-lcci/
堆（优先队列）	简单	最小的k个数	https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
排序&归并	中等	排序数组	https://leetcode-cn.com/problems/sort-an-array/
排序&归并	简单	合并排序的数组	https://leetcode-cn.com/problems/sorted-merge-lcci/
排序&归并	困难	数组中的逆序对	https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
字符串处理	简单	重复的子字符串	https://leetcode-cn.com/problems/repeated-substring-pattern/
字符串处理	简单	反转字符串中的单词 III	https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
字符串处理	简单	字符串压缩	https://leetcode-cn.com/problems/compress-string-lcci/
字符串处理	中等	字符串转换整数 (atoi)	https://leetcode-cn.com/problems/string-to-integer-atoi/
字符串处理	困难	最小覆盖子串	https://leetcode-cn.com/problems/minimum-window-substring/
数组&双指针	简单	汇总区间	https://leetcode-cn.com/problems/summary-ranges/
数组&双指针	中等	轮转数组	https://leetcode-cn.com/problems/rotate-array/
数组&双指针	中等	最大交换	https://leetcode-cn.com/problems/maximum-swap/
位运算	简单	只出现一次的数字	https://leetcode-cn.com/problems/single-number/
系统设计（缓存）	中等	LRU 缓存	https://leetcode-cn.com/problems/lru-cache-lcci/
系统设计（缓存）	困难	LFU 缓存	https://leetcode-cn.com/problems/lfu-cache/
随机&概率	中等	打乱数组	https://leetcode-cn.com/problems/shuffle-an-array/
随机&概率	中等	用 Rand7() 实现 Rand10()	https://leetcode-cn.com/problems/implement-rand10-using-rand7/

HduOJ练习

acm新生训练分类100题(杭电OJ网址 acm.hdu.edu.cn)
1、基本输入输出题(共8题)
1089——1096【√】
2、基础训练题(共33题)
2000——2032【√2000-2009】
3、数学题(共10题)
1008、1108、1061、2035、1425、1021、1005、1205、1071、1215
4、递推求解(共5题)
2050、2046、1297、1465、2045
5、贪心(共8题)
1009、1052、2037、1050、1045、1051、1053、1789
6、动态规划(共26题)
2084、1257、1160、1087、1159、1421、1058、1003、1025、1059、
1069、1074、1078、1114、1158、1165、1176、1203、1208、1331、
1355、1414、1428、1579、1723、2602

2025：字符串与字符
2026:字符串与字符
2027：字符串、字符与数组
数组：2018 2020 2022 2023 2027 2028 2032 2034

时间复杂度

增长趋势：输入规模 n 变大时，算法需要的操作次数随 n 怎么增长。只看最高阶项，忽略常数。

快速记忆

复杂度	通俗理解	典型算法
$O(1)$	做固定几步，跟数据量无关	随机访问数组
$O(\log n)$	每次砍一半	二分查找
$O(n)$	从头到尾扫一遍	单循环遍历
$O(n\log n)$	一层循环 × 一层二分	快排、归并、堆排
$O(n^2)$	双重循环	冒泡排序
$O(2^n)$	每多一个元素工作量翻倍	子集暴力枚举
$O(n!)$	全排列暴力枚举	全排列回溯无剪枝

补充两个容易混淆点

$O(\log n)$ 底数不写，因为只是常数倍差异，复杂度分析忽略常数。 $\log_2n$ 、 $\log_{10}n$ 都记作 $O(\log n)$ 。
$O(\sqrt{n})$ 平方根复杂度：介于 $O(\log n)$ 和 $O(n)$ 之间，比如枚举到根号n判断质数。