目錄Python進(jìn)階教程算法與數(shù)據(jù)結(jié)構(gòu)入門一、時間復(fù)雜度二、常用數(shù)據(jù)結(jié)構(gòu)2.1 列表與字典2.2 棧Stack2.3 隊(duì)列Queue三、排序算法3.1 冒泡排序O(n2)3.2 快速排序O(n log n)四、查找算法五、遞歸六、動態(tài)規(guī)劃入門七、實(shí)戰(zhàn)實(shí)現(xiàn) LRU 緩存總結(jié)Python進(jìn)階教程算法與數(shù)據(jù)結(jié)構(gòu)入門本文是Python 入門教程系列的第 18 篇擴(kuò)展篇。算法與數(shù)據(jù)結(jié)構(gòu)是編程的內(nèi)功本篇介紹最核心的幾種用 Python 實(shí)現(xiàn)。一、時間復(fù)雜度衡量算法效率用大 O 表示法描述執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的速度復(fù)雜度含義示例O(1)常數(shù)時間數(shù)組按下標(biāo)訪問O(log n)對數(shù)時間二分查找O(n)線性時間遍歷列表O(n log n)線性對數(shù)快速排序O(n2)平方時間冒泡排序二、常用數(shù)據(jù)結(jié)構(gòu)2.1 列表與字典# 列表有序、可重復(fù)fruits[蘋果,香蕉,橙子]fruits.append(葡萄)print(fruits[0],len(fruits))# 字典鍵值對、查找 O(1)scores{張三:90,李四:85}print(scores[張三])print(scores.get(王五,不存在))2.2 棧Stack# 棧后進(jìn)先出LIFO用列表實(shí)現(xiàn)stack[]stack.append(1)# 入棧stack.append(2)stack.append(3)print(stack.pop())# 3 出棧print(stack[-1])# 2 查看棧頂print(len(stack)0)# 判斷是否為空2.3 隊(duì)列Queuefromcollectionsimportdeque# 隊(duì)列先進(jìn)先出FIFOqueuedeque([a,b,c])queue.append(d)# 入隊(duì)print(queue.popleft())# a 出隊(duì)print(queue)# deque([b, c, d])三、排序算法3.1 冒泡排序O(n2)defbubble_sort(arr):nlen(arr)foriinrange(n-1):forjinrange(n-1-i):ifarr[j]arr[j1]:arr[j],arr[j1]arr[j1],arr[j]returnarrprint(bubble_sort([5,2,8,1,9]))# [1, 2, 5, 8, 9]3.2 快速排序O(n log n)defquick_sort(arr):iflen(arr)1:returnarr pivotarr[len(arr)//2]left[xforxinarrifxpivot]mid[xforxinarrifxpivot]right[xforxinarrifxpivot]returnquick_sort(left)midquick_sort(right)print(quick_sort([5,2,8,1,9]))# [1, 2, 5, 8, 9]四、查找算法# 二分查找要求有序O(log n)defbinary_search(arr,target):left,right0,len(arr)-1whileleftright:mid(leftright)//2ifarr[mid]target:returnmidelifarr[mid]target:leftmid1else:rightmid-1return-1nums[1,3,5,7,9,11]print(binary_search(nums,7))# 3print(binary_search(nums,8))# -1五、遞歸# 遞歸函數(shù)調(diào)用自身deffactorial(n):ifn1:return1returnn*factorial(n-1)print(factorial(5))# 120# 斐波那契帶緩存避免重復(fù)計(jì)算fromfunctoolsimportlru_cachelru_cache(maxsizeNone)deffib(n):ifn2:returnnreturnfib(n-1)fib(n-2)print(fib(50))# 12586269025六、動態(tài)規(guī)劃入門# 經(jīng)典問題爬樓梯每次 1 或 2 階defclimb_stairs(n):ifn2:returnn dp[0]*(n1)dp[1],dp[2]1,2foriinrange(3,n1):dp[i]dp[i-1]dp[i-2]returndp[n]print(climb_stairs(10))# 89七、實(shí)戰(zhàn)實(shí)現(xiàn) LRU 緩存fromcollectionsimportOrderedDictclassLRUCache:最近最少使用緩存def__init__(self,capacity):self.cacheOrderedDict()self.capacitycapacitydefget(self,key):ifkeynotinself.cache:return-1self.cache.move_to_end(key)# 標(biāo)記為最近使用returnself.cache[key]defput(self,key,value):ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]valueiflen(self.cache)self.capacity:self.cache.popitem(lastFalse)# 淘汰最久未用cacheLRUCache(2)cache.put(1,A)cache.put(2,B)print(cache.get(1))# Acache.put(3,C)# 淘汰 key2print(cache.get(2))# -1print(cache.get(3))# C總結(jié)本篇介紹了時間復(fù)雜度、常用數(shù)據(jù)結(jié)構(gòu)棧、隊(duì)列、排序與查找算法、遞歸和動態(tài)規(guī)劃入門并用 LRU 緩存串聯(lián)實(shí)戰(zhàn)。刷題建議從 LeetCode 簡單題開始每天 1-2 題堅(jiān)持就是勝利。