2025年編程挑戰(zhàn)賽中級(jí)實(shí)戰(zhàn)模擬題及解析#2025年編程挑戰(zhàn)賽中級(jí)實(shí)戰(zhàn)模擬題1.算法設(shè)計(jì)題（共3題，每題20分）題目1：最長(zhǎng)有效括號(hào)（20分）問題描述：給定一個(gè)由`'('`和`')'`組成的字符串`s`，找出其中最長(zhǎng)的有效（括號(hào)正確匹配）括號(hào)子串的長(zhǎng)度。示例：-輸入：`"(()"`-輸出：`2`-解釋：最長(zhǎng)有效括號(hào)子串是`"()"`要求：-時(shí)間復(fù)雜度O(n)-空間復(fù)雜度O(n)提示：-可以使用?；螂p指針方法解決題目2：合并區(qū)間（20分）問題描述：給定一個(gè)區(qū)間列表`intervals`，其中`intervals[i]=[start_i,end_i]`，合并所有重疊的區(qū)間，并返回一個(gè)不重疊的區(qū)間列表。如果兩個(gè)區(qū)間有重疊，則將它們合并為一個(gè)區(qū)間。示例：-輸入：`[[1,3],[2,6],[8,10],[15,18]]`-輸出：`[[1,6],[8,10],[15,18]]`-解釋：區(qū)間`[1,3]`和`[2,6]`重疊，合并為`[1,6]`要求：-合并后的區(qū)間按起始位置升序排列-不能有重復(fù)區(qū)間題目3：?jiǎn)卧~搜索（20分）問題描述：給定一個(gè)`mxn`的字符矩陣`board`和一個(gè)字符串`word`，判斷`word`是否存在于`board`中。每個(gè)格子可以且只能使用一次。示例：-輸入：`board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word="ABCCED"`-輸出：`true`-解釋：如上圖所示要求：-可以使用回溯算法-考慮所有可能的路徑2.數(shù)據(jù)結(jié)構(gòu)題（共2題，每題25分）題目4：二叉樹的最大深度（25分）問題描述：給定一個(gè)二叉樹的根節(jié)點(diǎn)`root`，返回其最大深度。二叉樹的深度為根節(jié)點(diǎn)到最底層葉節(jié)點(diǎn)的最大路徑長(zhǎng)度。示例：-輸入：`[3,9,20,null,null,15,7]`-輸出：`3`-解釋：最大深度從根到葉節(jié)點(diǎn)`[3,9,15]`或`[3,9,7]`要求：-可以使用遞歸或迭代方法-處理空樹的情況（深度為0）題目5：LRU緩存機(jī)制（25分）問題描述：設(shè)計(jì)一個(gè)LRU（最近最少使用）緩存機(jī)制。它應(yīng)該支持以下操作：-`LRUCache(intcapacity)`：初始化緩存容量為`capacity`-`get(intkey)`：如果鍵存在，則返回其值，否則返回`-1`-`put(intkey,intvalue)`：如果鍵存在，則更新其值；如果鍵不存在，則添加鍵值對(duì)。當(dāng)緩存容量已滿時(shí)，刪除最近最少使用的緩存項(xiàng)示例：-初始化`LRUCache(2)`-`put(1,1)`-`put(2,2)`-`get(1)`返回`1`-`put(3,3)`（容量已滿，刪除鍵`2`）-`get(2)`返回`-1`要求：-使用哈希表和雙向鏈表實(shí)現(xiàn)-`get`和`put`操作的時(shí)間復(fù)雜度為O(1)3.編碼實(shí)現(xiàn)題（共3題，每題25分）題目6：移動(dòng)零（25分）問題描述：給定一個(gè)數(shù)組`nums`，原地修改該數(shù)組，將所有`0`移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對(duì)順序。示例：-輸入：`[0,1,0,3,12]`-輸出：`[1,3,12,0,0]`要求：-不能使用額外空間-只允許用常數(shù)個(gè)額外空間題目7：字符串轉(zhuǎn)換整數(shù)（25分）問題描述：實(shí)現(xiàn)一個(gè)`myAtoi`函數(shù)，將字符串`s`轉(zhuǎn)換為整數(shù)。轉(zhuǎn)換規(guī)則如下：-忽略前導(dǎo)空格-如果第一個(gè)非空字符是正號(hào)或負(fù)號(hào)，記錄符號(hào)-從第一個(gè)非空字符開始，讀取字符直到遇到非數(shù)字字符或字符串結(jié)束-如果沒有數(shù)字字符，返回`0`-最終結(jié)果可能為正或負(fù)，確保結(jié)果在`32位有符號(hào)整數(shù)`范圍內(nèi)（即`-2^31`到`2^31-1`）示例：-輸入：`"-42"`-輸出：`-42`-解釋：忽略前導(dǎo)空格，第一個(gè)非空字符是`-`，接下來是數(shù)字`42`要求：-處理溢出情況（如`"21474836460"`應(yīng)返回`2147483647`）-考慮所有邊界條件題目8：有效括號(hào)（25分）問題描述：給定一個(gè)字符串`s`，判斷它是否是一個(gè)有效的括號(hào)字符串。有效括號(hào)字符串需滿足：-只包含字符`'('`,`')'`,`{'}`,`'}'`,`'['`,`']'`-左括號(hào)必須與相同類型的右括號(hào)匹配-括號(hào)必須正確嵌套示例：-輸入：`"()"`→`true`-輸入：`"()[]{}"`→`true`-輸入：`"(]"`→`false`要求：-使用?；蚬１韺?shí)現(xiàn)-時(shí)間復(fù)雜度O(n)答案答案1：最長(zhǎng)有效括號(hào)（20分）思路：使用棧記錄括號(hào)的索引位置。遍歷字符串，當(dāng)遇到`'('`時(shí)壓入棧，遇到`')'`時(shí)彈出棧頂。如果棧為空，則當(dāng)前`')'`沒有匹配的`'('`；否則，當(dāng)前有效括號(hào)的長(zhǎng)度為`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：合并區(qū)間（20分）思路：首先按區(qū)間的起始位置排序，然后遍歷區(qū)間列表，合并所有重疊的區(qū)間。代碼（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：?jiǎn)卧~搜索（20分）思路：使用回溯算法，遍歷每個(gè)格子，嘗試按上下左右方向搜索。使用`visited`數(shù)組記錄已訪問的格子，避免重復(fù)使用。代碼（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分）思路：使用遞歸方法，計(jì)算左子樹和右子樹的最大深度，取較大值加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緩存機(jī)制（25分）思路：使用雙向鏈表和哈希表實(shí)現(xiàn)。雙向鏈表頭部為最近使用節(jié)點(diǎn)，尾部為最久未使用節(jié)點(diǎn)。哈希表存儲(chǔ)鍵到鏈表節(jié)點(diǎn)的映射。代碼（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：移動(dòng)零（25分）思路：雙指針方法。一個(gè)指針用于遍歷，另一個(gè)指針記錄非零元素的位置。遍歷時(shí)將非零元素依次移動(dòng)到前面。代碼（Python）：pythondefmoveZeroes(nums):left=0forrightinrange(len(nums)):ifnums[right]!=0:nums[left],nums[right]=nums[right],nums[left]left+=1答案7：字符串轉(zhuǎn)換整數(shù)（25分）思路：按規(guī)則逐步處理字符串，注意邊界條件。使用`int`轉(zhuǎn)換時(shí)處理溢出。代碼（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：有效括號(hào)（25分）思路：使用棧存儲(chǔ)左括號(hào)，遇到右括號(hào)時(shí)與棧頂匹配。如果匹配則彈出，否則無效。代碼（Python）：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stac