算法培訓(xùn)課件：系統(tǒng)掌握數(shù)據(jù)結(jié)構(gòu)與算法核心第一章算法與數(shù)據(jù)結(jié)構(gòu)導(dǎo)論課程核心內(nèi)容算法的定義與重要性算法復(fù)雜度分析方法時(shí)間復(fù)雜度與空間復(fù)雜度Python語言優(yōu)勢(shì)及應(yīng)用算法復(fù)雜度基礎(chǔ)大O符號(hào)表示法用于描述算法的漸進(jìn)時(shí)間復(fù)雜度,關(guān)注輸入規(guī)模增長(zhǎng)時(shí)的性能變化趨勢(shì)O(1)-常數(shù)時(shí)間O(logn)-對(duì)數(shù)時(shí)間O(n)-線性時(shí)間O(n2)-平方時(shí)間遞歸關(guān)系分析通過遞推關(guān)系式求解復(fù)雜度,常用主定理和遞歸樹方法遞歸樹可視化分析主定理應(yīng)用場(chǎng)景分治算法復(fù)雜度經(jīng)典對(duì)比案例斐波那契數(shù)列的兩種實(shí)現(xiàn)方式遞歸版本:O(2?)指數(shù)級(jí)動(dòng)態(tài)規(guī)劃:O(n)線性級(jí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)概念數(shù)據(jù)結(jié)構(gòu)是組織和存儲(chǔ)數(shù)據(jù)的方式,不同的數(shù)據(jù)結(jié)構(gòu)適用于不同的場(chǎng)景。理解數(shù)據(jù)結(jié)構(gòu)的本質(zhì),能幫助我們?cè)趯?shí)際開發(fā)中做出最優(yōu)選擇。抽象數(shù)據(jù)類型ADT定義了數(shù)據(jù)的邏輯結(jié)構(gòu)和操作接口,隱藏了具體實(shí)現(xiàn)細(xì)節(jié),是面向?qū)ο笤O(shè)計(jì)的基礎(chǔ)線性結(jié)構(gòu)元素之間存在一對(duì)一關(guān)系,如數(shù)組、鏈表、棧、隊(duì)列等,數(shù)據(jù)按順序排列非線性結(jié)構(gòu)元素之間存在一對(duì)多或多對(duì)多關(guān)系,如樹、圖等,結(jié)構(gòu)更復(fù)雜但表達(dá)能力更強(qiáng)Python內(nèi)置結(jié)構(gòu)數(shù)組與鏈表數(shù)組的特點(diǎn)數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu),元素在內(nèi)存中連續(xù)存儲(chǔ),支持O(1)時(shí)間的隨機(jī)訪問。但插入和刪除操作需要移動(dòng)元素,時(shí)間復(fù)雜度為O(n)。鏈表的優(yōu)勢(shì)鏈表通過指針連接節(jié)點(diǎn),插入和刪除只需修改指針,時(shí)間復(fù)雜度O(1)。但訪問元素需要從頭遍歷,時(shí)間復(fù)雜度O(n)。單鏈表:每個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)雙鏈表:節(jié)點(diǎn)同時(shí)指向前后節(jié)點(diǎn),可雙向遍歷循環(huán)鏈表:尾節(jié)點(diǎn)指向頭節(jié)點(diǎn),形成環(huán)狀代碼演示:鏈表插入操作棧與隊(duì)列1棧(Stack)后進(jìn)先出(LIFO)的線性數(shù)據(jù)結(jié)構(gòu),像一摞盤子,只能從頂部添加或移除元素。典型應(yīng)用場(chǎng)景:括號(hào)匹配檢查函數(shù)調(diào)用棧表達(dá)式求值瀏覽器歷史記錄2隊(duì)列(Queue)先進(jìn)先出(FIFO)的線性數(shù)據(jù)結(jié)構(gòu),像排隊(duì)買票,從隊(duì)尾加入,從隊(duì)首離開。典型應(yīng)用場(chǎng)景:任務(wù)調(diào)度系統(tǒng)廣度優(yōu)先搜索消息隊(duì)列打印任務(wù)管理3雙端隊(duì)列(Deque)兩端都可以進(jìn)行插入和刪除操作的隊(duì)列,結(jié)合了棧和隊(duì)列的特點(diǎn),應(yīng)用更靈活。Python實(shí)現(xiàn):fromcollectionsimportdequedq=deque([1,2,3])dq.append(4)#右端添加dq.appendleft(0)#左端添加哈希表與散列沖突解決哈希表是實(shí)現(xiàn)快速查找的關(guān)鍵數(shù)據(jù)結(jié)構(gòu),通過哈希函數(shù)將鍵映射到數(shù)組索引,實(shí)現(xiàn)O(1)平均時(shí)間復(fù)雜度的查找、插入和刪除操作。哈希函數(shù)將任意大小的輸入數(shù)據(jù)轉(zhuǎn)換為固定大小的輸出值,決定了元素在表中的存儲(chǔ)位置散列沖突不同的鍵經(jīng)過哈希函數(shù)后得到相同的索引值,這是不可避免的現(xiàn)象鏈地址法在每個(gè)數(shù)組位置維護(hù)一個(gè)鏈表,沖突的元素添加到對(duì)應(yīng)鏈表中開放地址法當(dāng)發(fā)生沖突時(shí),按某種規(guī)則尋找下一個(gè)空閑位置進(jìn)行存儲(chǔ)Python字典底層實(shí)現(xiàn)Python的dict使用哈希表實(shí)現(xiàn),采用開放地址法解決沖突。字典的鍵必須是可哈希的不可變對(duì)象,如字符串、數(shù)字、元組等。字典在Python3.6+保持插入順序。面試典型題目?jī)蓴?shù)之和(TwoSum)字符串中第一個(gè)不重復(fù)的字符最長(zhǎng)連續(xù)序列LRU緩存機(jī)制實(shí)現(xiàn)字符串基礎(chǔ)與匹配算法字符串操作基礎(chǔ)字符串是最常見的數(shù)據(jù)類型之一,Python提供了豐富的字符串操作方法。字符串是不可變對(duì)象,任何修改都會(huì)創(chuàng)建新字符串。切片操作:s[start:end:step]拼接與重復(fù):+和*常用方法:split,join,replace格式化:f-string,format字符串匹配算法樸素匹配算法逐個(gè)字符比對(duì),時(shí)間復(fù)雜度O(m×n),簡(jiǎn)單但效率低。KMP算法核心思想利用已匹配的信息,避免重復(fù)比較。通過next數(shù)組記錄模式串的前綴信息,失配時(shí)跳轉(zhuǎn)而非從頭開始。時(shí)間復(fù)雜度O(m+n)。KMP算法代碼演示defget_next(pattern):next_arr=[0]*len(pattern)j=0foriinrange(1,len(pattern)):whilej>0andpattern[i]!=pattern[j]:j=next_arr[j-1]ifpattern[i]==pattern[j]:j+=1next_arr[i]=jreturnnext_arr排序算法基礎(chǔ)排序是計(jì)算機(jī)科學(xué)中最基本的操作之一。理解各種排序算法的原理和特點(diǎn),是算法學(xué)習(xí)的重要基礎(chǔ)。冒泡排序重復(fù)遍歷數(shù)組,比較相鄰元素并交換,大元素逐漸"冒泡"到末尾時(shí)間復(fù)雜度:O(n2)穩(wěn)定性:穩(wěn)定選擇排序每次從未排序部分選擇最小元素,放到已排序部分末尾時(shí)間復(fù)雜度:O(n2)穩(wěn)定性:不穩(wěn)定插入排序?qū)⒃刂饌€(gè)插入到已排序序列的正確位置,類似整理撲克牌時(shí)間復(fù)雜度:O(n2)穩(wěn)定性:穩(wěn)定基礎(chǔ)排序算法雖然效率不高,但實(shí)現(xiàn)簡(jiǎn)單,適合小規(guī)模數(shù)據(jù)。插入排序?qū)τ诮跤行虻臄?shù)據(jù)表現(xiàn)優(yōu)異,在實(shí)際應(yīng)用中有其價(jià)值。高級(jí)排序算法01歸并排序(MergeSort)采用分治策略,將數(shù)組遞歸分解為小數(shù)組,排序后再合并。時(shí)間復(fù)雜度O(nlogn),空間復(fù)雜度O(n),是穩(wěn)定排序算法的代表。02快速排序(QuickSort)選擇基準(zhǔn)元素,將數(shù)組劃分為小于和大于基準(zhǔn)的兩部分,遞歸排序。平均時(shí)間復(fù)雜度O(nlogn),最壞O(n2),是實(shí)踐中最常用的排序算法。03堆排序(HeapSort)利用堆這種數(shù)據(jù)結(jié)構(gòu),先建立最大堆,然后依次取出堆頂元素。時(shí)間復(fù)雜度O(nlogn),空間復(fù)雜度O(1),不穩(wěn)定但原地排序?？焖倥判虼a實(shí)現(xiàn)defquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)歸并排序代碼實(shí)現(xiàn)defmerge_sort(arr):iflen(arr)<=1:returnarrmid=len(arr)//2left=merge_sort(arr[:mid])right=merge_sort(arr[mid:])returnmerge(left,right)樹的基礎(chǔ)知識(shí)樹是一種非線性的層次結(jié)構(gòu),由節(jié)點(diǎn)和邊組成。樹的每個(gè)節(jié)點(diǎn)可以有零個(gè)或多個(gè)子節(jié)點(diǎn),除根節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都有唯一的父節(jié)點(diǎn)。二叉樹定義每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)的樹結(jié)構(gòu),分為左子樹和右子樹。二叉樹是最重要的樹形結(jié)構(gòu)。遍歷方法前序(根-左-右)、中序(左-根-右)、后序(左-右-根)、層序(逐層訪問)二叉搜索樹左子樹所有節(jié)點(diǎn)小于根節(jié)點(diǎn),右子樹所有節(jié)點(diǎn)大于根節(jié)點(diǎn),支持高效的查找、插入、刪除操作。二叉樹遍歷代碼示例classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorder_traversal(root):ifnotroot:return[]returninorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)堆與優(yōu)先級(jí)隊(duì)列堆的定義與性質(zhì)堆是一種特殊的完全二叉樹,滿足堆性質(zhì):最大堆:父節(jié)點(diǎn)的值大于或等于子節(jié)點(diǎn)最小堆:父節(jié)點(diǎn)的值小于或等于子節(jié)點(diǎn)堆通常用數(shù)組實(shí)現(xiàn),對(duì)于索引i的節(jié)點(diǎn):左子節(jié)點(diǎn):2i+1右子節(jié)點(diǎn):2i+2父節(jié)點(diǎn):(i-1)//2優(yōu)先級(jí)隊(duì)列基于堆實(shí)現(xiàn),每次取出優(yōu)先級(jí)最高(或最低)的元素,應(yīng)用于任務(wù)調(diào)度、事件驅(qū)動(dòng)系統(tǒng)等場(chǎng)景核心操作插入O(logn)、刪除最值O(logn)、獲取最值O(1)、堆化O(n)應(yīng)用場(chǎng)景TopK問題、堆排序、中位數(shù)維護(hù)、Dijkstra最短路徑算法Pythonheapq模塊使用importheapq#創(chuàng)建最小堆heap=[]heapq.heappush(heap,3)heapq.heappush(heap,1)heapq.heappush(heap,5)#彈出最小元素min_val=heapq.heappop(heap)#返回1#獲取最大的3個(gè)元素largest=heapq.nlargest(3,[1,5,2,8,3])圖論基礎(chǔ)圖是由節(jié)點(diǎn)(頂點(diǎn))和邊組成的數(shù)據(jù)結(jié)構(gòu),用于表示事物之間的關(guān)系。圖可以是有向或無向的,帶權(quán)或不帶權(quán)的。鄰接矩陣使用二維數(shù)組表示圖,matrix[i][j]表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊。優(yōu)點(diǎn)是查詢邊的存在快速O(1),缺點(diǎn)是空間復(fù)雜度O(V2),適合稠密圖。graph=[[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]鄰接表使用字典或列表存儲(chǔ)每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)?？臻g復(fù)雜度O(V+E),適合稀疏圖,是實(shí)際應(yīng)用中最常用的表示方法。graph={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C']}深度優(yōu)先搜索(DFS)沿著一條路徑盡可能深入探索,直到無法繼續(xù)時(shí)回溯。使用棧(或遞歸)實(shí)現(xiàn),適合路徑問題、連通性檢測(cè)。廣度優(yōu)先搜索(BFS)逐層訪問節(jié)點(diǎn),先訪問距離起點(diǎn)近的節(jié)點(diǎn)。使用隊(duì)列實(shí)現(xiàn),適合最短路徑、層次遍歷問題?；A(chǔ)算法設(shè)計(jì)思想枚舉法窮舉所有可能的解,從中找出滿足條件的答案。簡(jiǎn)單直接但效率較低,適合規(guī)模較小的問題。遞歸策略將問題分解為規(guī)模更小的相同問題,通過解決子問題來解決原問題。注意遞歸終止條件和棧溢出風(fēng)險(xiǎn)。分治思想將問題分解為若干獨(dú)立的子問題,遞歸求解后合并結(jié)果。典型應(yīng)用:歸并排序、快速排序、二分查找。貪心算法每步都做出當(dāng)前看來最優(yōu)的選擇,希望最終得到全局最優(yōu)解。不是所有問題都適用,需要證明貪心選擇性質(zhì)。這四種思想是算法設(shè)計(jì)的基石。枚舉是最樸素的方法,遞歸提供了優(yōu)雅的表達(dá)方式,分治將復(fù)雜問題簡(jiǎn)化,貪心則在特定條件下提供高效解法。貪心算法經(jīng)典題目活動(dòng)選擇問題:選擇最多不沖突的活動(dòng)霍夫曼編碼:構(gòu)造最優(yōu)前綴編碼最小生成樹:Prim算法和Kruskal算法找零錢問題:用最少硬幣數(shù)找零動(dòng)態(tài)規(guī)劃入門動(dòng)態(tài)規(guī)劃(DP)是解決最優(yōu)化問題的強(qiáng)大工具,通過保存子問題的解避免重復(fù)計(jì)算。核心思想是將問題分解為重疊的子問題,自底向上或自頂向下求解。識(shí)別DP問題問題具有最優(yōu)子結(jié)構(gòu)和重疊子問題性質(zhì)定義狀態(tài)確定用什么變量表示子問題,通常用dp數(shù)組狀態(tài)轉(zhuǎn)移方程找出當(dāng)前狀態(tài)與子狀態(tài)的關(guān)系,這是DP的核心初始化與邊界設(shè)置基礎(chǔ)情況的值,確定計(jì)算順序計(jì)算結(jié)果按照轉(zhuǎn)移方程填充dp數(shù)組,得到最終答案經(jīng)典問題:爬樓梯每次可以爬1級(jí)或2級(jí)臺(tái)階,問爬到第n級(jí)有多少種方法?狀態(tài)定義:dp[i]表示爬到第i級(jí)的方法數(shù)狀態(tài)轉(zhuǎn)移:dp[i]=dp[i-1]+dp[i-2]defclimb_stairs(n):ifn<=2:returnndp=[0]*(n+1)dp[1],dp[2]=1,2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]經(jīng)典問題:0-1背包有n個(gè)物品和容量為W的背包,第i個(gè)物品重量wi、價(jià)值vi,求最大價(jià)值。狀態(tài)定義:dp[i][w]表示前i個(gè)物品、容量w時(shí)的最大價(jià)值狀態(tài)轉(zhuǎn)移:dp[i][w]=max(dp[i-1][w],#不選第i個(gè)dp[i-1][w-wi]+vi#選第i個(gè))回溯算法回溯是一種通過探索所有可能的候選解來找出所有解的算法。如果候選解不符合要求,就回退到上一步繼續(xù)嘗試其他選擇?；厮荼举|(zhì)上是深度優(yōu)先搜索的應(yīng)用。選擇在當(dāng)前狀態(tài)下,列出所有可能的選擇路徑約束判斷選擇是否滿足問題的約束條件目標(biāo)判斷是否達(dá)到問題的目標(biāo)狀態(tài)回溯撤銷上一步的選擇,嘗試其他路徑八皇后問題在8×8棋盤上放置8個(gè)皇后,使得任意兩個(gè)皇后都不在同一行、同一列或同一對(duì)角線上。回溯解法思路逐行放置皇后對(duì)于每一行,嘗試每一列檢查當(dāng)前位置是否與已放置的皇后沖突如果不沖突,放置皇后并遞歸處理下一行如果沖突或后續(xù)無解,回溯到上一行嘗試其他位置八皇后代碼實(shí)現(xiàn)defsolve_n_queens(n):defbacktrack(row,cols,diag1,diag2):ifrow==n:result.append(cols[:])returnforcolinrange(n):d1,d2=row-col,row+colifcolincolsord1indiag1ord2indiag2:continuecols.add(col)diag1.add(d1)diag2.add(d2)backtrack(row+1,cols,diag1,diag2)cols.remove(col)diag1.remove(d1)diag2.remove(d2)

result=[]backtrack(0,set(),set(),set())returnresult剪枝優(yōu)化技巧剪枝是提高回溯算法效率的關(guān)鍵。通過提前判斷某條路徑不可能產(chǎn)生解,避免繼續(xù)探索,大幅減少搜索空間。常見的剪枝策略包括可行性剪枝、最優(yōu)性剪枝和記憶化剪枝。算法設(shè)計(jì)進(jìn)階隨機(jī)算法利用隨機(jī)性來解決問題或提高算法效率。蒙特卡羅算法給出近似解,拉斯維加斯算法給出精確解但運(yùn)行時(shí)間隨機(jī)。典型應(yīng)用包括快速排序的隨機(jī)化、隨機(jī)采樣、概率驗(yàn)證等。復(fù)雜度理論初步P類問題:能在多項(xiàng)式時(shí)間內(nèi)求解的問題NP類問題:解可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的問題NP完全問題:最難的NP問題,如旅行商問題、圖著色問題。如果任何一個(gè)NP完全問題有多項(xiàng)式解,則所有NP問題都有。算法正確性證明循環(huán)不變式:用于證明循環(huán)算法的正確性,需證明初始化、保持、終止三個(gè)性質(zhì)數(shù)學(xué)歸納法:證明遞歸算法的常用方法,先證基礎(chǔ)情況,再證遞推關(guān)系反證法:假設(shè)算法錯(cuò)誤,推導(dǎo)出矛盾,從而證明算法正確Python工程實(shí)踐中的算法應(yīng)用Python提供了豐富的標(biāo)準(zhǔn)庫,充分利用這些工具可以大幅提升開發(fā)效率。理解內(nèi)置數(shù)據(jù)結(jié)構(gòu)和算法模塊的實(shí)現(xiàn)原理,能幫助我們做出更好的技術(shù)選擇。collections模塊deque:雙端隊(duì)列,支持O(1)的兩端操作Counter:計(jì)數(shù)器,快速統(tǒng)計(jì)元素頻率defaultdict:帶默認(rèn)值的字典OrderedDict:保持插入順序的字典namedtuple:具名元組,提高代碼可讀性heapq模塊實(shí)現(xiàn)最小堆功能heappush/heappop操作nlargest/nsmallest查找merge合并有序序列適用于優(yōu)先隊(duì)列、TopK問題bisect模塊二分查找算法insort維護(hù)有序列表bisect_left/right查找插入位置O(logn)時(shí)間復(fù)雜度適用于有序數(shù)據(jù)操作實(shí)際業(yè)務(wù)場(chǎng)景示例場(chǎng)景一:日志分析使用Counter統(tǒng)計(jì)關(guān)鍵詞頻率,heapq獲取Top10高頻詞,時(shí)間復(fù)雜度O(nlogk)。場(chǎng)景二:緩存系統(tǒng)使用OrderedDict實(shí)現(xiàn)LRU緩存,O(1)時(shí)間訪問和更新。代碼優(yōu)化示例fromcollectionsimportCounterimportheapq#高效統(tǒng)計(jì)TopKdeftop_k_frequent(words,k):count=Counter(words)returnheapq.nlargest(k,count.items(),key=lambdax:x[1])#使用bisect維護(hù)有序列表importbisectsorted_list=[1,3,5,7,9]bisect.insort(sorted_list,4)#[1,3,4,5,7,9]面試高頻算法題解析(一)數(shù)組與鏈表專題兩數(shù)之和(TwoSum)題目:給定數(shù)組和目標(biāo)值,找出兩個(gè)數(shù)使其和等于目標(biāo)值思路:使用哈希表存儲(chǔ)已遍歷的數(shù)字和索引,O(n)時(shí)間解決deftwo_sum(nums,target):seen={}fori,numinenumerate(nums):complement=target-numifcomplementinseen:return[seen[complement],i]seen[num]=i時(shí)間復(fù)雜度:O(n)|空間復(fù)雜度:O(n)反轉(zhuǎn)鏈表題目:反轉(zhuǎn)一個(gè)單向鏈表思路:迭代或遞歸,改變指針方向。迭代法使用三個(gè)指針prev,curr,nextdefreverse_list(head):prev=Nonecurr=headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev時(shí)間復(fù)雜度:O(n)|空間復(fù)雜度:O(1)合并兩個(gè)有序數(shù)組題目:將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組思路:從后向前填充,避免覆蓋未處理的元素,充分利用已有空間時(shí)間復(fù)雜度:O(m+n)|空間復(fù)雜度:O(1)解題技巧總結(jié):數(shù)組問題常用雙指針、滑動(dòng)窗口、哈希表;鏈表問題注意邊界條件、善用快慢指針、虛擬頭節(jié)點(diǎn)技巧。時(shí)刻思考時(shí)間和空間復(fù)雜度的權(quán)衡。面試高頻算法題解析(二)棧、隊(duì)列與哈希表專題1有效的括號(hào)使用棧匹配括號(hào)對(duì)。遇到左括號(hào)入棧,遇到右括號(hào)檢查棧頂是否匹配。最后檢查棧是否為空。2用隊(duì)列實(shí)現(xiàn)棧使用兩個(gè)隊(duì)列,或者一個(gè)隊(duì)列通過循環(huán)出入隊(duì)實(shí)現(xiàn)。關(guān)鍵是理解LIFO和FIFO的轉(zhuǎn)換。3LRU緩存機(jī)制結(jié)合哈希表和雙向鏈表。哈希表提供O(1)查找,雙向鏈表維護(hù)訪問順序,實(shí)現(xiàn)O(1)的get和put操作。4字母異位詞分組將每個(gè)字符串排序后作為鍵,原字符串作為值存入哈希表。排序后相同的字符串屬于同一組。LRU緩存代碼框架fromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity):self.cache=OrderedDict()self.capacity=capacity

defget(self,key):ifkeynotinself.cache:return-1self.cache.move_to_end(key)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(last=False)常見陷阱棧問題:忘記檢查棧是否為空隊(duì)列問題:循環(huán)隊(duì)列的索引計(jì)算錯(cuò)誤哈希表:沒有處理鍵不存在的情況邊界條件:空輸入、單元素等特殊情況應(yīng)對(duì)策略:先在紙上畫出數(shù)據(jù)結(jié)構(gòu)的變化過程,理清思路后再寫代碼。編寫完成后用簡(jiǎn)單示例手動(dòng)驗(yàn)證,特別注意邊界情況。面試高頻算法題解析(三)樹與圖專題1二叉樹的最大深度遞歸求解:max(左子樹深度,右子樹深度)+1。也可用層序遍歷計(jì)數(shù)層數(shù)。2驗(yàn)證二叉搜索樹中序遍歷結(jié)果應(yīng)嚴(yán)格遞增?；蜻f歸驗(yàn)證每個(gè)節(jié)點(diǎn)值在合法范圍內(nèi)。3二叉樹的層序遍歷使用隊(duì)列BFS實(shí)現(xiàn)。每次處理一層的所有節(jié)點(diǎn),記錄層數(shù)或?qū)觾?nèi)結(jié)果。4島嶼數(shù)量遍歷矩陣,遇到陸地時(shí)計(jì)數(shù)器加1,并用DFS/BFS標(biāo)記所有連通的陸地。5課程表(檢測(cè)環(huán))拓?fù)渑判蚧駾FS檢測(cè)有向圖中是否有環(huán)。維護(hù)訪問狀態(tài),發(fā)現(xiàn)回邊說明有環(huán)。島嶼數(shù)量代碼實(shí)現(xiàn)defnum_islands(grid):ifnotgrid:return0

defdfs(i,j):if(i<0ori>=len(grid)orj<0orj>=len(grid[0])orgrid[i][j]!='1'):returngrid[i][j]='0'#標(biāo)記為已訪問dfs(i+1,j)dfs(i-1,j)dfs(i,j+1)dfs(i,j-1)

count=0foriinrange(len(grid)):forjinrange(len(grid[0])):ifgrid[i][j]=='1':count+=1dfs(i,j)returncount思路總結(jié)樹問題關(guān)鍵點(diǎn):明確遞歸的定義和返回值處理空節(jié)點(diǎn)的邊界情況理解前中后序遍歷的應(yīng)用場(chǎng)景圖問題關(guān)鍵點(diǎn):選擇合適的圖表示方法防止重復(fù)訪問(標(biāo)記或集合)DFS用于路徑/環(huán)檢測(cè),BFS用于最短路徑面試高頻算法題解析(四)動(dòng)態(tài)規(guī)劃與回溯專題爬樓梯dp[i]=dp[i-1]+dp[i-2],經(jīng)典入門題打家劫舍不能搶相鄰房屋,dp[i]=max(dp[i-1],dp[i-2]+nums[i])0-1背包二維dp或空間優(yōu)化的一維dp,選或不選的決策零錢兌換完全背包變形,求最少硬幣數(shù)或方案數(shù)最長(zhǎng)遞增子序列O(n2)的dp或O(nlogn)的貪心+二分編輯距離字符串DP經(jīng)典題,三種操作的最小次數(shù)狀態(tài)設(shè)計(jì)技巧明確狀態(tài)含義:dp[i]或dp[i][j]代表什么找準(zhǔn)決策點(diǎn):每一步有哪些選擇寫出轉(zhuǎn)移方程:當(dāng)前狀態(tài)如何由子狀態(tài)得出確定邊界條件:初始狀態(tài)的值優(yōu)化空間復(fù)雜度:滾動(dòng)數(shù)組或狀態(tài)壓縮回溯題目精選全排列與組合子集問題電話號(hào)碼的字母組合N皇后問題單詞搜索性能優(yōu)化要點(diǎn)記憶化搜索:自頂向下,緩存已計(jì)算的結(jié)果狀態(tài)壓縮:用位運(yùn)算壓縮狀態(tài)空間剪枝優(yōu)化:回溯中提前終止無效分支滾動(dòng)數(shù)組:DP中只保留必要的前幾行狀態(tài)#最長(zhǎng)遞增子序列(貪心+二分,O(nlogn))deflength_of_lis(nums):tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)else:tails[left]=numreturnlen(tails)算法學(xué)習(xí)資源推薦經(jīng)典教材算法導(dǎo)論(CLRS):算法圣經(jīng),理論嚴(yán)謹(jǐn)算法(第4版):Sedgewick著,工程實(shí)踐導(dǎo)向算法圖解:圖文并茂,適合入門編程珠璣:問題解決思路和技巧在線刷題平臺(tái)LeetCode:海量題庫,分類詳細(xì),支持多語言?？途W(wǎng):國(guó)內(nèi)主流,模擬面試功能HackerRank:競(jìng)賽和認(rèn)證Codeforces:算法競(jìng)賽平臺(tái)可視化工具與社區(qū)VisuAlgo:算法動(dòng)畫演示,直觀易懂AlgorithmVisualizer:開源可視化項(xiàng)目GitHub:學(xué)習(xí)優(yōu)秀開源算法實(shí)現(xiàn)StackOverflow:問題討論社區(qū)視頻課程推薦MIT6.006算法導(dǎo)論普林斯頓算法課程(Coursera)GeeksforGeeks算法教程國(guó)內(nèi)各大平臺(tái)的算法專欄博客與公眾號(hào)labuladong的算法小抄代碼隨想錄五分鐘學(xué)算法LeetCode官方題解算法學(xué)習(xí)方法與技巧高效刷題策略按專題分類練習(xí),先易后難。每個(gè)專題練習(xí)20-30題形成肌肉記憶。不要貪多,重在理解和總結(jié)。定期復(fù)習(xí)已做過的題目,溫故知新。做題流程建議仔細(xì)審題,明確輸入輸出和約束條件思考暴力解法,分析時(shí)間空間復(fù)雜度尋找優(yōu)化方向,畫圖輔助思考編寫代碼前先寫清楚思路注釋實(shí)現(xiàn)代碼,注意邊界條件測(cè)試用例驗(yàn)證,特別是邊界情況總結(jié)題目類型和解題模板面試準(zhǔn)備策略提前3-6個(gè)月系統(tǒng)準(zhǔn)備。按公司常考題型分類練習(xí),多做模擬面試。準(zhǔn)備自我介紹和項(xiàng)目經(jīng)歷,能清晰表達(dá)技術(shù)方案。練習(xí)在白板或紙上寫代碼,鍛煉思維表達(dá)能力。編碼規(guī)范與測(cè)試變量命名有意義,代碼邏輯清晰。添加必要注釋說明思路。養(yǎng)成寫單元測(cè)試的習(xí)慣?？紤]異常輸入和邊界情況。代碼review和重構(gòu)提升代碼質(zhì)量。刷題建議時(shí)間分配思考時(shí)間:15-20分鐘,想不出來就看題解編碼時(shí)間:20-30分鐘,完成基本實(shí)現(xiàn)測(cè)試時(shí)間:10分鐘,驗(yàn)證邊界情況總結(jié)時(shí)間:10分鐘,記錄解題思路和模板一道題完整做下來約1小時(shí),重在質(zhì)量而非數(shù)量!課程總結(jié)與學(xué)習(xí)路徑規(guī)劃基礎(chǔ)知識(shí)數(shù)組、鏈表、棧、隊(duì)列、哈希表等基本數(shù)據(jù)結(jié)構(gòu)樹形結(jié)構(gòu)二叉樹、BST、堆、字典樹等及其遍歷操作圖算法圖的表示、DFS/BFS、最短路徑、拓?fù)渑判蚺判蛩阉鞲黝惻判蛩惴?、二分查找及其變體應(yīng)用高級(jí)技巧動(dòng)態(tài)規(guī)劃、貪心、回溯、分治等算法思想數(shù)學(xué)與邏輯位運(yùn)算、數(shù)論、概率、組合數(shù)學(xué)等基礎(chǔ)進(jìn)階學(xué)習(xí)建議初級(jí)階段(1-3月)掌握基本數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)算法思想刷簡(jiǎn)單難度題100+建立代碼模板庫中級(jí)階段(4-6月)深入動(dòng)態(tài)規(guī)劃和圖論刷中等難度題200+參與周賽提升速度整理錯(cuò)題和心得高級(jí)階段(7月+)挑戰(zhàn)困難題和競(jìng)賽研究算法優(yōu)化技巧參與開源項(xiàng)目實(shí)踐準(zhǔn)備系統(tǒng)設(shè)計(jì)面試實(shí)戰(zhàn)項(xiàng)目與競(jìng)賽推薦參與ACM/ICPC、GoogleCodeJam、LeetCode周賽等算法競(jìng)賽。實(shí)現(xiàn)經(jīng)典算法庫,如STL的部分容器和算法。開發(fā)算法可視化工具或在線判題系統(tǒng)。將算法應(yīng)用到實(shí)際項(xiàng)目中,如推薦系統(tǒng)、路徑規(guī)劃、數(shù)據(jù)分析等。課程答疑與互動(dòng)環(huán)節(jié)問:如何克服刷題的畏難情緒?答:從簡(jiǎn)單題開始建立信心,設(shè)定小目標(biāo)逐步達(dá)成。遇到難題不要?dú)怵H,看題解學(xué)習(xí)也是進(jìn)步。加入學(xué)習(xí)小組互相鼓勵(lì),分享解題心得。記住算法能力是練出來的,堅(jiān)持就會(huì)看到成效。問:時(shí)間復(fù)雜度分析有什么快速方法?答:記住常見模式:單層循環(huán)O(n),嵌套循環(huán)O(n2),二分O(logn),遞歸看遞歸樹深度和每層工作量。多數(shù)情況看最內(nèi)層循環(huán)執(zhí)行次數(shù)和遞歸深度。實(shí)在不確定就代入具體數(shù)字估算。問:動(dòng)態(tài)規(guī)劃狀態(tài)定義總是想不出來怎么辦?答:多做題積累經(jīng)驗(yàn),熟悉常見的狀態(tài)定義套路。嘗試從問題的最優(yōu)子結(jié)構(gòu)入手?？梢韵葘懕┝f歸,再加記憶化,最后改成DP?？磧?yōu)秀題解學(xué)習(xí)狀態(tài)設(shè)計(jì)思路,慢慢就能形成直覺。學(xué)員經(jīng)驗(yàn)分享"堅(jiān)持每天刷2-3題,3個(gè)月后明顯感覺思路清晰了很多?，F(xiàn)在看到題目能快速識(shí)別類型,套用對(duì)應(yīng)模板。"——張同學(xué),已拿到大廠offer"建議準(zhǔn)備一個(gè)錯(cuò)題本,記錄做錯(cuò)的題和當(dāng)時(shí)沒想到的優(yōu)化點(diǎn)。定期回顧,避免重復(fù)犯錯(cuò)。"——李同學(xué),算法競(jìng)賽獲獎(jiǎng)?wù)呓涣鲗W(xué)習(xí)小貼士加入算法學(xué)習(xí)群組,互相監(jiān)督打卡參與周賽和月賽,檢驗(yàn)學(xué)習(xí)效果在博客或公眾號(hào)分享解題思路關(guān)注大佬的題解,學(xué)習(xí)不同思路遇到問題及時(shí)提問,不要閉門造車定期總結(jié)知識(shí)點(diǎn),建立知識(shí)體系代碼實(shí)戰(zhàn)演示(一)鏈表操作現(xiàn)場(chǎng)編碼讓我們現(xiàn)場(chǎng)編寫一個(gè)常見的鏈表操作:刪除鏈表中的倒數(shù)第N個(gè)節(jié)點(diǎn)。這道題綜合考察了鏈表操作、雙指針技巧和邊界處理。問題描述給定一個(gè)鏈表,刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn),并返回鏈表的頭節(jié)點(diǎn)。要求只遍歷一次鏈表。解題思路使用雙指針技巧,快指針先走n步然后快慢指針同時(shí)移動(dòng),直到快指針到達(dá)末尾此時(shí)慢指針的下一個(gè)節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)使用虛擬頭節(jié)點(diǎn)簡(jiǎn)化邊界處理完整代碼實(shí)現(xiàn)classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefremove_nth_from_end(head,n):#創(chuàng)建虛擬頭節(jié)點(diǎn),簡(jiǎn)化邊界情況dummy=ListNode(0)dummy.next=head

#初始化快慢指針fast=slow=dummy

#快指針先走n步for_inrange(n):fast=fast.next

#快慢指針同時(shí)移動(dòng)whilefast.next:fast=fast.nextslow=slow.next

#刪除目標(biāo)節(jié)點(diǎn)slow.next=slow.next.next

returndummy.next#測(cè)試用例#輸入:1->2->3->4->5,n=2#輸出:1->2->3->5代碼調(diào)試要點(diǎn)邊界情況:刪除頭節(jié)點(diǎn)(n等于鏈表長(zhǎng)度)空指針檢查:確保fast.next不為空時(shí)才移動(dòng)測(cè)試用例:單節(jié)點(diǎn)鏈表、n=1、n等于鏈表長(zhǎng)度時(shí)間復(fù)雜度:O(L),L為鏈表長(zhǎng)度,只遍歷一次空間復(fù)雜度:O(1),只使用常數(shù)額外空間代碼實(shí)戰(zhàn)演示(二)動(dòng)態(tài)規(guī)劃經(jīng)典題目實(shí)現(xiàn)我們來實(shí)現(xiàn)一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃問題:最長(zhǎng)公共子序列(LCS)。這道題是序列DP的代表,在文本比對(duì)、版本控制等領(lǐng)域有廣泛應(yīng)用。01定義狀態(tài)dp[i][j]表示text1的前i個(gè)字符和text2的前j個(gè)字符的最長(zhǎng)公共子序列長(zhǎng)度02狀態(tài)轉(zhuǎn)移如果text1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+1否則:dp[i][j]=max(dp[i-1][j],dp[i][j-1])03初始化dp[0][j]和dp[i][0]都為0,表示空串的LCS長(zhǎng)度為004計(jì)算答案按行或按列填充dp表,最終答案在dp[m][n]代碼實(shí)現(xiàn)deflongest_common_subsequence(text1,text2):m,n=len(text1),len(text2)

#創(chuàng)建dp表dp=[[0]*(n+1)for_inrange(m+1)]

#填充dp表foriinrange(1,m+1):forjinrange(1,n+1):iftext1[i-1]==text2[j-1]:#字符相同,長(zhǎng)度加1dp[i][j]=dp[i-1][j-1]+1else:#字符不同,取左或上的最大值dp[i][j]=max(dp[i-1][j],dp[i][j-1])

returndp[m][n]#測(cè)試text1="abcde"text2="ace"print(longest_common_subsequence(text1,text2))