2025年蚂蚁算法笔试题及答案

2025年蚂蚁算法笔试题及答案题目1：字符串处理与密码验证题目描述在一个在线系统中，用户注册时需要设置密码。密码需要满足以下规则：1.长度至少为8个字符。2.至少包含一个大写字母、一个小写字母和一个数字。3.不能包含连续重复的字符（例如，“aa”是不允许的）。给定一个字符串表示用户输入的密码，编写一个函数来验证该密码是否符合上述规则。如果符合，返回`True`；否则，返回`False`。代码实现```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检查是否有连续重复字符ifi>0andpassword[i]==password[i1]:returnFalse检查是否包含大写、小写字母和数字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))```复杂度分析时间复杂度：$O(n)$，其中$n$是密码的长度。因为只需要遍历一次密码字符串。空间复杂度：$O(1)$，只使用了常数级的额外空间。题目2：数组排序与中位数计算题目描述给定两个已排序的整数数组`nums1`和`nums2`，请找出这两个数组合并后的中位数。代码实现```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))```复杂度分析时间复杂度：$O((m+n)log(m+n))$，其中$m$和$n$分别是`nums1`和`nums2`的长度。主要是排序操作的时间复杂度。空间复杂度：$O(m+n)$，需要合并两个数组并存储在一个新的数组中。题目3：图的最短路径问题题目描述给定一个无向图，图中每个节点表示一个城市，每条边表示两个城市之间的道路，边的权重表示道路的长度。请使用Dijkstra算法找出从指定起点到指定终点的最短路径长度。代码实现```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))```复杂度分析时间复杂度：$O((V+E)logV)$，其中$V$是节点数，$E$是边数。主要是优先队列操作的时间复杂度。空间复杂度：$O(V)$，主要用于存储距离数组和优先队列。题目4：二叉树的层序遍历题目描述给定一个二叉树的根节点`root`，返回其节点值的层序遍历结果（即从左到右，逐层遍历）。代码实现```python定义二叉树节点类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))```复杂度分析时间复杂度：$O(n)$，其中$n$是二叉树的节点数。每个节点都会被访问一次。空间复杂度：$O(m)$，其中$m$是二叉树中节点数最多的一层的节点数。主要用于队列的空间。题目5：动态规划之背包问题题目描述有一个容量为$W$的背包和$n$个物品，每个物品有一个重量$weights[i]$和一个价值$values[i]$。请选择一些物品放入背包中，使得背包中物品的总价值最大，且总重量不超过背包的容量。代码实现```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))```复杂度分析时间复杂度：$O(nW)$，其中$n$是物品数，$W$是背包容量。需要填充一个$n\timesW$的二维数组。空间复杂度：$O(nW)$，主要用于存储动态规划数组。题目6：字符串匹配之KMP算法题目描述给定一个文本字符串`text`和一个模式字符串`pattern`，请使用KMP（Knuth-Morris-Pratt）算法找出模式字符串在文本字符串中第一次出现的位置。如果未找到，返回-1。代码实现```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))```复杂度分析时间复杂度：$O(n+m)$，其中$n$是文本字符串的长度，$m$是模式字符串的长度。空间复杂度：$O(m)$，主要用于存储最长前缀后缀数组。题目7：链表的反转题目描述给定一个单链表的头节点`head`，请反转该链表并返回反转后的链表头节点。代码实现```python定义链表节点类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测试示例创建链表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```复杂度分析时间复杂度：$O(n)$，其中$n$是链表的长度。需要遍历链表一次。空间复杂度：$O(1)$，只使用了常数级的额外空间。题目8：股票买卖问题题目描述给定一个数组`prices`，其中`prices[i]`表示第$i$天的股票价格。你可以进行多次买卖交易，但在再次购买之前必须先卖出手中的股票。请计算你能获得的最大利润。代码实现```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))```复杂度分析时间复杂度：$O(n)$，其中$n$是数组的长度。只需要遍历数组一次。空间复杂度：$O(1)$，只使用了常数级的额外空间。题目9：矩阵旋转题目描述给定一个$n\timesn$的二维矩阵`matrix`，将其顺时针旋转90度。代码实现```pythondefrotate(matrix):n=len(matrix)转置矩阵foriinrange(n):forjinrange(i,n):matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]反转每一行foriinrange(n):matrix[i].reverse()returnmatrix测试示例matrix=[[1,2,3],[4,5,6],[7,8,9]]rotated_matrix