GitHub Python項目推薦|數據結構和算法必知必會的50個代碼實現

項目熱度

標星(star)：8860

關注(watch)：486

拷貝(fork)：2644

貢獻人數：98 （貢獻人數很多哈）

倉庫大小：1 MB

最後更新：2019-08-17

代碼提交活躍：

開發語言

主要語言：Python

語言比例：Python:15.12%、C:14.77%、C++:13.48%、Scala:9.96%、Go:7.49%、Java:6.95%、JavaScript:6.07%、PHP:5.71%、Rust:5.41%、C#:4.21%、TypeScript:3.95%、Objective-C:2.83%、Swift:2.39%、Kotlin:1.49%、HTML:0.16%、Shell:0.00%

項目概述

數據結構和算法必知必會的50個代碼實現 ，內容包括

數組

• 實現一個支持動態擴容的數組
• 實現一個大小固定的有序數組，支持動態增刪改操作
• 實現兩個有序數組合併為一個有序數組

鏈表

• 實現單鏈表、循環鏈表、雙向鏈表，支持增刪操作
• 實現單鏈表反轉
• 實現兩個有序的鏈表合併為一個有序鏈表
• 實現求鏈表的中間結點

棧

• 用數組實現一個順序棧
• 用鏈表實現一個鏈式棧
• 編程模擬實現一個瀏覽器的前進、後退功能

隊列

• 用數組實現一個順序隊列
• 用鏈表實現一個鏈式隊列
• 實現一個循環隊列

遞歸

• 編程實現斐波那契數列求值f(n)=f(n-1)+f(n-2)
• 編程實現求階乘n!
• 編程實現一組數據集合的全排列

排序

• 實現歸併排序、快速排序、插入排序、冒泡排序、選擇排序
• 編程實現O(n)時間複雜度內找到一組數據的第K大元素

二分查找

• 實現一個有序數組的二分查找算法
• 實現模糊二分查找算法（比如大於等於給定值的第一個元素）

散列表

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

字符串

• 實現一個字符集，只包含a～z這26個英文字母的Trie樹
• 實現樸素的字符串匹配算法

二叉樹

• 實現一個二叉查找樹，並且支持插入、刪除、查找操作
• 實現查找二叉查找樹中某個節點的後繼、前驅節點
• 實現二叉樹前、中、後序以及按層遍歷

堆

• 實現一個小頂堆、大頂堆、優先級隊列
• 實現堆排序
• 利用優先級隊列合併K個有序數組
• 求一組動態數據集合的最大Top K

圖

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

回溯

• 利用回溯算法求解八皇后問題
• 利用回溯算法求解0-1揹包問題

分治

• 利用分治算法求一組數據的逆序對個數

動態規劃

• 0-1揹包問題
• 最小路徑和
• 編程實現萊文斯坦最短編輯距離
• 編程實現查找兩個字符串的最長公共子序列
• 編程實現一個數據序列的最長遞增子序列

項目地址

https://github.com/wangzheng0822/algo