超級(jí)無敵干貨，第一時(shí)間送達(dá)?。?！

本文將對Python web后端面試時(shí)?？紨?shù)據(jù)結(jié)構(gòu)與算法進(jìn)行總結(jié)，適合即將找工作或面試的你。Python web后端?？紨?shù)據(jù)結(jié)構(gòu)包括:

• 常見的數(shù)據(jù)結(jié)構(gòu)鏈表、隊(duì)列、棧、二叉樹、堆

• 使用內(nèi)置的結(jié)構(gòu)實(shí)現(xiàn)高級(jí)數(shù)據(jù)結(jié)構(gòu)，比如內(nèi)置的list/deque實(shí)現(xiàn)棧

• LeetCode或者劍指Offer上的?？碱}，本文將給出示例。

鏈表

鏈表有單鏈表、雙鏈表、循環(huán)雙端鏈表

• 如何使用Python來表示鏈表結(jié)構(gòu)

• 實(shí)現(xiàn)鏈表常見操作，比如插入節(jié)點(diǎn)，反轉(zhuǎn)鏈表，合并多個(gè)鏈表等

• LeetCode練習(xí)常見鏈表題目，如翻轉(zhuǎn)鏈表，如下所示：

合并兩個(gè)有序鏈表

隊(duì)列

隊(duì)列（queue）是先進(jìn)先出結(jié)構(gòu)

• 如何使用Python實(shí)現(xiàn)隊(duì)列？

• 實(shí)現(xiàn)隊(duì)列的append和pop操作，如何做到先進(jìn)先出

• 使用collections.deque實(shí)現(xiàn)隊(duì)列

棧

棧（stack）是先進(jìn)后出結(jié)構(gòu)

• 如何使用Python實(shí)現(xiàn)棧？

• 實(shí)現(xiàn)棧的push和pop操作，如何做到先進(jìn)后出

• 使用collections.deque實(shí)現(xiàn)隊(duì)列

字典與集合

Python dict/set底層都是哈希表

• 哈希表的實(shí)現(xiàn)原理，底層其實(shí)就是一個(gè)數(shù)組

• 根據(jù)哈希函數(shù)快速定位一個(gè)元素，平均查找O(1)

• 不斷加入元素會(huì)引起哈希表重新開辟空間，拷貝之前的元素到新數(shù)組

哈希表如何解決沖突

• 鏈接法：元素key沖突之后使用一個(gè)鏈表填充相同key的元素

• 開放尋址法：沖突之后根據(jù)一種方式(二次探查)尋找下一個(gè)可用的槽

• cpython使用的二次探查

二叉樹

先序、中序、后序

• 先序 根左右

• 中序 左根右

• 后序 左右根

堆

堆其實(shí)是完全二叉樹，有最大堆和最小堆

• 最大堆：對于每個(gè)非葉子節(jié)點(diǎn)V，V的值都比它的兩個(gè)孩子大

• 最小堆：對于每個(gè)非葉子節(jié)點(diǎn)V，V的值都比它的兩個(gè)孩子小

• 最大堆支持每次pop操作獲取最大的元素，最小堆獲取最小元素

• 常見問題：用堆完成topK問題，從海量數(shù)字中尋找最大的K個(gè)

Python?？妓惴?/strong>

排序+查找，重中之重

• ?？寂判蛩惴ǎ好芭菖判颉⒖焖倥判?、歸并排序、堆排序

• 線性查找，二分查找

• 能獨(dú)立實(shí)現(xiàn)代碼（手寫），能夠分析時(shí)間空間復(fù)雜度

常見排序算法的時(shí)空復(fù)雜度

排序算法的穩(wěn)定性

• 相同大小的元素在排序之后依然保持相對位置不變，就是穩(wěn)定的

• r[i]=r[j]且r[i]在r[j]之前，排序之后r[i]依然在r[j]之前

• 穩(wěn)定性對于排序一個(gè)復(fù)雜結(jié)構(gòu)，并且需要保持原有排序才有意義

快速排序

快速排序經(jīng)常問分治法(divide and conquer)，快排三步走:

• Partition：選擇基準(zhǔn)分割數(shù)組為兩個(gè)子數(shù)組，小于基準(zhǔn)和大于基準(zhǔn)的

• 對兩個(gè)子數(shù)組分別快排

• 合并結(jié)果

合并兩個(gè)有序數(shù)組

• 要求m+n復(fù)雜度內(nèi)

歸并排序

堆排序

二分查找