Leetcode面试高频题分类刷题总结

2022-03-10 15 min

朋友给我的就不公开了

Leetcode面试高频题分类刷题总结

受启于: https://zhuanlan.zhihu.com/p/349940945

Sat 5 Mar 2022 00:37

EST

本文一共200多道题, 算上一些附加的衍生题差不多有250+, 基本上很少有easy题目, 大部分都是medium, 少部分hard, 足够应对大部分的算法面试了。

**排序类 (Sort) : **

基础知识: Quick Sort & Merge Sort 的实现, Time Complexity, In-place, Stability, Performance.
入门题目:
- Leetcode 148. Sort List
- Leetcode 56. Merge Intervals
- Leetcode 27. Remove elements
进阶题目:
- Leetcode 179. Largest Number
- Leetcode 75. Sort Colors

**选择类 (Selection): **

Quick Selection, Heapsort. 知道两者的取舍, 知道 C++ STL 中两个对应 method. 手写快速选择有时候是必要的.
- Leetcode 215, 347, 2099. 这三题有清晰的递进关系.
- Leetcode 4. Median of Two Sorted Arrays

**链表类 (Linked List) : **

基础知识: 链表如何实现, 如何遍历链表。链表可以保证头部尾部插入删除操作都是O (1) , 查找任意元素位置O (N)
基础题目:
- Leetcode 206. Reverse Linked List
- Leetcode 876. Middle of the Linked List

快慢指针和链表反转几乎是所有链表类问题的基础, 尤其是反转链表, 代码很短, 建议直接背熟。

进阶题目:
- Leetcode 160. Intersection of Two Linked Lists
- Leetcode 141. Linked List Cycle (Linked List Cycle II)
- Leetcode 92. Reverse Linked List II
- Leetcode 328. Odd Even Linked List

Heap, Dictionary (Set, Map, Hashmap), Stack, Queue:

基础知识: 请熟读 Introduction of Algorithm 相关章节.
Queue题目:
- Leetcode 225. Implement Stack using Queues
- Leetcode 346. Moving Average from Data Stream
- Leetcode 281. Zigzag Iterator
- Leetcode 1429. First Unique Number
- Leetcode 54. Spiral Matrix
- Leetcode 362. Design Hit Counter
Stack题目:
- Leetcode 155. Min Stack (follow up Leetcode 716 Max Stack)
- Leetcode 232. Implement Queue using Stacks
- Leetcode 150. Evaluate Reverse Polish Notation
- Leetcode 224. Basic Calculator II (I, II, III, IV)
- Leetcode 20. Valid Parentheses
- Leetcode 1472. Design Browser History
- Leetcode 1209. Remove All Adjacent Duplicates in String II
- Leetcode 1249. Minimum Remove to Make Valid Parentheses
- Leetcode 735. Asteroid Collision
Hashmap/ Hashset题目:
- Leetcode 1. Two Sum
- Leetcode 146. LRU Cache (Python中可以使用OrderedDict来代替)
- Leetcode 128. Longest Consecutive Sequence
- Leetcode 73. Set Matrix Zeroes
- Leetcode 380. Insert Delete GetRandom O(1)
- Leetcode 49. Group Anagrams
- Leetcode 350. Intersection of Two Arrays II
- Leetcode 299. Bulls and Cows
- Leetcode 348 Design Tic-Tac-Toe
Heap／Priority Queue题目:
- Leetcode 973. K Closest Points
- Leetcode 347. Top k Largest Elements
- Leetcode 23. Merge K Sorted Lists
- Leetcode 264. Ugly Number II
- Leetcode 1086. High Five
- Leetcode 88. Merge Sorted Arrays
- Leetcode 692. Top K Frequent Words
- Leetcode 378. Kth Smallest Element in a Sorted Matrix
- Leetcode 295. Find Median from Data Stream (标准解法是双heap, 但是SortedDict会非常容易)
- Leetcode 767. Reorganize String
- Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (这个题用单调双端队列/TreeMap/双heap都可以)
- Leetcode 895. Maximum Frequency Stack
Map 题目:
- Leetcode 729 My Calendar I
- Leetcode 981 Time Based Key-Value Store
- Leetcode 846 Hand of Straights
- Leetcode 218 The Skyline Problem
- Leetcode 480. Sliding Window Median (这个题用TreeMap超级方便)
- Leetcode 318 Count of Smaller Numbers After Self (这个题线段树/二分索引树/TreeMap都可以)

Binary Search

三大模板: [L, R), [L, R], Breakpoint.
显式二分法:
- Leetcode 34. Find First and Last Position of Element in Sorted Array
- Leetcode 33. Search in Rotated Sorted Array
- Leetcode 1095. Find in Mountain Array
- Leetcode 162. Find Peak Element
- Leetcode 278. First Bad Version
- Leetcode 74. Search a 2D Matrix
- Leetcode 240. Search a 2D Matrix II
隐式二分法:
- Leetcode 69. Sqrt(x)
- Leetcode 540. Single Element in a Sorted Array
- Leetcode 644. Maximum Average Subarray II
- Leetcode 528. Random Pick with Weight
- Leetcode 1300. Sum of Mutated Array Closest to Target
- Leetcode 1060. Missing Element in Sorted Array
- Leetcode 1062. Longest Repeating Substring
- Leetcode 1891. Cutting Ribbons

**双指针 (2 Pointer) : **

基础知识: 常见双指针算法分为三类, 同向 (即两个指针都相同一个方向移动) , 背向 (两个指针从相同或者相邻的位置出发, 背向移动直到其中一根指针到达边界为止) , 相向 (两个指针从两边出发一起向中间移动直到两个指针相遇)
背向双指针: (基本上全是回文串的题)
- Leetcode 409. Longest Palindrome
- Leetcode 125. Valid Palindrome
- Leetcode 5. Longest Palindromic Substring
相向双指针: (以two sum为基础的一系列题)
- Leetcode 1. Two Sum (这里使用的是先排序的双指针算法, 不同于hashmap做法)
- Leetcode 167. Two Sum II - Input array is sorted
- Leetcode 15. 3Sum
- Leetcode 16. 3Sum Closest
- Leetcode 18. 4Sum
- Leetcode 454. 4Sum II
- Leetcode 277. Find the Celebrity
- Leetcode 11. Container With Most Water
同向双指针: (个人觉得最难的一类题, 可以参考下这里 TimothyL: Leetcode 同向双指针/滑动窗口类代码模板)
- Leetcode 283. Move Zeroes
- Leetcode 26. Remove Duplicate Numbers in Array
- Leetcode 395. Longest Substring with At Least K Repeating Characters
- Leetcode 340. Longest Substring with At Most K Distinct Characters
- Leetcode 424. Longest Repeating Character Replacement
- Leetcode 76. Minimum Window Substring
- Leetcode 3. Longest Substring Without Repeating Characters
- Leetcode 1004 Max Consecutive Ones III

深度优先搜索 (DFS) :

基础知识:
- 常见的DFS用来解决什么问题？(1) 图中 (有向无向皆可) 的符合某种特征 (比如最长) 的路径以及长度 (2) 排列组合 (3) 遍历一个图 (或者树) (4) 找出图或者树中符合题目要求的全部方案
- DFS基本模板 (需要记录路径, 不需要返回值 and 不需要记录路径, 但需要记录某些特征的返回值)
- 除了遍历之外多数情况下时间复杂度是指数级别, 一般是O(方案数×找到每个方案的时间复杂度)
- 递归题目都可以用非递归迭代的方法写, 但一般实现起来非常麻烦
基于树的DFS: 需要记住递归写前序中序后序遍历二叉树的模板
- Leetcode 543 Diameter of Binary Tree
- Leetcode 226 Invert Binary Tree
- Leetcode 101 Symmetric Tree
- Leetcode 951 Flip Equivalent Binary Trees
- Leetcode 124 Binary Tree Maximum Path Sum
- Leetcode 236 Lowest Common Ancestor of a Binary Tree (相似题: 235/1650)
- Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal
- Leetcode 104 Maximum Depth of Binary Tree
- Leetcode 987 Vertical Order Traversal of a Binary Tree
- Leetcode 1485 Clone Binary Tree With Random Pointer
- Leetcode 572 Subtree of Another Tree
- Leetcode 863 All Nodes Distance K in Binary Tree
- Leetcode 1110 Delete Nodes And Return Forest
二叉搜索树 (BST) : BST特征: 中序遍历为单调递增的二叉树, 换句话说, 根节点的值比左子树任意节点值都大, 比右子树任意节点值都小, 增删查改均为O (h) 复杂度, h为树的高度; 注意不是所有的BST题目都需要递归, 有的题目只需要while循环即可
- Leetcode 230 Kth Smallest element in a BST
- Leetcode 98 Validate Binary Search Tree
- Leetcode 270 Cloest Binary Search Tree Value
- Leetcode 235 Lowest Common Ancestor of a Binary Search Tree
- Leetcode 669 Trim a Binary Search Tree
- Leetcode 700 Search in a Binary Search Tree
- Leetcode 108 Convert Sorted Array to Binary Search Tree
- Leetcode 333 Largest BST Subtree (与98类似)
- Leetcode 285 Inorder Successor in BST (I, II)
基于图的DFS: 和BFS一样一般需要一个set来记录访问过的节点, 避免重复访问造成死循环; Word XXX 系列面试中非常常见, 例如word break, word ladder, word pattern, word search。
- Leetcode 341 Flatten Nested List Iterator (339 364)
- Leetcode 394 Decode String
- Leetcode 51 N-Queens (I II基本相同)
- Leetcode 291 Word Pattern II (I为简单的Hashmap题)
- Leetcode 126 Word Ladder II (I为BFS题目)
- Leetcode 93 Restore IP Addresses
- Leetcode 22 Generate Parentheses
- Leetcode 586 Score of Parentheses
- Leetcode 301 Remove Invalid Parentheses
- Leetcode 37 Sodoku Solver
- Leetcode 212 Word Search II (I, II)
- Leetcode 1087 Brace Expansion
- Leetcode 399 Evaluate Division
- Leetcode 1274 Number of Ships in a Rectangle
- Leetcode 1376 Time Needed to Inform All Employees
- Leetcode 694 Number of Distinct Islands
- Leetcode 131 Palindrome Partitioning
基于排列组合的DFS: 其实与图类DFS方法一致, 但是排列组合的特征更明显
- Leetcode 17 Letter Combinations of a Phone Number
- Leetcode 39 Combination Sum (I, II, III相似, IV为动态规划题目)
- Leetcode 78 Subsets (I, II 重点在于如何去重)
- Leetcode 46 Permutation (I, II 重点在于如何去重)
- Leetcode 77 Combinations (I, II 重点在于如何去重)
- Leetcode 698 Partition to K Equal Sum Subsets
- Leetcode 526 Beautiful Arrangement (similar to 46)
记忆化搜索 (DFS + Memoization Search) : 算是动态规划的一种, 递归每次返回时同时记录下已访问过的节点特征, 避免重复访问同一个节点, 可以有效的把指数级别的DFS时间复杂度降为多项式级别; 注意这一类的DFS必须在最后有返回值, 不可以用排列组合类型的DFS方法写; for循环的dp题目都可以用记忆化搜索的方式写, 但是不是所有的记忆化搜索题目都可以用for循环的dp方式写。
- Leetcode 139 Word Break II
- Leetcode 72 Edit Distance
- Leetcode 377 Combination Sum IV
- Leetcode 1235 Maximum Profit in Job Scheduling
- Leetcode 1335 Minimum Difficulty of a Job Schedule
- Leetcode 1216 Valid Palindrome III
- Leetcode 97 Interleaving String
- Leetcode 472 Concatenated Words
- Leetcode 403 Frog Jump
- Leetcode 329 Longest Increasing Path in a Matrix

拓扑排序 (Topo Sort) :

常见题目:
- Leetcode 207 Course Schedule (I, II)
- Leetcode 444 Sequence Reconstruction
- Leetcode 269 Alien Dictionary
- Leetcode 310 Minimum Height Trees
- Leetcode 366 Find Leaves of Binary Tree

**宽度优先搜索 (BFS) : **

基础知识:
常见的BFS用来解决什么问题？(1) 简单图 (有向无向皆可) 的最短路径长度, 注意是长度而不是具体的路径 (2) 遍历一个图 (或者树)
BFS基本模板 (需要记录层数或者不需要记录层数)
多数情况下时间复杂度空间复杂度都是O (N+M) , N为节点个数, M为边的个数
基于树的BFS: 不需要专门一个set来记录访问过的节点
- Leetcode 102 Binary Tree Level Order Traversal
- Leetcode 103 Binary Tree Zigzag Level Order Traversal
- Leetcode 297 Serialize and Deserialize Binary Tree (很好的BFS和双指针结合的题)
- Leetcode 314 Binary Tree Vertical Order Traversal
基于图的BFS: (一般需要一个set来记录访问过的节点)
- Leetcode 200. Number of Islands
- Leetcode 133. Clone Graph
- Leetcode 127. Word Ladder
- Leetcode 490. The Maze
- Leetcode 323. Connected Component in Undirected Graph
- Leetcode 130. Surrounded Regions
- Leetcode 752. Open the Lock
- Leetcode 815. Bus Routes
- Leetcode 1091. Shortest Path in Binary Matrix
- Leetcode 542. 01 Matrix
- Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

**前缀和 (Prefix Sum) **

基础知识: 前缀和本质上是在一个list当中, 用O (N) 的时间提前算好从第0个数字到第i个数字之和, 在后续使用中可以在O (1) 时间内计算出第i到第j个数字之和, 一般很少单独作为一道题出现, 而是很多题目中的用到的一个小技巧.
常见题目:
- Leetcode 53 Maximum Subarray
- Leetcode 1423 Maximum Points You Can Obtain from Cards
- Leetcode 1031 Maximum Sum of Two Non-Overlapping Subarrays
- Leetcode 523 Continuous Subarray Sum
- Leetcode 304 Range Sum Query 2D - Immutable

以上内容皆为面试中高频的知识点. 以下知识点和题目在面试中属于中等频率.

并查集 (Union Find) : 把两个或者多个集合合并为一个集合

以近乎 $O(1)$ 的时间进行归类. UNITE, FIND, 以及两大优化; rank 的精确定义.
常见题目:
- Leetcode 721 Accounts Merge
- Leetcode 547 Number of Provinces
- Leetcode 737 Sentence Similarity II
- Leetcode 305 Number of Islands II

**字典树 (Trie, Prefix Tree) **

多数情况下可以通过用一个set来记录所有单词的prefix来替代, 时间复杂度不变, 空间复杂度提升.
常见题目:
- Leetcode 208 Implement Trie (Prefix Tree)
- Leetcode 211 Design Add and Search Words Data Structure
- Leetcode 1268 Search Suggestions System
- Leetcode 212 Word Search II

**单调栈 (Monotone Stack／Queue) **

单调的意思是保留在栈或者队列中的数字是单调递增或者单调递减的. 参见: “Monotone Stack”.
常见题目:
- Leetcode 85 Maximum Rectangle
- Leetcode 84 Largest Rectangle in Histogram
- Leetcode 907 Sum of Subarray Minimums (与84类似)
- Leetcode 739 Daily Temperatures
- Leetcode 901 Online Stock Span
- Leetcode 503 Next Greater Element II
- Leetcode 239 Sliding Window Maximum (唯一的单调队列题)

**扫描线算法 (Sweep Line) **

基础知识: 一个很巧妙的解决时间安排冲突的算法, 本身比较容易些也很容易理解
常见题目:
- Leetcode 253 Meeting Room II (Meeting Room I也可以使用)
- Leetcode 218 The Skyline Problem
- Leetcode 759 Employee Free Time

**动态规划 (Dynamic Programming) **

基础知识: 这里指的是用for循环方式的动态规划, 非Memoization Search方式。DP可以在多项式时间复杂度内解决DFS需要指数级别的问题。常见的题目包括找最大最小, 找可行性, 找总方案数等, 一般结果是一个Integer或者Boolean。动态规划有很多分支.
常见题目:
- Leetcode 674 Longest Continuous Increasing Subsequence (接龙型dp)
- Leetcode 62 Unique Paths II
- Leetcode 70 Climbing Stairs
- Leetcode 64 Minimum Path Sum
- Leetcode 368 Largest Divisible Subset (接龙型dp)
- Leetcode 300 Longest Increasing Subsequence (接龙型dp)
- Leetcode 354 Russian Doll Envelopes (接龙型dp, 300的2D版)
- Leetcode 256 Paint House
- Leetcode 121 Best Time to Buy and Sell Stock
- Leetcode 55 Jump Game
- Leetcode 45 Jump Game II
- Leetcode 132 Palindrome Partitioning II
- Leetcode 312 Burst Balloons (区间型dp)
- Leetcode 1143 Longest Common Subsequence (前缀型dp)
- Leetcode 1062 Longest Repeating Substring (dp方法与longest common substring一致)
- Leetcode 718 Maximum Length of Repeated Subarray (和1062本质上一样)
- Leetcode 174 Dungeon Game
- Leetcode 115 Distinct Subsequences
- Leetcode 72 Edit Distance
- Leetcode 91 Decode Ways
- Leetcode 639 Decode Ways II
- Leetcode 712 Minimum ASCII Delete Sum for Two Strings
- Leetcode 221 Maximal Square
- Leetcode 1277 Count Square Submatrices with All Ones (可以使用221一样的解法)
- Leetcode 198 House Robber
- Leetcode 213 House Robber II
- Leetcode 740 Delete and Earn
- Leetcode 87 Scramble String
- Leetcode 1140 Stone Game II
- Leetcode 322 Coin Change
- Leetcode 518 Coin Change II (01背包型)
- Leetcode 1048 Longest String Chain
- Leetcode 44 Wildcard Matching
- Leetcode 10 Regular Expression Matching
- Leetcode 32 Longest Valid Parentheses
- Leetcode 1235 Maximum Profit in Job Scheduling (DP + binary search)
- Leetcode 1043 Partition Array for Maximum Sum
- Leetcode 926 Flip String to Monotone Increasing

Algorithm LeetCode