LeetCode算法题整理(200题左右)

前言

最后完整的整理了一遍备战秋招过程中刷过的Leetcode题目，这里大概200道左右，有些很简单的题目没有搬上来，可以去下面链接里的我的github找，大概总共280+左右。

说说刷完这些的感受吧，基本上大小厂的笔试题可以 2.5/4，3/5这样子，所以这200题还是不太够的，应该要400-500题，笔试才可以比较从容。

面试手撕的话，这200道题会了就完全够用了。

重点掌握章节：贪心、动归、模拟

一、树（17）

1.1、后序遍历

Leetcode226. 翻转二叉树（53）
Leetcode543. 二叉树的直径（65）
Leetcode110. 平衡二叉树（68）
Leetcode124. 二叉树中的最大路径和（110）
Leetcode236. 二叉树的最近公共祖先（164）
Leetcode337. 打家劫舍 III（11）

1.2、层次遍历

Leetcode662. 二叉树最大宽度（44）
Leetcode958. 二叉树的完全性检验（37）

1.3、中序

Leetcode230. 二叉搜索树中第K小的元素（28）
剑指 Offer 54. 二叉搜索树的第k大节点（37）
Leetcode98. 验证二叉搜索树（65）
Leetcode426. 将二叉搜索树转化为排序的双向链表（49）

1.4、前序

Leetcode104. 二叉树的最大深度（68）
Leetcode112. 路径总和（58）
Leetcode113. 路径总和 II（65）
Leetcode129. 求根节点到叶节点数字之和（69）
Leetcode257. 二叉树的所有路径（12）

二、回溯（20）

技巧：dfs函数前加一个@cache可以加速

2.1、普通回溯

Leetcode22. 括号生成（82）
Leetcode面试题 08.06. 汉诺塔问题（9）

2.2、线性回溯：组合、排列、子集、分割

Leetcode77. 组合（11）
Leetcode39. 组合总和（59）
Leetcode40. 组合总和 II（28）
Leetcode17. 电话号码的字母组合（17）

Leetcode46. 全排列（146）
Leetcode47.全排列 II（32）
剑指 Offer 38. 字符串的排列（11）

Leetcode78. 子集（62）
Leetcode90.子集 II（3）

Leetcode131. 分割回文串（9）
Leetcode93. 复原 IP 地址（77）

2.3、矩阵回溯

Leetcode200. 岛屿数量（161）
Leetcode695. 岛屿的最大面积（47）
Leetcode329. 矩阵中的最长递增路径（26）

Leetcode79. 单词搜索（35）
Leetcode130. 被围绕的区域（12）
Leetcode51. N 皇后（14）
【Leetcode37. 解数独】

三、二分查找（11）

模板：

# 找左边界
while left < right:
	  mid = left + (right - left) // 2   # 取左中位数
	  if nums[mid] < target: left = mid + 1
	  else: right = mid
# 找右边界
while left < right:
      mid = left + (right - left + 1) // 2    # 取右中位数
      if nums[mid] > target: right = mid - 1
      else: left = mid
1
2
3
4
5
6
7
8
9
10

3.1、普通二分

Leetcode704. 二分查找（108）
Leetcode34. 在排序数组中查找元素的第一个和最后一个位置（53）
Leetcode69. x 的平方根（93）
Leetcode611. 有效三角形的个数（17）
Leetcode189. 轮转数组（23）
Leetcode4. 寻找两个正序数组的中位数（96）

3.2、旋转数组二分

Leetcode33. 搜索旋转排序数组（166）
Leetcode81. 搜索旋转排序数组 II（2）
面试题 10.03. 搜索旋转数组最小idx（11）

Leetcode153. 寻找旋转排序数组中的最小值（46）
Leetcode154. 寻找旋转排序数组中的最小值 II（12）

四、栈和队列（13）

4.1、普通栈、普通队列

Leetcode155. 最小栈（67）
Leetcode232. 用栈实现队列（104）
剑指 Offer 09. 用两个栈实现队列的插入和删除（37）
Leetcode402. 移掉 K 位数字（38）

Leetcode678. 有效的括号字符串（19）
Leetcode20. 有效的括号（172）
Leetcode227. 基本计算器 II（44）
Leetcode394. 字符串解码（47）

4.2、单调栈、单调队列

Leetcode42.接雨水（120）
Leetcode84. 柱状图中最大的矩形（13）
Leetcode85. 最大矩形（14）
Leetcode739. 每日温度（33）

Leetcode239. 滑动窗口最大值（74）

五、贪心（10）

5.1、区间贪心

Leetcode55. 跳跃游戏（30）
Leetcode45. 跳跃游戏 II（22）
Leetcode56. 合并区间（99）
Leetcode435. 无重叠区间（6）
Leetcode452. 用最少数量的箭引爆气球（6）

5.2、两个维度贪心

Leetcode135. 分发糖果（28）
Leetcode406. 根据身高重建队列（3）

5.3、简单贪心

Leetcode162. 寻找峰值（52）

5.4、复杂贪心

Leetcode134. 加油站（17）
Leetcode253. 会议室 II（14）

六、动态规划（31）

6.1、经典类型动归

Leetcode121. 买卖股票的最佳时机（173）
Leetcode122. 买卖股票的最佳时机 II（44）
Leetcode123. 买卖股票的最佳时机 III（29）

Leetcode198. 打家劫舍（43）
Leetcode213. 打家劫舍 II（20）

Leetcode62. 不同路径（50）
Leetcode63. 不同路径 II（16）
Leetcode64. 最小路径和（62）
Leetcode120. 三角形最小路径和（21）
Leetcode221. 最大正方形（51）

Leetcode416. 分割等和子集（11）
Leetcode494. 目标和（13）

Leetcode322. 零钱兑换（65）
Leetcode518. 零钱兑换 II（32）

0-1背包模板：

# 0-1背包
# 物品： nums   bagweight
dp = [看题目具体情况 for _ in range(bagweight + 1)]
dp[0] = 看题目具体情况   有多少种=1   最大价值=0
for i in range(len(nums)):
    for j in range(bagweight, nums[i]-1, -1):
        # 问题1
        if j >= nums[i]:
            dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])  # 这句视情况而定  最大值+nums[i]  最少个数+1
        # 问题2  多少种组合方式
        if j >= nums[i]:   # 可加可不加
            dp[j] += dp[j-nums[i]]
1
2
3
4
5
6
7
8
9
10
11
12

完全背包模板：

# 完全背包
# 物品： nums   bagweight
dp = [看题目具体情况 for _ in range(bagweight+1)]
dp[0] = 看题目具体情况
for i in range(len(nums)):
    for j in range(nums[i], bagweight+1):
        # 问题1
        if j >= nums[i]:
            dp[j] = min(dp[j], dp[j-nums[i]]+看情况而定)   # 组合里 最少个数+1 
        # 问题2
        if j >= nums[i]:
        	dp[j] += dp[j-nums[i]]    # 多少种组合方式
1
2
3
4
5
6
7
8
9
10
11
12

6.2、单串动归

Leetcode53. 最大子数组和（211）
Leetcode152. 乘积最大子数组（45）

Leetcode674. 最长连续递增子序列长度（11）
Leetcode300. 最长递增子序列长度（123）
Leetcode673. 最长递增子序列的个数（19）

Leetcode5. 找到最长回文子串（161）
Leetcode647. 回文子串个数（10）
Leetcode516. 最长回文子序列长度（15）

Leetcode139. 单词拆分（37）

6.3、双串动归

Leetcode72. 编辑距离（93）
Leetcode97. 交错字符串（14）

Leetcode1143. 最长公共子序列（80）
Leetcode718. 最长重复子数组（57）
Leetcode115. 不同的子序列（14） 难

6.4、普通动归

Leetcode70. 爬楼梯（100）
Leetcode32. 最长有效括号（65）
Leetcode96. 不同的二叉搜索树（20）

七、链表（23）

Leetcode2. 两数相加（91）
Leetcode445. 两数相加 II（24）
Leetcode19. 删除链表的倒数第 N 个结点（100）
Leetcode21. 合并两个有序链表（200）
Leetcode23. 合并K个升序链表（140）
Leetcode24. 两两交换链表中的节点（45）
Leetcode25. K 个一组翻转链表（249）
Leetcode61. 旋转链表（30）
Leetcode83. 删除排序链表中的重复元素（50）
Leetcode82. 删除排序链表中的重复元素 II（93）
Leetcode92. 反转链表 II（134）
Leetcode138. 复制带随机指针的链表（40）
Leetcode141. 环形链表（172）
Leetcode142. 环形链表 II（139）
Leetcode143. 重排链表（112）
Leetcode146. LRU缓存机制（396）
Leetcode160. 相交链表（160）
Leetcode206. 反转链表（487）
Leetcode234. 回文链表（61）
Leetcode328. 奇偶链表（26）
Leetcode86. 分隔链表（18）
Leetcode114. 二叉树展开为链表（24）
Leetcode237. 删除链表中的节点（3）

八、排序（5）

排序模板：堆排序、快排、归并排序

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def heapify(tree, n, i):  # tree[i]为根节点的子树进行堆排序
            c1 = 2 * i + 1
            c2 = 2 * i + 2
            max_index = i  # 小顶堆这里改下
            if c1 < n and tree[c1] > tree[max_index]:  # 小顶堆这里改下
                max_index = c1
            if c2 < n and tree[c2] > tree[max_index]:
                max_index = c2
            if max_index != i:
                # tree[max_index], tree[i] = tree[i], tree[max_index]
                tree[i], tree[max_index] = tree[max_index], tree[i]
                # max_index和i作了交换，所以max_index分支需要重新整理为大顶堆
                heapify(tree, n, max_index)
        def build_heap(tree, n):   # 从parent->0节点分别进行一次堆排序 就建立了这个树的堆
            last_node = n - 1
            parent = (last_node - 1) // 2
            for i in range(parent, -1, -1):
                heapify(tree, n, i)
        def heap_sort(tree, n):
            build_heap(tree, n)
            for i in range(n-1, -1, -1):
                tree[i], tree[0] = tree[0], tree[i]  # 把最大值放到最后
                heapify(tree, i, 0)   # 从根节点开始heapify 但是个数为n-0
        heap_sort(nums, len(nums))
        return nums



# 2、归并排序
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge(left, right):
            # 合并两个有序数组
            m, n = len(left), len(right)
            merge_arr = [0 for _ in range(m + n)]
            # 从后往前遍历，进行合并
            while m and n:
                if left[m - 1] > right[n - 1]:
                    merge_arr[m + n - 1] = left[m - 1]
                    m -= 1
                else:
                    merge_arr[m + n - 1] = right[n - 1]
                    n -= 1
            if m:
                merge_arr[:m] = left[:m]
            if n:
                merge_arr[:n] = right[:n]
            return merge_arr

        def merge_sort(nums):
            if len(nums) <= 1: return nums
            mid = len(nums) // 2
            left = merge_sort(nums[:mid])
            right = merge_sort(nums[mid:])
            return merge(left, right)

        return merge_sort(nums)


# 2、快排  超时了  为什么？？？
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(nums, left, right):
            if left >= right: return
            temp = left
            i, j = left, right
            while i < j:
                while i < j and nums[j] > nums[temp]: j -= 1
                while i < j and nums[i] <= nums[temp]: i += 1
                nums[i], nums[j] = nums[j], nums[i]
            nums[temp], nums[i] = nums[i], nums[temp]
            quick_sort(nums, left, i-1)
            quick_sort(nums, i+1, right)
        quick_sort(nums, 0, len(nums)-1)
        return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

Leetcode148. 排序链表（92）
Leetcode179. 最大数（43）
Leetcode215. 数组中的第K个最大元素（327）
Leetcode347. 前 K 个高频元素（18）
Leetcode剑指 Offer 45. 把数组排成最小的数（17）

九、图（4）

Leetcode207. 课程表（36）
Leetcode210. 课程表 II（16）
Leetcode547. 省份数量（11）
Leetcode841. 钥匙和房间

十、其他经典类型（63）

10.1、Hash

Leetcode1. 两数之和（195）
Leetcode560. 和为 K 的子数组（35）
Leetcode974. 和可被 K 整除的子数组（9）
Leetcode12. 整数转罗马数字（10）

10.2、原地Hash

Leetcode41. 缺失的第一个正数（84）
Leetcode268. 丢失的数字（268）
Leetcode287. 寻找重复数（22）
Leetcode442. 数组中重复的数据（19）
剑指 Offer 03. 数组中重复的数字（13）

10.3、双指针

Leetcode11. 盛最多水的容器（27）
Leetcode15. 三数之和（232）
Leetcode16. 最接近的三数之和（21）
Leetcode18. 四数之和（14）

Leetcode125. 验证回文串（26）
Leetcode680. 验证回文字符串 Ⅱ（10）

Leetcode26. 删除有序数组中的重复项（27）
Leetcode75. 颜色分类（27）
Leetcode283. 移动零（39）
Leetcode240. 搜索二维矩阵 II（50）

10.4、滑动窗口

Leetcode3. 无重复字符的最长子串（438）
Leetcode28. 实现 strStr()（10）
Leetcode76. 最小覆盖子串（72）
Leetcode209. 长度最小的子数组（40）
Leetcode1004. 最大连续1的个数 III（15）

10.5、字符串

Leetcode6. Z 字形变换（12）
Leetcode14. 最长公共前缀（52）
Leetcode43. 字符串相乘（65）
Leetcode151. 颠倒字符串中的单词（76）
Leetcode165. 比较版本号（64）
Leetcode344. 反转字符串（16）
Leetcode443. 压缩字符串（17）
Leetcode468. 验证IP地址（42）
Leetcode557. 反转字符串中的单词 III（17）
Leetcode415. 字符串相加（138）

10.6、模拟

10.6.1、一维模拟

Leetcode9. 回文数（22）
Leetcode88. 合并两个有序数组（165）
Leetcode128. 最长连续序列（49）
Leetcode217. 存在重复元素（3）
Leetcode238. 除自身以外数组的乘积（7）
Leetcode657. 机器人能否返回原点
Leetcode剑指 Offer 61. 扑克牌中的顺子（17）

10.6.2、二维模拟

Leetcode48. 旋转图像（58）
Leetcode54. 螺旋矩阵（136）
Leetcode59. 螺旋矩阵 II（31）
Leetcode73. 矩阵置零（10）

10.6.3、数字模拟

Leetcode7. 整数反转（30）
Leetcode8. 字符串转换整数 (atoi)（88）
Leetcode89. 格雷编码（5）
Leetcode166. 分数到小数（11）
Leetcode171. 26进制数（12）
Leetcode231. 2 的幂（7）

10.7、位运算

Leetcode136. 只出现一次的数字（42）
Leetcode260. 只出现一次的数字 III（13）
剑指 Offer 15. 二进制中1的个数

10.8、数学题

Leetcode470. 用 Rand7() 实现 Rand10()（61）
Leetcode50. Pow(x, n)（31）
Leetcode172. 阶乘后的零（10）
Leetcode292. Nim 游戏（2）

10.9、设计题

Leetcode208. 实现前缀树（22）
Leetcode706. 设计哈希映射（10）

10.10、其他题

Leetcode31. 下一个排列（82）
Leetcode169. 多数元素（59）
Leetcode556. 下一个更大元素 III（16）

Reference

Github Python答案: https://github.com/HuKai97/Leetcode

CSDN: LeetCode算法题高频整理(精华篇)