點(diǎn)擊上方“AI有道”，選擇“置頂”公眾號

重磅干貨，第一時間送達(dá)

數(shù)據(jù)結(jié)構(gòu)和算法是程序員的內(nèi)功心法和基本功。無論是人工智能還是其它計(jì)算機(jī)科學(xué)領(lǐng)域，掌握扎實(shí)的數(shù)據(jù)結(jié)構(gòu)和算法知識，往往會助力不少！今天給大家推薦一份不錯的數(shù)據(jù)結(jié)構(gòu)與算法資源。特點(diǎn)是：全代碼實(shí)現(xiàn)！

這份資源的作者王爭老師是前 Google 工程師，5 萬+人跟著學(xué)的《數(shù)據(jù)結(jié)構(gòu)和算法之美》專欄作者。他總結(jié)了程序員必備的 50 個數(shù)據(jù)結(jié)構(gòu)與算法，以及相應(yīng)的代碼實(shí)現(xiàn)。開源地址為：

https://github.com/wangzheng0822/algo

我們來看一下這必備的 50 個數(shù)據(jù)結(jié)構(gòu)與算法究竟包含了哪些內(nèi)容。

數(shù)組?

• 問題：實(shí)現(xiàn)一個支持動態(tài)擴(kuò)容的數(shù)組

• 問題：實(shí)現(xiàn)一個大小固定的有序數(shù)組，支持動態(tài)增刪改操作

• 問題：實(shí)現(xiàn)兩個有序數(shù)組合并為一個有序數(shù)組

鏈表?

• 問題：實(shí)現(xiàn)單鏈表、循環(huán)鏈表、雙向鏈表，支持增刪操作

• 問題：實(shí)現(xiàn)單鏈表反轉(zhuǎn)

• 問題：實(shí)現(xiàn)兩個有序的鏈表合并為一個有序鏈表

• 問題：實(shí)現(xiàn)求鏈表的中間結(jié)點(diǎn)

棧?

• 問題：用數(shù)組實(shí)現(xiàn)一個順序棧

• 問題：用鏈表實(shí)現(xiàn)一個鏈?zhǔn)綏?

• 問題：編程模擬實(shí)現(xiàn)一個瀏覽器的前進(jìn)、后退功能

隊(duì)列?

• 問題：用數(shù)組實(shí)現(xiàn)一個順序隊(duì)列

• 問題：用鏈表實(shí)現(xiàn)一個鏈?zhǔn)疥?duì)列

• 問題：實(shí)現(xiàn)一個循環(huán)隊(duì)列

遞歸?

• 問題：編程實(shí)現(xiàn)斐波那契數(shù)列求值f(n)=f(n-1)+f(n-2)

• 問題：編程實(shí)現(xiàn)求階乘n!

• 問題：編程實(shí)現(xiàn)一組數(shù)據(jù)集合的全排列

排序?

• 問題：實(shí)現(xiàn)歸并排序、快速排序、插入排序、冒泡排序、選擇排序

• 問題：編程實(shí)現(xiàn)O(n)時間復(fù)雜度內(nèi)找到一組數(shù)據(jù)的第K大元素

二分查找?

• 問題：實(shí)現(xiàn)一個有序數(shù)組的二分查找算法

• 問題：實(shí)現(xiàn)模糊二分查找算法（比如大于等于給定值的第一個元素）

散列表?

• 問題：實(shí)現(xiàn)一個基于鏈表法解決沖突問題的散列表

• 問題：實(shí)現(xiàn)一個LRU緩存淘汰算法

字符串?

• 問題：實(shí)現(xiàn)一個字符集，只包含a～z這26個英文字母的Trie樹

• 問題：實(shí)現(xiàn)樸素的字符串匹配算法

二叉樹?

• 問題：實(shí)現(xiàn)一個二叉查找樹，并且支持插入、刪除、查找操作

• 問題：實(shí)現(xiàn)查找二叉查找樹中某個節(jié)點(diǎn)的后繼、前驅(qū)節(jié)點(diǎn)

• 問題：實(shí)現(xiàn)二叉樹前、中、后序以及按層遍歷

堆?

• 問題：實(shí)現(xiàn)一個小頂堆、大頂堆、優(yōu)先級隊(duì)列

• 問題：實(shí)現(xiàn)堆排序

• 問題：利用優(yōu)先級隊(duì)列合并K個有序數(shù)組

• 問題：求一組動態(tài)數(shù)據(jù)集合的最大Top K

圖?

• 問題：實(shí)現(xiàn)有向圖、無向圖、有權(quán)圖、無權(quán)圖的鄰接矩陣和鄰接表表示方法

• 問題：實(shí)現(xiàn)圖的深度優(yōu)先搜索、廣度優(yōu)先搜索

• 問題：實(shí)現(xiàn)Dijkstra算法、A*算法

• 問題：實(shí)現(xiàn)拓?fù)渑判虻腒ahn算法、DFS算法

回溯?

• 問題：利用回溯算法求解八皇后問題

• 問題：利用回溯算法求解0-1背包問題

分治?

• 問題：利用分治算法求一組數(shù)據(jù)的逆序?qū)€數(shù)

動態(tài)規(guī)劃?

• 問題：0-1背包問題

• 問題：最小路徑和

• 問題：編程實(shí)現(xiàn)萊文斯坦最短編輯距離

• 問題：編程實(shí)現(xiàn)查找兩個字符串的最長公共子序列

• 問題：編程實(shí)現(xiàn)一個數(shù)據(jù)序列的最長遞增子序列

以上所有的數(shù)據(jù)結(jié)構(gòu)與算法都配備相應(yīng)的程序代碼。一大特點(diǎn)是代碼配備多種編程語言，例如 Python、C、Java、Go、Scala 等。

舉例來說，關(guān)于常見的排序算法，例如冒泡排序、插入排序、選擇排序，作者給出了相應(yīng)的 Python 代碼實(shí)現(xiàn)：

"""Bubble sort, insertion sort and selection sort冒泡排序、插入排序、選擇排序Author: Wenru """from typing import List# 冒泡排序 def bubble_sort(a: List[int]):length = len(a)if length <= 1:returnfor i in range(length):made_swap = Falsefor j in range(length - i - 1):if a[j] > a[j + 1]:a[j], a[j + 1] = a[j + 1], a[j]made_swap = Trueif not made_swap:break# 插入排序 def insertion_sort(a: List[int]):length = len(a)if length <= 1:returnfor i in range(1, length):value = a[i]j = i - 1while j >= 0 and a[j] > value:a[j + 1] = a[j]j -= 1a[j + 1] = value# 選擇排序 def selection_sort(a: List[int]):length = len(a)if length <= 1:returnfor i in range(length):min_index = imin_val = a[i]for j in range(i, length):if a[j] < min_val:min_val = a[j]min_index = ja[i], a[min_index] = a[min_index], a[i]def test_bubble_sort():test_array = [1, 1, 1, 1]bubble_sort(test_array)assert test_array == [1, 1, 1, 1]test_array = [4, 1, 2, 3]bubble_sort(test_array)assert test_array == [1, 2, 3, 4]test_array = [4, 3, 2, 1]bubble_sort(test_array)assert test_array == [1, 2, 3, 4]def test_insertion_sort():test_array = [1, 1, 1, 1]insertion_sort(test_array)assert test_array == [1, 1, 1, 1]test_array = [4, 1, 2, 3]insertion_sort(test_array)assert test_array == [1, 2, 3, 4]test_array = [4, 3, 2, 1]insertion_sort(test_array)assert test_array == [1, 2, 3, 4]def test_selection_sort():test_array = [1, 1, 1, 1]selection_sort(test_array)assert test_array == [1, 1, 1, 1]test_array = [4, 1, 2, 3]selection_sort(test_array)assert test_array == [1, 2, 3, 4]test_array = [4, 3, 2, 1]selection_sort(test_array)assert test_array == [1, 2, 3, 4]if __name__ == "__main__":array = [5, 6, -1, 4, 2, 8, 10, 7, 6]bubble_sort(array)print(array)array = [5, 6, -1, 4, 2, 8, 10, 7, 6]insertion_sort(array)print(array)array = [5, 6, -1, 4, 2, 8, 10, 7, 6]selection_sort(array)print(array)

當(dāng)然，還有其它編程語言的代碼實(shí)現(xiàn)，這里就不一一列舉了！

目前，這份資源已經(jīng)在 GitHub 上收獲了 6000 星了。是一份不錯的數(shù)據(jù)結(jié)構(gòu)與算法參考代碼。值得一看。最后再附上地址：

https://github.com/wangzheng0822/algo

---

推薦閱讀

（點(diǎn)擊標(biāo)題可跳轉(zhuǎn)閱讀）

完備的 AI 學(xué)習(xí)路線，最詳細(xì)的資源整理！

干貨 | 公眾號歷史文章精選

我的深度學(xué)習(xí)入門路線

我的機(jī)器學(xué)習(xí)入門路線圖

覺得這篇文章有幫助？請轉(zhuǎn)發(fā)給更多人

關(guān)注?AI有道?加星標(biāo)，獲取最新 AI 干貨

最新 AI 干貨，我在看??

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法必备的 50 个代码实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。