2025年常见编程算法题库及答案

2025年常见编程算法题库及答案动态规划问题1：最长公共子序列（空间优化版）给定两个字符串s和t，返回它们的最长公共子序列（LCS）的长度。要求使用O(n)空间复杂度，其中n为较短字符串的长度。解法思路：传统LCS使用二维数组dp[i][j]表示s前i个字符与t前j个字符的LCS长度，状态转移方程为：若s[i-1]==t[j-1]，则dp[i][j]=dp[i-1][j-1]+1；否则取dp[i-1][j]和dp[i][j-1]的最大值。空间优化时，由于每次仅需上一行和当前行的前一个值，可用一维数组并维护prev变量保存左上角值，将空间复杂度从O(mn)降至O(n)（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]保存当前行原dp[j]值（即上一行的dp[j]）ifs[i-1]==t[j-1]:dp[j]=prev+1else:dp[j]=max(dp[j],dp[j-1])取上一行当前列或当前行前一列的最大值prev=temp更新prev为当前行原dp[j]值，供下一轮j+1使用returndp[n]```贪心算法问题2：跳跃游戏IV（最少跳跃次数）给定非负整数数组nums，每个元素表示在当前位置可跳跃的最大长度。初始位于0索引，每次可跳1到nums[i]步，求到达最后一个位置的最少跳跃次数。解法思路：贪心策略。维护当前能到达的最远位置current_end和下一步能到达的最远位置max_reach。遍历数组时，不断更新max_reach；当遍历到current_end时，说明必须进行一次跳跃，此时跳跃次数加一，并将current_end更新为max_reach。若current_end已覆盖最后一个位置，提前终止。代码实现（Python）：```pythondefjump(nums):n=len(nums)ifn<=1:return0jumps=0跳跃次数current_end=0当前能到达的最远位置max_reach=0下一步能到达的最远位置foriinrange(n1):无需遍历最后一个元素max_reach=max(max_reach,i+nums[i])更新下一步最远位置ifi==current_end:到达当前边界，必须跳跃jumps+=1current_end=max_reach更新边界为下一步最远位置ifcurrent_end>=n1:提前到达终点breakreturnjumps```回溯算法问题3：组合总和III（k个数和为n）找出所有k个数的组合，使其和为n，每个数取自1-9且不重复。解法思路：回溯法。从1开始尝试选择数字，确保路径长度不超过k，且当前和不超过n。当路径长度等于k时，若和为n则记录结果。通过剪枝（如当前数大于剩余和时提前终止循环）减少无效递归。代码实现（Python）：```pythondefcombination_sum3(k,n):res=[]defbacktrack(start,path,target):iflen(path)==k:路径长度达标iftarget==0:和为nres.append(path.copy())return从start开始选数，避免重复（如[1,2]和[2,1]视为同一组合）foriinrange(start,10):ifi>target:当前数大于剩余和，后续数更大，无需继续breakpath.append(i)backtrack(i+1,path,targeti)下一轮从i+1开始，避免重复path.pop()回溯backtrack(1,[],n)初始从1开始，路径为空，剩余和为nreturnres```图论算法问题4：Dijkstra算法（优先队列优化）给定有向图的邻接表（每个节点存储邻接节点及边权），求单源最短路径（从起点到所有其他节点的最短距离）。解法思路：使用优先队列（最小堆）优化传统Dijkstra算法。维护距离数组dist，初始时起点距离为0，其他为无穷大。每次从堆中取出当前距离最小的节点u，遍历其邻接节点v，若通过u到v的路径更短（即dist[u]+边权<dist[v]），则更新dist[v]并将新距离加入堆中。通过堆的性质确保每次处理的是当前最优节点。代码实现（Python）：```pythonimportheapqdefdijkstra(graph,start):n=len(graph)节点数（假设节点编号0到n-1）dist=[float('inf')]ndist[start]=0heap=[]heapq.heappush(heap,(0,start))堆中元素为（距离，节点）whileheap:current_dist,u=heapq.heappop(heap)ifcurrent_dist>dist[u]:已存在更短路径，跳过continueforv,wingraph[u]:遍历u的所有邻接节点v及边权wifdist[v]>dist[u]+w:发现更短路径dist[v]=dist[u]+wheapq.heappush(heap,(dist[v],v))将新距离加入堆returndist```字符串处理问题5：KMP算法（模式匹配）实现KMP算法，返回模式串pattern在文本text中的起始索引（若不存在返回-1）。解法思路：KMP核心是构建部分匹配表（最长前缀后缀数组lps），避免主串指针回溯。lps[i]表示pattern[0..i]的最长相等真前缀和后缀长度。匹配时，若字符不匹配，利用lps数组将pattern指针回退到lps[j-1]，减少无效比较。代码实现（Python）：```pythondefkmp_search(text,pattern):n,m=len(text),len(pattern)ifm==0:空模式串返回0return0构建最长前缀后缀数组lpslps=[0]mlength=0最长前缀后缀长度i=1whilei<m:ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:回退到前一个长度length=lps[length1]else:无匹配，lps[i]为0，i递增lps[i]=0i+=1匹配过程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时，i递增i+=1return-1未找到```数组与链表问题6：合并区间（插入新区间）给定无重叠且按起始点排序的区间列表intervals，插入一个新的区间new_interval，合并所有重叠的区间。解法思路：分三步处理。第一步将不重叠的前置区间加入结果；第二步合并所有与new_interval重叠的区间（扩展new_interval的起止点）；第三步将剩余不重叠的后置区间加入结果。代码实现（Python）：```pythondefinsert_interval(intervals,new_interval):res=[]i=0n=len(intervals)1.处理前置不重叠区间（原区间结束<新区间开始）whilei<nandintervals[i][1]<new_interval[0]:res.append(intervals[i])i+=12.合并重叠区间（原区间开始<=新区间结束）whilei<nandintervals[i][0]<=new_interval[1]:new_interval[0]=min(new_interval[0],intervals[i][0])扩展左边界new_interval[1]=max(new_interval[1],intervals[i][1])扩展右边界i+=1res.append(new_interval)加入合并后的新区间3.处理后置不重叠区间whilei<n:res.append(intervals[i])i+=1returnres```数学类算法问题7：快速幂（计算x的n次幂）实现函数my_pow(x,n)，计算x的n次幂，其中n为整数（包括负数）。解法思路：分治思想。将指数n二分，递归计算x^(n/2)，利用x^n=(x^(n/2))^2（n为偶数）或x(x^(n/2))^2（n为奇数）。处理负数时，取倒数并将n转为正数。代码实现（Python）：```pythondefmy_pow(x,n):defquick_pow(a,b):ifb==0:边界条件：任何数的0次幂为1return1.0res=quick_pow(a,b//2)递归计算a^(b//2)ifb%2==1:指数为奇数returnresresaelse:指数为偶数returnresresifn<0:处理负数指数x=1/xn=-nreturnquick_pow(x,n)```数据结构操作问题8：环形链表II（找环的入口节点）给定链表头节点head，判断是否有环。若有环，返回环的入口节点；否则返回None。解法思路：快