2025年螞蟻算法筆試題及答案題目1：字符串處理與密碼驗(yàn)證題目描述在一個(gè)在線系統(tǒng)中，用戶注冊時(shí)需要設(shè)置密碼。密碼需要滿足以下規(guī)則：1.長度至少為8個(gè)字符。2.至少包含一個(gè)大寫字母、一個(gè)小寫字母和一個(gè)數(shù)字。3.不能包含連續(xù)重復(fù)的字符（例如，“aa”是不允許的）。給定一個(gè)字符串表示用戶輸入的密碼，編寫一個(gè)函數(shù)來驗(yàn)證該密碼是否符合上述規(guī)則。如果符合，返回`True`；否則，返回`False`。代碼實(shí)現(xiàn)```pythondefis_valid_password(password):檢查長度是否至少為8iflen(password)<8:returnFalsehas_upper=Falsehas_lower=Falsehas_digit=Falseforiinrange(len(password)):ifpassword[i].isupper():has_upper=Trueelifpassword[i].islower():has_lower=Trueelifpassword[i].isdigit():has_digit=True檢查是否有連續(xù)重復(fù)字符ifi>0andpassword[i]==password[i1]:returnFalse檢查是否包含大寫、小寫字母和數(shù)字returnhas_upperandhas_lowerandhas_digit測試示例password1="Abc1defg"print(is_valid_password(password1))password2="abcdefg1"print(is_valid_password(password2))password3="AAbc1def"print(is_valid_password(password3))```復(fù)雜度分析時(shí)間復(fù)雜度：$O(n)$，其中$n$是密碼的長度。因?yàn)橹恍枰闅v一次密碼字符串?？臻g復(fù)雜度：$O(1)$，只使用了常數(shù)級(jí)的額外空間。題目2：數(shù)組排序與中位數(shù)計(jì)算題目描述給定兩個(gè)已排序的整數(shù)數(shù)組`nums1`和`nums2`，請找出這兩個(gè)數(shù)組合并后的中位數(shù)。代碼實(shí)現(xiàn)```pythondeffindMedianSortedArrays(nums1,nums2):nums=sorted(nums1+nums2)n=len(nums)ifn%2==0:return(nums[n//21]+nums[n//2])/2else:returnnums[n//2]測試示例nums1=[1,3]nums2=[2]print(findMedianSortedArrays(nums1,nums2))nums3=[1,2]nums4=[3,4]print(findMedianSortedArrays(nums3,nums4))```復(fù)雜度分析時(shí)間復(fù)雜度：$O((m+n)log(m+n))$，其中$m$和$n$分別是`nums1`和`nums2`的長度。主要是排序操作的時(shí)間復(fù)雜度。空間復(fù)雜度：$O(m+n)$，需要合并兩個(gè)數(shù)組并存儲(chǔ)在一個(gè)新的數(shù)組中。題目3：圖的最短路徑問題題目描述給定一個(gè)無向圖，圖中每個(gè)節(jié)點(diǎn)表示一個(gè)城市，每條邊表示兩個(gè)城市之間的道路，邊的權(quán)重表示道路的長度。請使用Dijkstra算法找出從指定起點(diǎn)到指定終點(diǎn)的最短路徑長度。代碼實(shí)現(xiàn)```pythonimportheapqdefdijkstra(graph,start,end):distances={node:float('inf')fornodeingraph}distances[start]=0priority_queue=[(0,start)]whilepriority_queue:current_distance,current_node=heapq.heappop(priority_queue)ifcurrent_node==end:returncurrent_distanceifcurrent_distance>distances[current_node]:continueforneighbor,weightingraph[current_node].items():distance=current_distance+weightifdistance<distances[neighbor]:distances[neighbor]=distanceheapq.heappush(priority_queue,(distance,neighbor))return-1測試示例graph={'A':{'B':1,'C':4},'B':{'A':1,'C':2,'D':5},'C':{'A':4,'B':2,'D':1},'D':{'B':5,'C':1}}start='A'end='D'print(dijkstra(graph,start,end))```復(fù)雜度分析時(shí)間復(fù)雜度：$O((V+E)logV)$，其中$V$是節(jié)點(diǎn)數(shù)，$E$是邊數(shù)。主要是優(yōu)先隊(duì)列操作的時(shí)間復(fù)雜度?？臻g復(fù)雜度：$O(V)$，主要用于存儲(chǔ)距離數(shù)組和優(yōu)先隊(duì)列。題目4：二叉樹的層序遍歷題目描述給定一個(gè)二叉樹的根節(jié)點(diǎn)`root`，返回其節(jié)點(diǎn)值的層序遍歷結(jié)果（即從左到右，逐層遍歷）。代碼實(shí)現(xiàn)```python定義二叉樹節(jié)點(diǎn)類classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevelOrder(root):ifnotroot:return[]result=[]queue=[root]whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.pop(0)current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult測試示例root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)print(levelOrder(root))```復(fù)雜度分析時(shí)間復(fù)雜度：$O(n)$，其中$n$是二叉樹的節(jié)點(diǎn)數(shù)。每個(gè)節(jié)點(diǎn)都會(huì)被訪問一次?？臻g復(fù)雜度：$O(m)$，其中$m$是二叉樹中節(jié)點(diǎn)數(shù)最多的一層的節(jié)點(diǎn)數(shù)。主要用于隊(duì)列的空間。題目5：動(dòng)態(tài)規(guī)劃之背包問題題目描述有一個(gè)容量為$W$的背包和$n$個(gè)物品，每個(gè)物品有一個(gè)重量$weights[i]$和一個(gè)價(jià)值$values[i]$。請選擇一些物品放入背包中，使得背包中物品的總價(jià)值最大，且總重量不超過背包的容量。代碼實(shí)現(xiàn)```pythondefknapsack(W,weights,values):n=len(weights)dp=[[0for_inrange(W+1)]for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,W+1):ifweights[i1]<=w:dp[i][w]=max(values[i1]+dp[i1][wweights[i1]],dp[i1][w])else:dp[i][w]=dp[i1][w]returndp[n][W]測試示例W=5weights=[2,3,4]values=[3,4,5]print(knapsack(W,weights,values))```復(fù)雜度分析時(shí)間復(fù)雜度：$O(nW)$，其中$n$是物品數(shù)，$W$是背包容量。需要填充一個(gè)$n\timesW$的二維數(shù)組?？臻g復(fù)雜度：$O(nW)$，主要用于存儲(chǔ)動(dòng)態(tài)規(guī)劃數(shù)組。題目6：字符串匹配之KMP算法題目描述給定一個(gè)文本字符串`text`和一個(gè)模式字符串`pattern`，請使用KMP（Knuth-Morris-Pratt）算法找出模式字符串在文本字符串中第一次出現(xiàn)的位置。如果未找到，返回-1。代碼實(shí)現(xiàn)```pythondefcompute_lps(pattern):m=len(pattern)lps=[0]mlength=0i=1whilei<m:ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length1]else:lps[i]=0i+=1returnlpsdefkmp_search(text,pattern):n=len(text)m=len(pattern)lps=compute_lps(pattern)i=0j=0whilei<n:ifpattern[j]==text[i]:i+=1j+=1ifj==m:returnijelifi<nandpattern[j]!=text[i]:ifj!=0:j=lps[j1]else:i+=1return-1測試示例text="ABABDABACDABABCABAB"pattern="ABABCABAB"print(kmp_search(text,pattern))```復(fù)雜度分析時(shí)間復(fù)雜度：$O(n+m)$，其中$n$是文本字符串的長度，$m$是模式字符串的長度?？臻g復(fù)雜度：$O(m)$，主要用于存儲(chǔ)最長前綴后綴數(shù)組。題目7：鏈表的反轉(zhuǎn)題目描述給定一個(gè)單鏈表的頭節(jié)點(diǎn)`head`，請反轉(zhuǎn)該鏈表并返回反轉(zhuǎn)后的鏈表頭節(jié)點(diǎn)。代碼實(shí)現(xiàn)```python定義鏈表節(jié)點(diǎn)類classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev測試示例創(chuàng)建鏈表1->2->3head=ListNode(1)head.next=ListNode(2)head.next.next=ListNode(3)reversed_head=reverseList(head)whilereversed_head:print(reversed_head.val,end="->"ifreversed_head.nextelse"\n")reversed_head=reversed_head.next```復(fù)雜度分析時(shí)間復(fù)雜度：$O(n)$，其中$n$是鏈表的長度。需要遍歷鏈表一次?？臻g復(fù)雜度：$O(1)$，只使用了常數(shù)級(jí)的額外空間。題目8：股票買賣問題題目描述給定一個(gè)數(shù)組`prices`，其中`prices[i]`表示第$i$天的股票價(jià)格。你可以進(jìn)行多次買賣交易，但在再次購買之前必須先賣出手中的股票。請計(jì)算你能獲得的最大利潤。代碼實(shí)現(xiàn)```pythondefmaxProfit(prices):profit=0foriinrange(1,len(prices)):ifprices[i]>prices[i1]:profit+=prices[i]prices[i1]returnprofit測試示例prices=[7,1,5,3,6,4]print(maxProfit(prices))```復(fù)雜度分析時(shí)間復(fù)雜度：$O(n)$，其中$n$是數(shù)組的長度。只需要遍歷數(shù)組一次?？臻g復(fù)雜度：$O(1)$，只使用了常數(shù)級(jí)的額外空間。題目9：矩陣旋轉(zhuǎn)題目描述給定一個(gè)$n\timesn$的二維矩陣`matrix`，將其順時(shí)針旋轉(zhuǎn)90度。代碼實(shí)現(xiàn)```pythondefrotate(matrix):n=len(matrix)轉(zhuǎn)置矩陣foriinrange(n):forjinrange(i,n):matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]反轉(zhuǎn)每一行foriinrange(n):matrix[i].reverse()returnmatrix測試示例matrix=[[1,2,3],[4,5,6],[7,8,9]]rotated_matrix