1.時(shí)間復(fù)雜度問題

已知 AList = [1, 2, 3]，BSet = {1, 2, 3} (1)從AList和BSet中查找4，最壞時(shí)間復(fù)雜度哪個(gè)大？(2)從AList和BSet中插入4，最壞時(shí)間復(fù)雜度哪個(gè)大？

答:

對(duì)于查找，列表和集合的最壞時(shí)間復(fù)雜度都是O(n)，所以一樣的。

列表操作插入的最壞時(shí)間復(fù)雜度為o(n), 集合為o(1)，所以Alist大。set是哈希表所以操作的復(fù)雜度基本上都是o(1)。

2. 用 Python 實(shí)現(xiàn)一個(gè)二分查找的函數(shù)

答:

3. Python 單例模式的實(shí)現(xiàn)方法
答:

實(shí)現(xiàn)單例模式的方法有多種，之前再說(shuō)元類的時(shí)候用 call 方法實(shí)現(xiàn)了一個(gè)單例模式，另外 Python 的模塊就是一個(gè)天然的單例模式，這里我們使用 new 關(guān)鍵字來(lái)實(shí)現(xiàn)一個(gè)單例模式。

通過 new 函數(shù)實(shí)現(xiàn)簡(jiǎn)單的單例模式。

4. 使用 Python 實(shí)現(xiàn)一個(gè)斐波那契數(shù)列
答:

斐波那契數(shù)列:數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。

5. 找出列表中的重復(fù)數(shù)字
答:

思路：從頭掃到尾，只要當(dāng)前元素值與下標(biāo)不同，就做一次判斷，numbers[i] 與 numbers[numbers[i]] 相等就認(rèn)為找到了重復(fù)元素，返回 true；否則就交換兩者，繼續(xù)循環(huán)。直到最后還沒找到認(rèn)為沒找到重復(fù)元素。

6. 找出列表中的單個(gè)數(shù)字
答:

7. 寫一個(gè)冒泡排序
答:

8. 寫一個(gè)快速排序
答:

9. 寫一個(gè)拓?fù)渑判?br>答:

對(duì)應(yīng)于該圖的拓?fù)渑判?。每一個(gè)有向無(wú)環(huán)圖都至少存在一種拓?fù)渑判颉?/p>

10. Python 實(shí)現(xiàn)一個(gè)二進(jìn)制計(jì)算
答:

二進(jìn)制加法

更多 Python 編程常見面試題，我們后續(xù)繼續(xù)分享，敬請(qǐng)關(guān)注。