極客時間算法學習之后開始跟著花花醬刷題。大概從4月份開始的。從今天開始（2020-8-24）開始做總結，復習一下已經刷過的題目。到目前為止leetcode刷題323道。
2020/8/24 完成題目整理，下一步是將每個題目都加上超鏈接。這個超鏈接盡可能都指向csdn的博客。

2020/10/23 完成12個題目完成了散列表。進度有點蝸速。大多數題目不能做到看一眼就知道解法，仿佛之前做的全忘記了。但是一看答案，就回想起當時自己做題的情景了。繼續。

2020/11/5 完成二叉樹、跳表、字符串部分。二叉樹部分有些代碼沒寫，只是看了看。跳表好早就想動手寫一寫。字符串部分也是好早就想綜合復習一下。

2020/11/14完成了圖的部分。數據結構部分的習題完成。開始算法部分的習題。

2020/11/30完成了二分。

2020/12/18 回溯算法刷起來相對簡單一些，hard題目需要再刷一次
2020/12/24 回溯算法刷完
2021/1/2 動態規劃刷完。發現在處理字符串的動態規劃問題的還是會有些理解不了的地方。本文章更新完畢。

文章目錄

• 1刷題原則
• 2 數據結構題目整理
• • 2.1 數組
  • 2.2鏈表
  • 2.3 棧
  • 2.4 隊列
  • 2.5 散列表
  • 2.6 二叉樹
  • 2.7 堆
  • 2.8 跳表
  • 2.9 圖
  • 2.10 Trie樹
• 3 算法題目整理
• • 3.1 排序
  • 3.2 二分
  • 3.3 搜索(BFS、DFS)/回溯
  • 3.4 哈希
  • 3.5 貪心
  • 3.6 分治
  • 3.7 動態規劃
  • 3.8 字符串匹配

1刷題原則

根據花花醬建議，梳理出以下結論。
要刷多少題
1 每個類型 10-20，總共200-300題

如何刷題
1 同類型題目一起刷
2 看代碼很重要，看至少3-5種不同實現
3 第一遍：5分鐘想不出來就看答案；第二遍：嘗試不看答案完整實現，一道題目不超過60min；第三遍：嘗試快速實現，15-20min實現不了就看答案
4 完整的手寫代碼，增強肌肉記憶
5 培養代碼風格

2 數據結構題目整理

根據刷題原則這是我第二次刷題。其實算上以前斷斷續續的，算三刷也不為過。
這次題目整理會把之前在極客時間算法題目中的課后題目和這次刷的題目一起整理一下。這部分整理數據結構的題目。

2.1 數組

15 3sum

169 Majority Element

41 Missing Positive

2.2鏈表

141 LinkedListCycle I

23 Merge k sorted lists

2.3 棧

20 Valid Parentheses

32 Longest Valid Parentheses

150 Evaluate Reverse Polish Notatio

2.4 隊列

641 Design Circular Deque

239 Sliding Window Maximum

2.5 散列表

實現一個基于鏈表法解決沖突問題的散列表
實現一個 LRU 緩存淘汰算法

2.6 二叉樹

實現一個二叉查找樹，并且支持插入、刪除、查找操作
實現查找二叉查找樹中某個節點的后繼、前驅節點
實現二叉樹前、中、后序以及按層遍歷
Invert Binary Tree
Maximum Depth of Binary Tree
Validate Binary Search Tree
Path Sum

2.7 堆

實現一個小頂堆、大頂堆(堆結構描述)、優先級隊列
實現堆排序利用優先級隊列
合并 K 個有序數組
求一組動態數據集合的最大 Top K

2.8 跳表

跳表的實現（參考小灰）

2.9 圖

實現有向圖、無向圖、有權圖、無權圖的鄰接矩陣和鄰接表表示方法
實現圖的深度優先搜索、廣度優先搜索
實現 Dijkstra 算法、A* 算法
實現拓撲排序的 Kahn 算法、DFS 算法

2.10 Trie樹

只包含 a～z 這 26 個英文字母的 Trie 樹

3 算法題目整理

3.1 排序

1 排序：實現歸并排序、快速排序、插入排序、冒泡排序、選擇排序
2 編程實現 O(n) 時間復雜度內找到一組數據的第 K 大元素
3 還要記得有桶排序、計數排序

3.2 二分

35 Search Insert Position
相似題目：34、704、981
tag：upper_bound

33 Search in Rotated Sorted Array
相似題目：81、153、154、162、852
tag:rotated;peek

69 Sqrt(x)
tag:upper_bound

74 Search a 2D Matrix

875 Koko Eating Bananas
相似題目：1011
tag：guess ans and check

4 Median of Two Sorted Arrays

378 Kth Smallest Element in a Sorted Matrix
相似題目：668
tag：k-th+matrix 對數組中的值做二分，也有guess and check的感覺

719 Find K-th Smallest Pair Distance
相似題目：786
tag：k-th+two pointers

3.3 搜索(BFS、DFS)/回溯

17 Letter Combinations of a Phone Number
相似題目：39、40、77、78、90、216
tag：組合

46 Permutations
相似題目：47、784、943、996
tag：排列

22 Generate Parentheses
相似題目 301
tag：DFS

37 Sudoku Solver
相似題目：51 52
tag：DFS

79 Word Search
相似題目：212
tag：DFS

127 Word Ladder
相似題目：126、752、818
tag：BFS

542 01 Matrix
相似題目：675、934
tag：BFS

698 Partition to K Equal Sum Subsets
相似題目：93、131、241、282、842
tag：排列

3.4 哈希

3.5 貪心

3.6 分治

169 Majority Element

153 Find Minimum in Rotated Sorted Array
相似題目 154

912 Sort and Array

315 Count of Smaller Numbers After Self

3.7 動態規劃

70 Climbing Stairs 相似題目：746、1137

303 Range Sum Query – Immutable 相似題目：1218

53 Maximum Subarray 相似題目：121

62 Unique Paths 相似題目：63、64、120、174、931、1210

85 Maximal Rectangle 相似題目：221、304、1277

198 House Robber 相似題目：213、309、740、790、801

279 Perfect Squares 相似題目：

139 Word Break 相似題目 140、818

300 Longest Increasing Subsequence 相似題目：673、1048

最小路徑和（詳細可看 @Smallfly 整理的 Minimum Path Sum）

編程實現萊文斯坦最短編輯距離

編程實現查找兩個字符串的最長公共子序列

3.8 字符串匹配

344 Reverse String

151 Reverse Words in a String

8 String to Integer (atoi)

KMP

AC自動機
AC介紹
AC自動機就是多模式匹配的kmp，文章沒有詳細看，抄來的代碼跑一跑。

總結

以上是生活随笔為你收集整理的数据结构与算法总结（完结）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。