2025年常見(jiàn)編程算法題庫(kù)及答案動(dòng)態(tài)規(guī)劃問(wèn)題1：最長(zhǎng)公共子序列（空間優(yōu)化版）給定兩個(gè)字符串s和t，返回它們的最長(zhǎng)公共子序列（LCS）的長(zhǎng)度。要求使用O(n)空間復(fù)雜度，其中n為較短字符串的長(zhǎng)度。解法思路：傳統(tǒng)LCS使用二維數(shù)組dp[i][j]表示s前i個(gè)字符與t前j個(gè)字符的LCS長(zhǎng)度，狀態(tài)轉(zhuǎn)移方程為：若s[i-1]==t[j-1]，則dp[i][j]=dp[i-1][j-1]+1；否則取dp[i-1][j]和dp[i][j-1]的最大值?？臻g優(yōu)化時(shí)，由于每次僅需上一行和當(dāng)前行的前一個(gè)值，可用一維數(shù)組并維護(hù)prev變量保存左上角值，將空間復(fù)雜度從O(mn)降至O(n)（n為較短字符串長(zhǎng)度）。代碼實(shí)現(xiàn)（Python）：```pythondeflongest_common_subsequence(s,t):m,n=len(s),len(t)ifm<n:確保t是較短字符串，減少空間使用s,t=t,sm,n=n,mdp=[0](n+1)foriinrange(1,m+1):prev=0保存左上角的值（dp[i-1][j-1]）forjinrange(1,n+1):temp=dp[j]保存當(dāng)前行原dp[j]值（即上一行的dp[j]）ifs[i-1]==t[j-1]:dp[j]=prev+1else:dp[j]=max(dp[j],dp[j-1])取上一行當(dāng)前列或當(dāng)前行前一列的最大值prev=temp更新prev為當(dāng)前行原dp[j]值，供下一輪j+1使用returndp[n]```貪心算法問(wèn)題2：跳躍游戲IV（最少跳躍次數(shù)）給定非負(fù)整數(shù)數(shù)組nums，每個(gè)元素表示在當(dāng)前位置可跳躍的最大長(zhǎng)度。初始位于0索引，每次可跳1到nums[i]步，求到達(dá)最后一個(gè)位置的最少跳躍次數(shù)。解法思路：貪心策略。維護(hù)當(dāng)前能到達(dá)的最遠(yuǎn)位置current_end和下一步能到達(dá)的最遠(yuǎn)位置max_reach。遍歷數(shù)組時(shí)，不斷更新max_reach；當(dāng)遍歷到current_end時(shí)，說(shuō)明必須進(jìn)行一次跳躍，此時(shí)跳躍次數(shù)加一，并將current_end更新為max_reach。若current_end已覆蓋最后一個(gè)位置，提前終止。代碼實(shí)現(xiàn)（Python）：```pythondefjump(nums):n=len(nums)ifn<=1:return0jumps=0跳躍次數(shù)current_end=0當(dāng)前能到達(dá)的最遠(yuǎn)位置max_reach=0下一步能到達(dá)的最遠(yuǎn)位置foriinrange(n1):無(wú)需遍歷最后一個(gè)元素max_reach=max(max_reach,i+nums[i])更新下一步最遠(yuǎn)位置ifi==current_end:到達(dá)當(dāng)前邊界，必須跳躍jumps+=1current_end=max_reach更新邊界為下一步最遠(yuǎn)位置ifcurrent_end>=n1:提前到達(dá)終點(diǎn)breakreturnjumps```回溯算法問(wèn)題3：組合總和III（k個(gè)數(shù)和為n）找出所有k個(gè)數(shù)的組合，使其和為n，每個(gè)數(shù)取自1-9且不重復(fù)。解法思路：回溯法。從1開(kāi)始嘗試選擇數(shù)字，確保路徑長(zhǎng)度不超過(guò)k，且當(dāng)前和不超過(guò)n。當(dāng)路徑長(zhǎng)度等于k時(shí)，若和為n則記錄結(jié)果。通過(guò)剪枝（如當(dāng)前數(shù)大于剩余和時(shí)提前終止循環(huán)）減少無(wú)效遞歸。代碼實(shí)現(xiàn)（Python）：```pythondefcombination_sum3(k,n):res=[]defbacktrack(start,path,target):iflen(path)==k:路徑長(zhǎng)度達(dá)標(biāo)iftarget==0:和為nres.append(path.copy())return從start開(kāi)始選數(shù)，避免重復(fù)（如[1,2]和[2,1]視為同一組合）foriinrange(start,10):ifi>target:當(dāng)前數(shù)大于剩余和，后續(xù)數(shù)更大，無(wú)需繼續(xù)breakpath.append(i)backtrack(i+1,path,targeti)下一輪從i+1開(kāi)始，避免重復(fù)path.pop()回溯backtrack(1,[],n)初始從1開(kāi)始，路徑為空，剩余和為nreturnres```圖論算法問(wèn)題4：Dijkstra算法（優(yōu)先隊(duì)列優(yōu)化）給定有向圖的鄰接表（每個(gè)節(jié)點(diǎn)存儲(chǔ)鄰接節(jié)點(diǎn)及邊權(quán)），求單源最短路徑（從起點(diǎn)到所有其他節(jié)點(diǎn)的最短距離）。解法思路：使用優(yōu)先隊(duì)列（最小堆）優(yōu)化傳統(tǒng)Dijkstra算法。維護(hù)距離數(shù)組dist，初始時(shí)起點(diǎn)距離為0，其他為無(wú)窮大。每次從堆中取出當(dāng)前距離最小的節(jié)點(diǎn)u，遍歷其鄰接節(jié)點(diǎn)v，若通過(guò)u到v的路徑更短（即dist[u]+邊權(quán)<dist[v]），則更新dist[v]并將新距離加入堆中。通過(guò)堆的性質(zhì)確保每次處理的是當(dāng)前最優(yōu)節(jié)點(diǎn)。代碼實(shí)現(xiàn)（Python）：```pythonimportheapqdefdijkstra(graph,start):n=len(graph)節(jié)點(diǎn)數(shù)（假設(shè)節(jié)點(diǎn)編號(hào)0到n-1）dist=[float('inf')]ndist[start]=0heap=[]heapq.heappush(heap,(0,start))堆中元素為（距離，節(jié)點(diǎn)）whileheap:current_dist,u=heapq.heappop(heap)ifcurrent_dist>dist[u]:已存在更短路徑，跳過(guò)continueforv,wingraph[u]:遍歷u的所有鄰接節(jié)點(diǎn)v及邊權(quán)wifdist[v]>dist[u]+w:發(fā)現(xiàn)更短路徑dist[v]=dist[u]+wheapq.heappush(heap,(dist[v],v))將新距離加入堆returndist```字符串處理問(wèn)題5：KMP算法（模式匹配）實(shí)現(xiàn)KMP算法，返回模式串pattern在文本text中的起始索引（若不存在返回-1）。解法思路：KMP核心是構(gòu)建部分匹配表（最長(zhǎng)前綴后綴數(shù)組lps），避免主串指針回溯。lps[i]表示pattern[0..i]的最長(zhǎng)相等真前綴和后綴長(zhǎng)度。匹配時(shí)，若字符不匹配，利用lps數(shù)組將pattern指針回退到lps[j-1]，減少無(wú)效比較。代碼實(shí)現(xiàn)（Python）：```pythondefkmp_search(text,pattern):n,m=len(text),len(pattern)ifm==0:空模式串返回0return0構(gòu)建最長(zhǎng)前綴后綴數(shù)組lpslps=[0]mlength=0最長(zhǎng)前綴后綴長(zhǎng)度i=1whilei<m:ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:回退到前一個(gè)長(zhǎng)度length=lps[length1]else:無(wú)匹配，lps[i]為0，i遞增lps[i]=0i+=1匹配過(guò)程i=j=0i為text指針，j為pattern指針whilei<n:ifpattern[j]==text[i]:i+=1j+=1ifj==m:完全匹配，返回起始位置returnijelse:ifj!=0:利用lps回退jj=lps[j1]else:j=0時(shí)，i遞增i+=1return-1未找到```數(shù)組與鏈表問(wèn)題6：合并區(qū)間（插入新區(qū)間）給定無(wú)重疊且按起始點(diǎn)排序的區(qū)間列表intervals，插入一個(gè)新的區(qū)間new_interval，合并所有重疊的區(qū)間。解法思路：分三步處理。第一步將不重疊的前置區(qū)間加入結(jié)果；第二步合并所有與new_interval重疊的區(qū)間（擴(kuò)展new_interval的起止點(diǎn)）；第三步將剩余不重疊的后置區(qū)間加入結(jié)果。代碼實(shí)現(xiàn)（Python）：```pythondefinsert_interval(intervals,new_interval):res=[]i=0n=len(intervals)1.處理前置不重疊區(qū)間（原區(qū)間結(jié)束<新區(qū)間開(kāi)始）whilei<nandintervals[i][1]<new_interval[0]:res.append(intervals[i])i+=12.合并重疊區(qū)間（原區(qū)間開(kāi)始<=新區(qū)間結(jié)束）whilei<nandintervals[i][0]<=new_interval[1]:new_interval[0]=min(new_interval[0],intervals[i][0])擴(kuò)展左邊界new_interval[1]=max(new_interval[1],intervals[i][1])擴(kuò)展右邊界i+=1res.append(new_interval)加入合并后的新區(qū)間3.處理后置不重疊區(qū)間whilei<n:res.append(intervals[i])i+=1returnres```數(shù)學(xué)類算法問(wèn)題7：快速冪（計(jì)算x的n次冪）實(shí)現(xiàn)函數(shù)my_pow(x,n)，計(jì)算x的n次冪，其中n為整數(shù)（包括負(fù)數(shù)）。解法思路：分治思想。將指數(shù)n二分，遞歸計(jì)算x^(n/2)，利用x^n=(x^(n/2))^2（n為偶數(shù)）或x(x^(n/2))^2（n為奇數(shù)）。處理負(fù)數(shù)時(shí)，取倒數(shù)并將n轉(zhuǎn)為正數(shù)。代碼實(shí)現(xiàn)（Python）：```pythondefmy_pow(x,n):defquick_pow(a,b):ifb==0:邊界條件：任何數(shù)的0次冪為1return1.0res=quick_pow(a,b//2)遞歸計(jì)算a^(b//2)ifb%2==1:指數(shù)為奇數(shù)returnresresaelse:指數(shù)為偶數(shù)returnresresifn<0:處理負(fù)數(shù)指數(shù)x=1/xn=-nreturnquick_pow(x,n)```數(shù)據(jù)結(jié)構(gòu)操作問(wèn)題8：環(huán)形鏈表II（找環(huán)的入口節(jié)點(diǎn)）給定鏈表頭節(jié)點(diǎn)head，判斷是否有環(huán)。若有環(huán)，返回環(huán)的入口節(jié)點(diǎn)；否則返回None。解法思路：快