超級無敵干貨,第一時間送達?。?!
常見的數(shù)據(jù)結(jié)構(gòu)鏈表、隊列、棧、二叉樹、堆
使用內(nèi)置的結(jié)構(gòu)實現(xiàn)高級數(shù)據(jù)結(jié)構(gòu),比如內(nèi)置的list/deque實現(xiàn)棧
LeetCode或者劍指Offer上的常考題,本文將給出示例。
鏈表有單鏈表、雙鏈表、循環(huán)雙端鏈表
如何使用Python來表示鏈表結(jié)構(gòu)
實現(xiàn)鏈表常見操作,比如插入節(jié)點,反轉(zhuǎn)鏈表,合并多個鏈表等
LeetCode練習常見鏈表題目,如翻轉(zhuǎn)鏈表,如下所示:
合并兩個有序鏈表
隊列(queue)是先進先出結(jié)構(gòu)
如何使用Python實現(xiàn)隊列?
實現(xiàn)隊列的append和pop操作,如何做到先進先出
使用collections.deque實現(xiàn)隊列
棧(stack)是先進后出結(jié)構(gòu)
如何使用Python實現(xiàn)棧?
實現(xiàn)棧的push和pop操作,如何做到先進后出
使用collections.deque實現(xiàn)隊列
Python dict/set底層都是哈希表
哈希表的實現(xiàn)原理,底層其實就是一個數(shù)組
根據(jù)哈希函數(shù)快速定位一個元素,平均查找O(1)
不斷加入元素會引起哈希表重新開辟空間,拷貝之前的元素到新數(shù)組
哈希表如何解決沖突
鏈接法:元素key沖突之后使用一個鏈表填充相同key的元素
開放尋址法:沖突之后根據(jù)一種方式(二次探查)尋找下一個可用的槽
cpython使用的二次探查
先序、中序、后序
先序 根左右
中序 左根右
后序 左右根
堆其實是完全二叉樹,有最大堆和最小堆
最大堆:對于每個非葉子節(jié)點V,V的值都比它的兩個孩子大
最小堆:對于每個非葉子節(jié)點V,V的值都比它的兩個孩子小
最大堆支持每次pop操作獲取最大的元素,最小堆獲取最小元素
常見問題:用堆完成topK問題,從海量數(shù)字中尋找最大的K個
??寂判蛩惴ǎ好芭菖判?、快速排序、歸并排序、堆排序
線性查找,二分查找
能獨立實現(xiàn)代碼(手寫),能夠分析時間空間復雜度
常見排序算法的時空復雜度
相同大小的元素在排序之后依然保持相對位置不變,就是穩(wěn)定的
r[i]=r[j]且r[i]在r[j]之前,排序之后r[i]依然在r[j]之前
穩(wěn)定性對于排序一個復雜結(jié)構(gòu),并且需要保持原有排序才有意義
要求m+n復雜度內(nèi)
聯(lián)系客服