2025年程序设计算法与数据结构练习题答案

2025年程序设计算法与数据结构练习题答案问题1：允许最多k次修改的最长连续递增子数组给定整数数组nums，允许将最多k个元素修改为任意整数，求修改后最长的连续递增子数组的长度。连续递增子数组定义为子数组中每个元素严格大于前一个元素（即nums[i]<nums[i+1]对所有i在子数组范围内成立）。解题思路：连续递增的关键在于相邻元素的关系，可将问题转化为寻找最长区间[left,right]，使得区间内相邻元素不满足递增的位置数（缺陷数）不超过k。使用滑动窗口法，维护窗口内的缺陷数，当缺陷数超过k时移动左指针，直到缺陷数≤k。代码实现（Python）：```pythondeflongest_increasing_subarray(nums,k):n=len(nums)ifn<=1:returnnmax_len=1left=0defects=0记录窗口内相邻不递增的次数forrightinrange(1,n):ifnums[right]<=nums[right-1]:defects+=1缺陷数超过k时，收缩左边界whiledefects>k:ifnums[left]>=nums[left+1]:defects-=1left+=1更新最大长度current_len=rightleft+1ifcurrent_len>max_len:max_len=current_lenreturnmax_len```复杂度分析：时间复杂度O(n)，每个元素最多被左右指针各访问一次；空间复杂度O(1)，仅用常数额外空间。问题2：前序与后序重建二叉树及根到叶子路径异或和总和已知二叉树的前序遍历序列pre和后序遍历序列post，重建该二叉树，并计算所有根到叶子路径的异或和的总和。解题思路：前序首元素为根，后序末元素也为根。前序次元素（若存在）是左子树根，在后序中找到其位置可确定左子树大小，递归构建左右子树。重建后，通过DFS遍历所有根到叶子路径，累加路径异或和。代码实现（Python）：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefconstruct_from_pre_post(pre,post):ifnotpre:returnNoneroot=TreeNode(pre[0])iflen(pre)==1:returnroot找左子树根在后序中的位置left_root_val=pre[1]pos=post.index(left_root_val)分割左右子树的前序和后序left_post=post[:pos+1]left_pre=pre[1:1+len(left_post)]right_post=post[pos+1:-1]right_pre=pre[1+len(left_post):]root.left=construct_from_pre_post(left_pre,left_post)root.right=construct_from_pre_post(right_pre,right_post)returnrootdefsum_xor_paths(root):total=0defdfs(node,current_xor):nonlocaltotalifnotnode:returncurrent_xor^=node.valifnotnode.leftandnotnode.right:叶子节点total+=current_xorreturndfs(node.left,current_xor)dfs(node.right,current_xor)dfs(root,0)returntotal```复杂度分析：重建树时间复杂度O(n²)（未优化查找），优化后O(n)；DFS时间复杂度O(n)。空间复杂度O(n)（递归栈）。问题3：SPFA算法处理负权图最短路径及负环检测给定有向图（可能含负权边），用SPFA算法求起点s到所有顶点的最短路径。若存在s可达的负环，输出“存在负环”。解题思路：SPFA是Bellman-Ford的队列优化，维护距离数组和入队次数。若节点入队次数≥顶点数n，说明存在负环。代码实现（Python）：```pythondefspfa(n,edges,s):fromcollectionsimportdequeadj=[[]for_inrange(n)]邻接表foru,v,winedges:adj[u].append((v,w))dist=[float('inf')]ndist[s]=0in_queue=[False]n标记是否在队列中cnt=[0]n记录入队次数q=deque([s])in_queue[s]=Truecnt[s]=1whileq:u=q.popleft()in_queue[u]=Falseforv,winadj[u]:ifdist[v]>dist[u]+w:dist[v]=dist[u]+wifnotin_queue[v]:q.append(v)in_queue[v]=Truecnt[v]+=1ifcnt[v]>=n:检测到负环return"存在负环"returndist```复杂度分析：平均时间复杂度O(m)，最坏O(nm)；空间复杂度O(n+m)（邻接表存储）。问题4：可变代价的字符串编辑距离给定字符串s和t，插入、删除、替换的代价函数分别为ins_cost(c)、del_cost(c)、rep_cost(a,b)，求将s转换为t的最小代价。解题思路：动态规划。定义dp[i][j]为s前i字符转t前j字符的最小代价。初始条件：dp[0][j]为插入j次代价和，dp[i][0]为删除i次代价和。状态转移考虑插入、删除、替换的最小代价。代码实现（Python）：```pythondefedit_distance(s,t,ins_cost,del_cost,rep_cost):m,n=len(s),len(t)dp=[[0](n+1)for_inrange(m+1)]初始化：删除s前i个字符的代价foriinrange(1,m+1):dp[i][0]=dp[i-1][0]+del_cost(s[i-1])初始化：插入t前j个字符的代价forjinrange(1,n+1):dp[0][j]=dp[0][j-1]+ins_cost(t[j-1])状态转移foriinrange(1,m+1):forjinrange(1,n+1):ifs[i-1]==t[j-1]:dp[i][j]=dp[i-1][j-1]else:delete=dp[i-1][j]+del_cost(s[i-1])insert=dp[i][j-1]+ins_cost(t[j-1])replace=dp[i-1][j-1]+rep_cost(s[i-1],t[j-1])dp[i][j]=min(delete,insert,replace)returndp[m][n]```复杂度分析：时间复杂度O(mn)，空间复杂度O(mn)（可优化为O(n)）。问题5：合并k个有序链表（O(Nlogk)时间）合并k个升序链表，要求时间复杂度O(Nlogk)（N为总节点数，k为链表数）。解题思路：使用最小堆。每次从所有链表头节点中选最小值，加入结果链表，并将该链表的下一个节点（若有）入堆。堆中存储（值，链表索引，节点）以避免重复值冲突。代码实现（Python）：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmerge_k_lists(lists):importheapqdummy=ListNode(0)curr=dummyheap=[]初始化堆：加入非空链表的头节点fori,linenumerate(lists):ifl:heapq.heappush(heap,(l.val,i,l))whileheap:val,idx,node=heapq.heappop(heap