本文轉(zhuǎn)載自知乎：Leetcode 面試高頻題 TimothyL
刷題前先確惫窭基本數(shù)據(jù)結(jié)構(gòu)知識已掌握：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識體系詳解、數(shù)據(jù)結(jié)構(gòu)skywang12345
LeetCode 做題心得，解題方法：動畫形式解LeetCode題目、cookbook
最終掌握各種數(shù)據(jù)結(jié)構(gòu)的原理棍掐、代碼實現(xiàn)烹俗、常用模板、應(yīng)用場景
高頻知識點(diǎn)
| 序號 | 題目類型 | 知識點(diǎn)概述 | 例題 | 難度評估 |
|---|---|---|---|---|
| 1 | 排序類（Sort） | 掌握快速排序嘹锁、歸并排序的原理與代碼實現(xiàn)，以及它們在數(shù)組着裹、鏈表领猾、區(qū)間等問題中的應(yīng)用。 | Leetcode 148. Sort List（鏈表歸并排序）骇扇，Leetcode 56. Merge Intervals（區(qū)間合并）摔竿，Leetcode 215. Kth Largest Element in an Array（數(shù)組快速選擇） | 中等 |
| 2 | 鏈表類（Linked List） | 掌握鏈表的實現(xiàn)、遍歷少孝、反轉(zhuǎn)继低、快慢指針等基本操作，以及它們在環(huán)形鏈表稍走、回文鏈表袁翁、合并鏈表等問題中的應(yīng)用柴底。 | Leetcode 141. Linked List Cycle（環(huán)形鏈表判斷），Leetcode 234. Palindrome Linked List（回文鏈表判斷）粱胜，Leetcode 21. Merge Two Sorted Lists（合并兩個有序鏈表） | 簡單 |
| 3 | 堆（Heap or Priority Queue）柄驻、棧（Stack）、隊列（Queue）焙压、哈希表類（Hashmap鸿脓、Hashset） | 掌握各個數(shù)據(jù)結(jié)構(gòu)的基本原理，增刪查改涯曲，以及它們在最近最少使用緩存野哭、滑動窗口、最大最小棧隊列幻件、最小生成樹拨黔、括號匹配等問題中的應(yīng)用。 | Leetcode 239. Sliding Window Maximum（滑動窗口最大值）傲武，Leetcode 23. Merge k Sorted Lists（合并k個有序鏈表）蓉驹，Leetcode 20. Valid Parentheses（括號匹配） | 中等 |
| 4 | 二分查找類（Binary Search） | 掌握二分查找的原理、邊界條件揪利、變形題目；分類：顯式與隱式狠持。顯式是指數(shù)組中存在目標(biāo)值疟位，隱式是指數(shù)組中不存在目標(biāo)值，但可以通過某種條件來確定目標(biāo)位置喘垂。 | Leetcode 704. Binary Search（顯式二分查找）甜刻，Leetcode 35. Search Insert Position（隱式二分查找） | 簡單 |
| 5 | 雙指針（Two Pointers） | 掌握雙指針的原理、分類正勒、應(yīng)用場景得院；分類：同向、背向章贞、相向祥绞。同向是指兩個指針從同一端開始移動，背向是指兩個指針從兩端開始移動鸭限，相向是指兩個指針從不同方向開始移動蜕径。 | 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） | 掌握二叉樹的遍歷兜喻、遞歸、迭代赡麦、層次遍歷朴皆、前中后序遍歷等基本操作帕识，以及它們在二叉搜索樹、平衡二叉樹遂铡、完全二叉樹等問題中的應(yīng)用肮疗。 | Leetcode 94. Binary Tree Inorder Traversal（中序遍歷），Leetcode 102. Binary Tree Level Order Traversal（層次遍歷）忧便，Leetcode 98. Validate Binary Search Tree（二叉搜索樹判斷） | 中等 |
| 7 | 寬度優(yōu)先搜索（BFS） | 解決什么問題：簡單圖的最短路徑長度族吻；拓?fù)渑判颍槐闅v一個圖（或者樹）珠增。BFS基本模板（需要記錄層數(shù)或者不需要記錄層數(shù)）超歌，以及它們在最短路徑、拓?fù)渑判虻俳獭u嶼數(shù)量等問題中的應(yīng)用巍举。 | Leetcode 127. Word Ladder（最短路徑），Leetcode 207. Course Schedule（拓?fù)渑判颍?a target="_blank">Leetcode 200. Number of Islands（島嶼數(shù)量） | 中等 |
| 8 | 深度優(yōu)先搜索（DFS） | 解決什么問題：圖中的符合某種特征的路徑以及長度凝垛、排列組合懊悯、遍歷一個圖（或者樹）、找出圖或者樹中符合題目要求的全部方案梦皮。DFS基本模板（需要記錄路徑炭分，不需要返回值 and 不需要記錄路徑，但需要記錄某些特征的返回值）剑肯，以及它們在組合數(shù)捧毛、子集、全排列等問題中的應(yīng)用让网。 | Leetcode 77. Combinations（組合數(shù)）呀忧，Leetcode 78. Subsets（子集），Leetcode 46. Permutations（全排列） | 中等 |
| 9 | 回溯法類（Backtracking） | 掌握回溯法的原理溃睹、剪枝技巧而账、常見模板，以及它們在N皇后因篇、數(shù)獨(dú)泞辐、單詞搜索等問題中的應(yīng)用。 | Leetcode 51. N-Queens（N皇后）惜犀，Leetcode 37. Sudoku Solver（數(shù)獨(dú)）铛碑，Leetcode 79. Word Search（單詞搜索） | 困難 |
| 10 | 前綴和（Prefix Sum） | 掌握前綴和的定義、計算方法虽界、應(yīng)用場景汽烦，以及它們在子數(shù)組和、區(qū)間和等問題中的應(yīng)用莉御。 | Leetcode 560. Subarray Sum Equals K（子數(shù)組和為k）撇吞，Leetcode 303. Range Sum Query - Immutable（區(qū)間和查詢） | 簡單 |
中頻知識點(diǎn)
| 序號 | 題目類型 | 知識點(diǎn)概述 | 例題 | 難度評估 |
|---|---|---|---|---|
| 1 | 并查集（Union Find） | 掌握并查集的原理俗冻、合并與查找操作的模板、應(yīng)用場景牍颈；牢記合并與查找兩個操作的模板迄薄，它們在連通分量、朋友圈煮岁、冗余連接等問題中的應(yīng)用讥蔽。 | Leetcode 547. Number of Provinces（朋友圈），Leetcode 684. Redundant Connection（冗余連接） | 中等 |
| 2 | 字典樹（Trie） | 掌握字典樹的原理画机、實現(xiàn)方法冶伞、應(yīng)用場景；它們在單詞搜索步氏、自動補(bǔ)全响禽、最長公共前綴等問題中的應(yīng)用。 | Leetcode 208. Implement Trie (Prefix Tree)（字典樹實現(xiàn)）荚醒，Leetcode 212. Word Search II（單詞搜索）芋类，Leetcode 14. Longest Common Prefix（最長公共前綴） | 中等 |
| 3 | 單調(diào)棧與單調(diào)隊列（Monotone Stack／Queue） | 單調(diào)指保留在棧或者隊列中的數(shù)字是單調(diào)遞增或者單調(diào)遞減的界阁；單調(diào)棧一般用于解決數(shù)組中找出每個數(shù)字的第一個大于／小于該數(shù)字的位置或者數(shù)字侯繁；在柱狀圖中最大的矩形、滑動窗口最大值等問題中的應(yīng)用泡躯。 | Leetcode 84. Largest Rectangle in Histogram（柱狀圖中最大的矩形）巫击，Leetcode 239. Sliding Window Maximum（滑動窗口最大值） | 困難 |
| 4 | 掃描線算法（Sweep Line） | 解決時間安排沖突，在會議室安排精续、日程表等問題中的應(yīng)用。 | Leetcode 253. Meeting Rooms II（會議室安排）粹懒，Leetcode 731. My Calendar II（日程表） | 中等 |
| 5 | TreeMap | 基于紅黑樹的樹狀 hashmap重付，它們在數(shù)據(jù)流中第K大元素、快照數(shù)組等問題中的應(yīng)用凫乖。 | Leetcode 703. Kth Largest Element in a Stream（數(shù)據(jù)流中第K大元素）确垫，Leetcode 1146. Snapshot Array（快照數(shù)組） | 中等 |
| 6 | 動態(tài)規(guī)劃（Dynamic Programming） | 掌握動態(tài)規(guī)劃的定義、狀態(tài)轉(zhuǎn)移方程帽芽、優(yōu)化技巧删掀，它們在最長遞增子序列、最長公共子序列导街、背包問題等問題中的應(yīng)用披泪。 | Leetcode 300. Longest Increasing Subsequence（最長遞增子序列），Leetcode 1143. Longest Common Subsequence（最長公共子序列）搬瑰，Leetcode 416. Partition Equal Subset Sum（背包問題） | 中等 |
