2026年牛客网暑期多校训练营试题详解与题解

2026年牛客网暑期多校训练营试题详解与题解一、编程基础（共3题，每题15分）1.[算法设计]合并多个有序链表题目描述：给定k个按非降序排列的链表，请设计一个算法将它们合并成一个新的有序链表。合并后的链表应满足所有节点按非降序排列。要求：-输入：链表的头节点数组（长度为k）。-输出：合并后的链表头节点。-时间复杂度：O(Nlogk)，其中N为所有链表节点的总和。示例：输入：`[[1,4,5],[1,3,4],[2,6]]`输出：`[1,1,2,3,4,4,5,6]`答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeKLists(lists):ifnotlists:returnNone使用最小堆优化合并过程importheapqheap=[]fori,headinenumerate(lists):ifhead:heapq.heappush(heap,(head.val,i,head))dummy=ListNode()current=dummywhileheap:val,i,node=heapq.heappop(heap)current.next=nodecurrent=current.nextifnode.next:heapq.heappush(heap,(node.next.val,i,node.next))returndummy.next解析：-使用最小堆（优先队列）存储每个链表的头节点，每次弹出最小值节点，并更新其下一个节点。-时间复杂度分析：每次弹出和插入操作为O(logk)，总操作次数为N，因此时间复杂度为O(Nlogk)。2.[字符串处理]重复字符串的最大重复次数题目描述：给定两个字符串`a`和`b`，请计算在`a`中重复`b`的最大次数，使得`b`的重复部分不重叠且均为`a`的子串。要求：-输入：两个字符串`a`和`b`。-输出：最大重复次数。-示例：`a="abcabcabc",b="abc"`→输出：3答案与解析：pythondefmax_repeating(a:str,b:str)->int:ifnotb:return0暴力匹配，记录最大次数max_count=0i=0whilei<=len(a)-len(b):j=0whilej<len(b)anda[i+j]==b[j]:j+=1ifj==len(b):max_count+=1i+=len(b)#避免重叠else:i+=1returnmax_count解析：-通过滑动窗口匹配`b`在`a`中的出现次数，每次匹配成功后跳过整个`b`的长度以避免重叠。-时间复杂度：O(NM)，其中N为`a`的长度，M为`b`的长度。3.[数据结构]实现LRU缓存题目描述：设计一个LRU（LeastRecentlyUsed）缓存，支持以下操作：-`get(key)`：获取键对应的值，如果键不存在返回-1。-`put(key,value)`：插入或更新键值对，如果缓存已满则删除最久未使用的键。要求：-使用双向链表和哈希表实现，支持O(1)时间复杂度的操作。答案与解析：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_pop_tail(self):res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.value=valueself._move_to_head(node)解析：-使用双向链表维护最近使用顺序，哈希表存储键到节点的映射。-`get`操作将节点移动到头部，`put`操作在哈希表中查找键，如果不存在则插入并移动到头部，如果缓存已满则删除尾节点。二、系统设计（共2题，每题25分）4.[分布式系统]负载均衡算法设计题目描述：设计一个负载均衡算法，用于将客户端请求均匀分配到多个服务器上。假设有`n`台服务器，每台服务器的当前负载为`weights`数组。要求：-输入：服务器数量`n`和权重数组`weights`。-输出：为每个请求分配的服务器索引（从0开始）。-算法需保证长期均衡分配，避免某一台服务器负载过高。示例：输入：`n=3,weights=[1,2,3]`输出：可能为`[0,1,2,0,1,2,...]`答案与解析：pythondefload_balancer(n,weights):total_weight=sum(weights)current_weights=weights.copy()result=[]for_inrange(total_weight):轮询算法的变种，考虑权重max_idx=0max_weight=0foriinrange(n):ifcurrent_weights[i]>max_weight:max_weight=current_weights[i]max_idx=iresult.append(max_idx)current_weights[max_idx]-=1returnresult解析：-通过轮询算法结合权重调整，每次选择当前权重最大的服务器。-确保权重较大的服务器不会被优先分配，从而实现长期均衡。5.[数据库设计]电商订单系统数据库表设计题目描述：设计一个电商订单系统的数据库表结构，支持以下功能：-订单创建、查询、修改状态。-用户下单、支付、发货、收货等流程。-关联用户、商品、库存等信息。要求：-设计至少3张核心表（订单表、用户表、商品表），并说明主键、外键关系。-说明至少3个关键约束（如唯一性、非空性）。答案与解析：表结构：1.用户表(users)-`user_id`(主键,自增)-`name`(非空)-`email`(唯一,非空)-`register_date`(非空)2.商品表(products)-`product_id`(主键,自增)-`name`(非空)-`price`(非空)-`stock`(非空,大于等于0)3.订单表(orders)-`order_id`(主键,自增)-`user_id`(外键,关联users表)-`order_date`(非空)-`status`(非空,枚举:待支付/已支付/已发货/已完成)-`total_amount`(非空)约束：-`users.email`唯一约束，防止重复注册。-`orders.user_id`外键约束，关联用户表。-`products.stock`非空且大于等于0，防止超卖。解析：-通过用户表、商品表、订单表关联，支持订单全流程管理。-约束确保数据一致性，如唯一性防止重复注册，外键保证引用完整性。三、算法进阶（共2题，每题20分）6.[动态规划]最长重复子数组题目描述：给定两个数组`A`和`B`，请计算它们的最长重复子数组的长度。要求：-输入：两个数组`A`和`B`。-输出：最长重复子数组的长度。-示例：`A=[1,2,3,2,1],B=[2,1,2,1,2]`→输出：2答案与解析：pythondeffindLength(A,B):m,n=len(A),len(B)dp=[[0](n+1)for_inrange(m+1)]max_len=0foriinrange(m):forjinrange(n):ifA[i]==B[j]:dp[i+1][j+1]=dp[i][j]+1max_len=max(max_len,dp[i+1][j+1])returnmax_len解析：-使用动态规划，`dp[i][j]`表示以`A[i-1]`和`B[j-1]`结尾的最长重复子数组长度。-时间复杂度：O(mn)，空间复杂度：O(mn)。7.[贪心算法]区间调度问题题目描述：给定一系列区间`[[start1,end1],[start2,end2],...]`，请计算最多可以安排多少个不重叠的区间。要求：-输入：区间列表。-输出：最大不重叠区间数量。-示例：`[[1,3],[2,4],[3,5]]`→输出：2答案与解析：pythondeferaseOverlapIntervals(intervals):ifnotintervals:return0按结束时间排序intervals.sort(key=lambdax:x[1])count=0end=float('-inf')forintervalinintervals:ifinterval[0]>=end:count+=1end=interval[1]returncount解析：-贪心策略：按区间结束时间升序排序，每次选择不与当前区间重叠的区间。-时间复杂度：O(NlogN)，空间复杂度：O(1)。答案与解析（补充）编程基础部分：1.合并多个有序链表：最小堆