2025年编程挑战赛中级实战模拟题及解析

2025年编程挑战赛中级实战模拟题及解析#2025年编程挑战赛中级实战模拟题1.算法设计题（共3题，每题20分）题目1：最长有效括号（20分）问题描述：给定一个由`'('`和`')'`组成的字符串`s`，找出其中最长的有效（括号正确匹配）括号子串的长度。示例：-输入：`"(()"`-输出：`2`-解释：最长有效括号子串是`"()"`要求：-时间复杂度O(n)-空间复杂度O(n)提示：-可以使用栈或双指针方法解决题目2：合并区间（20分）问题描述：给定一个区间列表`intervals`，其中`intervals[i]=[start_i,end_i]`，合并所有重叠的区间，并返回一个不重叠的区间列表。如果两个区间有重叠，则将它们合并为一个区间。示例：-输入：`[[1,3],[2,6],[8,10],[15,18]]`-输出：`[[1,6],[8,10],[15,18]]`-解释：区间`[1,3]`和`[2,6]`重叠，合并为`[1,6]`要求：-合并后的区间按起始位置升序排列-不能有重复区间题目3：单词搜索（20分）问题描述：给定一个`mxn`的字符矩阵`board`和一个字符串`word`，判断`word`是否存在于`board`中。每个格子可以且只能使用一次。示例：-输入：`board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word="ABCCED"`-输出：`true`-解释：如上图所示要求：-可以使用回溯算法-考虑所有可能的路径2.数据结构题（共2题，每题25分）题目4：二叉树的最大深度（25分）问题描述：给定一个二叉树的根节点`root`，返回其最大深度。二叉树的深度为根节点到最底层叶节点的最大路径长度。示例：-输入：`[3,9,20,null,null,15,7]`-输出：`3`-解释：最大深度从根到叶节点`[3,9,15]`或`[3,9,7]`要求：-可以使用递归或迭代方法-处理空树的情况（深度为0）题目5：LRU缓存机制（25分）问题描述：设计一个LRU（最近最少使用）缓存机制。它应该支持以下操作：-`LRUCache(intcapacity)`：初始化缓存容量为`capacity`-`get(intkey)`：如果键存在，则返回其值，否则返回`-1`-`put(intkey,intvalue)`：如果键存在，则更新其值；如果键不存在，则添加键值对。当缓存容量已满时，删除最近最少使用的缓存项示例：-初始化`LRUCache(2)`-`put(1,1)`-`put(2,2)`-`get(1)`返回`1`-`put(3,3)`（容量已满，删除键`2`）-`get(2)`返回`-1`要求：-使用哈希表和双向链表实现-`get`和`put`操作的时间复杂度为O(1)3.编码实现题（共3题，每题25分）题目6：移动零（25分）问题描述：给定一个数组`nums`，原地修改该数组，将所有`0`移动到数组的末尾，同时保持非零元素的相对顺序。示例：-输入：`[0,1,0,3,12]`-输出：`[1,3,12,0,0]`要求：-不能使用额外空间-只允许用常数个额外空间题目7：字符串转换整数（25分）问题描述：实现一个`myAtoi`函数，将字符串`s`转换为整数。转换规则如下：-忽略前导空格-如果第一个非空字符是正号或负号，记录符号-从第一个非空字符开始，读取字符直到遇到非数字字符或字符串结束-如果没有数字字符，返回`0`-最终结果可能为正或负，确保结果在`32位有符号整数`范围内（即`-2^31`到`2^31-1`）示例：-输入：`"-42"`-输出：`-42`-解释：忽略前导空格，第一个非空字符是`-`，接下来是数字`42`要求：-处理溢出情况（如`"21474836460"`应返回`2147483647`）-考虑所有边界条件题目8：有效括号（25分）问题描述：给定一个字符串`s`，判断它是否是一个有效的括号字符串。有效括号字符串需满足：-只包含字符`'('`,`')'`,`{'}`,`'}'`,`'['`,`']'`-左括号必须与相同类型的右括号匹配-括号必须正确嵌套示例：-输入：`"()"`→`true`-输入：`"()[]{}"`→`true`-输入：`"(]"`→`false`要求：-使用栈或哈希表实现-时间复杂度O(n)答案答案1：最长有效括号（20分）思路：使用栈记录括号的索引位置。遍历字符串，当遇到`'('`时压入栈，遇到`')'`时弹出栈顶。如果栈为空，则当前`')'`没有匹配的`'('`；否则，当前有效括号的长度为`i-stack[-1]`。代码（Python）：pythondeflongestValidParentheses(s:str)->int:stack=[-1]max_len=0fori,charinenumerate(s):ifchar=='(':stack.append(i)else:stack.pop()ifnotstack:stack.append(i)else:max_len=max(max_len,i-stack[-1])returnmax_len答案2：合并区间（20分）思路：首先按区间的起始位置排序，然后遍历区间列表，合并所有重叠的区间。代码（Python）：pythondefmerge(intervals):ifnotintervals:return[]intervals.sort(key=lambdax:x[0])merged=[intervals[0]]forcurrentinintervals[1:]:last=merged[-1]ifcurrent[0]<=last[1]:merged[-1][1]=max(last[1],current[1])else:merged.append(current)returnmerged答案3：单词搜索（20分）思路：使用回溯算法，遍历每个格子，尝试按上下左右方向搜索。使用`visited`数组记录已访问的格子，避免重复使用。代码（Python）：pythondefexist(board,word):m,n=len(board),len(board[0])directions=[(0,1),(1,0),(0,-1),(-1,0)]defdfs(i,j,k):ifnot(0<=i<mand0<=j<n):returnFalseifboard[i][j]!=word[k]:returnFalseifk==len(word)-1:returnTruetemp=board[i][j]board[i][j]='#'fordx,dyindirections:ifdfs(i+dx,j+dy,k+1):returnTrueboard[i][j]=tempreturnFalseforiinrange(m):forjinrange(n):ifdfs(i,j,0):returnTruereturnFalse答案4：二叉树的最大深度（25分）思路：使用递归方法，计算左子树和右子树的最大深度，取较大值加1。代码（Python）：python#Definitionforabinarytreenode.classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))答案5：LRU缓存机制（25分）思路：使用双向链表和哈希表实现。双向链表头部为最近使用节点，尾部为最久未使用节点。哈希表存储键到链表节点的映射。代码（Python）：pythonclassListNode:def__init__(self,key=0,val=0,prev=None,next=None):self.key=keyself.val=valself.prev=prevself.next=nextclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=ListNode(0,0),ListNode(0,0)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.valdefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnode:node.val=valueself._move_to_head(node)else:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]答案6：移动零（25分）思路：双指针方法。一个指针用于遍历，另一个指针记录非零元素的位置。遍历时将非零元素依次移动到前面。代码（Python）：pythondefmoveZeroes(nums):left=0forrightinrange(len(nums)):ifnums[right]!=0:nums[left],nums[right]=nums[right],nums[left]left+=1答案7：字符串转换整数（25分）思路：按规则逐步处理字符串，注意边界条件。使用`int`转换时处理溢出。代码（Python）：pythondefmyAtoi(s:str)->int:s=s.strip()ifnots:return0sign=1i=0ifs[0]=='-':sign=-1i+=1elifs[0]=='+':i+=1result=0INT_MAX=231-1INT_MIN=-231whilei<len(s)ands[i].isdigit():digit=int(s[i])#Checkforoverflowifresult>(INT_MAX-digit)//10:returnINT_MAXifsign==1elseINT_MINresult=result*10+digiti+=1returnsign*result答案8：有效括号（25分）思路：使用栈存储左括号，遇到右括号时与栈顶匹配。如果匹配则弹出，否则无效。代码（Python）：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stac