LeetCode 面试知识点小结
2023-03-02 本文已影响0人
三更冷
本文转载自知乎：Leetcode 面试高频题 TimothyL
刷题前先确保基本数据结构知识已掌握：数据结构基础知识体系详解、数据结构skywang12345
LeetCode 做题心得，解题方法：动画形式解LeetCode题目、cookbook
最终掌握各种数据结构的原理、代码实现、常用模板、应用场景
高频知识点
| 序号 | 题目类型 | 知识点概述 | 例题 | 难度评估 |
|---|---|---|---|---|
| 1 | 排序类（Sort） | 掌握快速排序、归并排序的原理与代码实现，以及它们在数组、链表、区间等问题中的应用。 | Leetcode 148. Sort List（链表归并排序），Leetcode 56. Merge Intervals（区间合并），Leetcode 215. Kth Largest Element in an Array（数组快速选择） | 中等 |
| 2 | 链表类（Linked List） | 掌握链表的实现、遍历、反转、快慢指针等基本操作，以及它们在环形链表、回文链表、合并链表等问题中的应用。 | Leetcode 141. Linked List Cycle（环形链表判断），Leetcode 234. Palindrome Linked List（回文链表判断），Leetcode 21. Merge Two Sorted Lists（合并两个有序链表） | 简单 |
| 3 | 堆（Heap or Priority Queue）、栈（Stack）、队列（Queue）、哈希表类（Hashmap、Hashset） | 掌握各个数据结构的基本原理，增删查改，以及它们在最近最少使用缓存、滑动窗口、最大最小栈队列、最小生成树、括号匹配等问题中的应用。 | Leetcode 239. Sliding Window Maximum（滑动窗口最大值），Leetcode 23. Merge k Sorted Lists（合并k个有序链表），Leetcode 20. Valid Parentheses（括号匹配） | 中等 |
| 4 | 二分查找类（Binary Search） | 掌握二分查找的原理、边界条件、变形题目；分类：显式与隐式。显式是指数组中存在目标值，隐式是指数组中不存在目标值，但可以通过某种条件来确定目标位置。 | Leetcode 704. Binary Search（显式二分查找），Leetcode 35. Search Insert Position（隐式二分查找） | 简单 |
| 5 | 双指针（Two Pointers） | 掌握双指针的原理、分类、应用场景；分类：同向、背向、相向。同向是指两个指针从同一端开始移动，背向是指两个指针从两端开始移动，相向是指两个指针从不同方向开始移动。 | Leetcode 26. Remove Duplicates from Sorted Array（同向双指针），Leetcode 167. Two Sum II - Input array is sorted（背向双指针），Leetcode 19. Remove Nth Node From End of List（相向双指针） | 简单 |
| 6 | 二叉树类（Binary Tree） | 掌握二叉树的遍历、递归、迭代、层次遍历、前中后序遍历等基本操作，以及它们在二叉搜索树、平衡二叉树、完全二叉树等问题中的应用。 | Leetcode 94. Binary Tree Inorder Traversal（中序遍历），Leetcode 102. Binary Tree Level Order Traversal（层次遍历），Leetcode 98. Validate Binary Search Tree（二叉搜索树判断） | 中等 |
| 7 | 宽度优先搜索（BFS） | 解决什么问题：简单图的最短路径长度；拓扑排序；遍历一个图（或者树）。BFS基本模板（需要记录层数或者不需要记录层数），以及它们在最短路径、拓扑排序、岛屿数量等问题中的应用。 | Leetcode 127. Word Ladder（最短路径），Leetcode 207. Course Schedule（拓扑排序），Leetcode 200. Number of Islands（岛屿数量） | 中等 |
| 8 | 深度优先搜索（DFS） | 解决什么问题：图中的符合某种特征的路径以及长度、排列组合、遍历一个图（或者树）、找出图或者树中符合题目要求的全部方案。DFS基本模板（需要记录路径，不需要返回值 and 不需要记录路径，但需要记录某些特征的返回值），以及它们在组合数、子集、全排列等问题中的应用。 | Leetcode 77. Combinations（组合数），Leetcode 78. Subsets（子集），Leetcode 46. Permutations（全排列） | 中等 |
| 9 | 回溯法类（Backtracking） | 掌握回溯法的原理、剪枝技巧、常见模板，以及它们在N皇后、数独、单词搜索等问题中的应用。 | Leetcode 51. N-Queens（N皇后），Leetcode 37. Sudoku Solver（数独），Leetcode 79. Word Search（单词搜索） | 困难 |
| 10 | 前缀和（Prefix Sum） | 掌握前缀和的定义、计算方法、应用场景，以及它们在子数组和、区间和等问题中的应用。 | Leetcode 560. Subarray Sum Equals K（子数组和为k），Leetcode 303. Range Sum Query - Immutable（区间和查询） | 简单 |
中频知识点
| 序号 | 题目类型 | 知识点概述 | 例题 | 难度评估 |
|---|---|---|---|---|
| 1 | 并查集（Union Find） | 掌握并查集的原理、合并与查找操作的模板、应用场景；牢记合并与查找两个操作的模板，它们在连通分量、朋友圈、冗余连接等问题中的应用。 | Leetcode 547. Number of Provinces（朋友圈），Leetcode 684. Redundant Connection（冗余连接） | 中等 |
| 2 | 字典树（Trie） | 掌握字典树的原理、实现方法、应用场景；它们在单词搜索、自动补全、最长公共前缀等问题中的应用。 | Leetcode 208. Implement Trie (Prefix Tree)（字典树实现），Leetcode 212. Word Search II（单词搜索），Leetcode 14. Longest Common Prefix（最长公共前缀） | 中等 |
| 3 | 单调栈与单调队列（Monotone Stack／Queue） | 单调指保留在栈或者队列中的数字是单调递增或者单调递减的；单调栈一般用于解决数组中找出每个数字的第一个大于／小于该数字的位置或者数字；在柱状图中最大的矩形、滑动窗口最大值等问题中的应用。 | Leetcode 84. Largest Rectangle in Histogram（柱状图中最大的矩形），Leetcode 239. Sliding Window Maximum（滑动窗口最大值） | 困难 |
| 4 | 扫描线算法（Sweep Line） | 解决时间安排冲突，在会议室安排、日程表等问题中的应用。 | Leetcode 253. Meeting Rooms II（会议室安排），Leetcode 731. My Calendar II（日程表） | 中等 |
| 5 | TreeMap | 基于红黑树的树状 hashmap，它们在数据流中第K大元素、快照数组等问题中的应用。 | Leetcode 703. Kth Largest Element in a Stream（数据流中第K大元素），Leetcode 1146. Snapshot Array（快照数组） | 中等 |
| 6 | 动态规划（Dynamic Programming） | 掌握动态规划的定义、状态转移方程、优化技巧，它们在最长递增子序列、最长公共子序列、背包问题等问题中的应用。 | Leetcode 300. Longest Increasing Subsequence（最长递增子序列），Leetcode 1143. Longest Common Subsequence（最长公共子序列），Leetcode 416. Partition Equal Subset Sum（背包问题） | 中等 |
