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

https://zhuanlan.zhihu.com/p/349940945

以下8个门类是面试中最常考的算法与数据结构知识点。

排序类（Sort）：

• 基础知识：快速排序（Quick Sort）， 归并排序（Merge Sort）的原理与代码实现。需要能讲明白代码中每一行的目的。快速排序时间复杂度平均状态下O（NlogN），空间复杂度O（1），归并排序最坏情况下时间复杂度O（NlogN），空间复杂度O（N）
• 入门题目：
  • Leetcode 148. Sort List
  • Leetcode 56. Merge Intervals
  • Leetcode 27. Remove elements
• 进阶题目：
  • Leetcode 179. Largest Number
  • Leetcode 75. Sort Colors
  • Leetcode 215. Kth Largest Element （可以用堆的解法替代）
  • Leetcode 4. Median of Two Sorted Arrays

注意：后两题是与快速排序非常相似的快速选择（Quick Select）算法，面试中很常考

链表类（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 or Priority Queue）、栈（Stack）、队列（Queue）、哈希表类（Hashmap、Hashset）：

• 基础知识：各个数据结构的基本原理，增删查改复杂度。
• 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

二分法（Binary Search）：

• 基础知识：二分法是用来解法基本模板，时间复杂度logN；常见的二分法题目可以分为两大类，显式与隐式，即是否能从字面上一眼看出二分法的特点：要查找的数据是否可以分为两部分，前半部分为X，后半部分为O
• 显式二分法：
  • 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
  • Leetcode 410. Split Array Largest Sum (与1891类似)

双指针（2 Pointer）：

• 基础知识：常见双指针算法分为三类，同向（即两个指针都相同一个方向移动），背向（两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止），相向（两个指针从两边出发一起向中间移动直到两个指针相遇）
• 背向双指针：(基本上全是回文串的题)
  • Leetcode 409. Longest Palindrome
  • Leetcode 125. Valid Palindrome (I、II)
  • Leetcode 5. Longest Palindromic Substring
  • Leetcode 647. Palindromic Substrings
• 相向双指针：(以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
  • Leetcode 186 Reverse Words in a String II
• 同向双指针：（个人觉得最难的一类题，可以参考下这里 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
  • Leetcode 1658 Minimum Operations to Reduce X to Zero

宽度优先搜索（BFS）：面试中最常考的

• 基础知识：
  • 常见的BFS用来解决什么问题？(1) 简单图（有向无向皆可）的最短路径长度，注意是长度而不是具体的路径（2）拓扑排序 （3） 遍历一个图（或者树）
• 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
  • Leetcode 417. Pacific Atlantic Water Flow
• 拓扑排序：（https://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F）
  • 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

深度优先搜索（DFS）：面试中最常考的（分类的稍微有点粗糙了，没有细分出回溯/分治来，准备找个时间给每个DFS的题标记下是哪种DFS）

• 基础知识：
  • 常见的DFS用来解决什么问题？(1) 图中（有向无向皆可）的符合某种特征（比如最长）的路径以及长度（2）排列组合（3） 遍历一个图（或者树）（4）找出图或者树中符合题目要求的全部方案
  • DFS基本模板（需要记录路径，不需要返回值 and 不需要记录路径，但需要记录某些特征的返回值）
  • 除了遍历之外多数情况下时间复杂度是指数级别，一般是O(方案数×找到每个方案的时间复杂度)
  • 递归题目都可以用非递归迭代的方法写，但一般实现起来非常麻烦
• 基于树的DFS：需要记住递归写前序中序后序遍历二叉树的模板
  • Leetcode 543 Diameter of Binary Tree (分治)
  • Leetcode 124 Binary Tree Maximum Path Sum (分治)
  • Leetcode 226 Invert Binary Tree (分治)
  • Leetcode 101 Symmetric Tree (回溯 or 分治)
  • Leetcode 951 Flip Equivalent Binary Trees (分治)
  • Leetcode 236 Lowest Common Ancestor of a Binary Tree (相似题：235、1650) (回溯 or 分治)
  • Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal (分治)
  • Leetcode 104 Maximum Depth of Binary Tree (回溯 or 分治)
  • 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 856 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必须在最后有返回值（分治法），不可以用回溯法; 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

前缀和（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