程序员面试中常见算法题及答案

2026年程序员面试中常见算法题及答案一、数组与字符串（共5题，每题10分）1.题目：给定一个整数数组，返回数组中重复次数最多的元素。如果存在多个元素重复次数相同，返回其中任意一个即可。答案：pythondeffind_largest_duplicate(nums):fromcollectionsimportCountercount=Counter(nums)max_duplicate=Nonemax_count=0fornum,cntincount.items():ifcnt>max_count:max_duplicate=nummax_count=cntreturnmax_duplicate解析：使用`collections.Counter`统计数组中每个数字的频率，遍历计数器找出出现次数最多的数字。时间复杂度O(n)，空间复杂度O(n)。2.题目：给定一个字符串，判断是否可以通过删除某些字符使其变为回文串。答案：pythondefcan_be_palindrome(s):left,right=0,len(s)-1whileleft<right:ifs[left]!=s[right]:尝试跳过左边或右边的字符skip_left=can_be_palindrome(s[left+1:right+1])skip_right=can_be_palindrome(s[left:right])returnskip_leftorskip_rightleft+=1right-=1returnTrue解析：使用双指针法，当遇到不匹配的字符时，分别尝试跳过左边或右边的字符，递归判断剩余子串是否为回文。时间复杂度O(2^n)，空间复杂度O(n)。对于更优解，可使用动态规划，时间复杂度O(n^2)。3.题目：将一个字符串中的所有大写字母转换为小写字母，所有小写字母转换为大写字母。答案：pythondefswap_case(s):return''.join([char.lower()ifchar.isupper()elsechar.upper()forcharins])解析：遍历字符串，对每个字符判断大小写并转换。Python中`str.isupper()`和`str.lower()`方法可直接使用。时间复杂度O(n)，空间复杂度O(n)。4.题目：给定两个字符串，找出它们的最长公共子串。答案：pythondeflongest_common_substring(s1,s2):m,n=len(s1),len(s2)dp=[[0](n+1)for_inrange(m+1)]max_len=0end=0foriinrange(1,m+1):forjinrange(1,n+1):ifs1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1]+1ifdp[i][j]>max_len:max_len=dp[i][j]end=ireturns1[end-max_len:end]解析：使用动态规划，`dp[i][j]`表示`s1[:i]`和`s2[:j]`的最长公共子串长度。遍历完成后，根据`max_len`和`end`提取子串。时间复杂度O(mn)，空间复杂度O(mn)。5.题目：给定一个包含重复数字的数组，返回所有不重复的全排列。答案：pythondefpermute_unique(nums):defbacktrack(path,used,res):iflen(path)==len(nums):res.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path,used,res)path.pop()used[i]=Falsenums.sort()used=[False]len(nums)res=[]backtrack([],used,res)returnres解析：先对数组排序，然后使用回溯法生成全排列。通过`used`数组记录已使用的数字，并跳过重复的数字。时间复杂度O(n!)，空间复杂度O(n)。二、链表（共5题，每题10分）1.题目：反转一个单链表。答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev解析：使用三指针法：`prev`、`curr`和`next_node`。遍历链表时，逐个反转节点方向。时间复杂度O(n)，空间复杂度O(1)。2.题目：判断一个链表是否存在环。答案：pythondefhas_cycle(head):slow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:returnTruereturnFalse解析：使用快慢指针法，快指针每次走两步，慢指针每次走一步。若存在环，快慢指针必相遇。时间复杂度O(n)，空间复杂度O(1)。3.题目：合并两个有序链表，返回合并后的有序链表。答案：pythondefmerge_two_lists(l1,l2):dummy=ListNode(0)curr=dummywhilel1andl2:ifl1.val<l2.val:curr.next=l1l1=l1.nextelse:curr.next=l2l2=l2.nextcurr=curr.nextcurr.next=l1orl2returndummy.next解析：使用虚拟头节点`dummy`，比较两个链表当前节点的值，按顺序合并。时间复杂度O(n)，空间复杂度O(1)。4.题目：删除链表中的倒数第n个节点。答案：pythondefremove_nth_from_end(head,n):dummy=ListNode(0,head)first=dummysecond=dummyfor_inrange(n+1):first=first.nextwhilefirst:first=first.nextsecond=second.nextsecond.next=second.next.nextreturndummy.next解析：使用双指针法，`first`先走n+1步，然后`first`和`second`同时走，当`first`到达末尾时，`second`指向要删除的前一个节点。时间复杂度O(n)，空间复杂度O(1)。5.题目：将一个单链表分成两个链表，前k个节点为第一个链表，其余为第二个链表。答案：pythondefsplit_list_to_parts(head,k):length=0curr=headwhilecurr:length+=1curr=curr.nextpart_size=length//kextra=length%kres=[]curr=headforiinrange(k):head_part=currsize=part_size+(1ifi<extraelse0)for_inrange(size-1):ifcurr:curr=curr.nextifcurr:next_part=curr.nextcurr.next=Nonecurr=next_partres.append(head_part)returnres解析：计算每个部分的长度：`part_size`为主部分长度，`extra`为多出来的节点数。遍历链表，按部分大小拆分。时间复杂度O(n)，空间复杂度O(1)。三、树（共5题，每题10分）1.题目：二叉树的中序遍历。答案：pythondefinorder_traversal(root):definorder(node):ifnotnode:return[]returninorder(node.left)+[node.val]+inorder(node.right)returninorder(root)解析：递归实现中序遍历（左-根-右）。时间复杂度O(n)，空间复杂度O(n)。2.题目：判断二叉树是否对称。答案：pythondefis_symmetric(root):defis_mirror(left,right):ifnotleftandnotright:returnTrueifnotleftornotright:returnFalsereturn(left.val==right.val)andis_mirror(left.left,right.right)andis_mirror(left.right,right.left)returnis_mirror(root,root)解析：对称二叉树满足：左子树的左子树与右子树的右子树对称，左子树的右子树与右子树的左子树对称。递归判断。时间复杂度O(n)，空间复杂度O(n)。3.题目：给定二叉树的根节点，返回其最大深度。答案：pythondefmax_depth(root):ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))解析：递归计算左子树和右子树的最大深度，取较大值加1。时间复杂度O(n)，空间复杂度O(n)。4.题目：二叉树的层序遍历（广度优先）。答案：pythondeflevel_order(root):ifnotroot:return[]res=[]queue=[root]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres解析：使用队列实现BFS，按层遍历节点。时间复杂度O(n)，空间复杂度O(n)。5.题目：判断二叉树是否是平衡二叉树（每个节点的左右子树高度差不超过1）。答案：pythondefis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)return1+max(left_height,right_height),left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：递归计算每个节点的高度，同时判断左右子树是否平衡。若高度差超过1或子树不平衡，则整棵树不平衡。时间复杂度O(n)，空间复杂度O(n)。四、哈希表（共5题，每题10分）1.题目：给定一个字符串，统计其中每个字符的出现次数。答案：pythondefcount_characters(s):fromcollectionsimportdefaultdictcount=defaultdict(int)forcharins:count[char]+=1returncount解析：使用`defaultdict`统计字符频率。时间复杂度O(n)，空间复杂度O(n)。2.题目：判断两个数组是否包含相同的元素（不考虑顺序）。答案：pythondefcontains_same_elements(arr1,arr2):returnlen(set(arr1))==len(set(arr2))andset(arr1).issubset(set(arr2))解析：将两个数组转换为集合，比较集合大小和子集关系。时间复杂度O(n)，空间复杂度O(n)。3.题目：找到数组中和为特定值的所有索引对。答案：pythondeftwo_sum(nums,target):fromcollectionsimportdefaultdictnum_to_index=defaultdict(int)res=[]fori,numinenumerate(nums):complement=target-numifcomplementinnum_to_index:res.append([num_to_index[complement],i])num_to_index[num]=ireturnres解析：使用哈希表记录数字及其索引，遍历时查找补数。时间复杂度O(n)，空间复杂度O(n)。4.题目：给定一个字符串，判断是否可以通过替换某些字符使其成为另一个字符串的子串。答案：pythondefcan_make_substring(s1,s2):fromcollectionsimportCountercount=Counter(s2)left,right=0,len(s1)foriinrange(len(s1)):count[s1[i]]-=1whilecount[s1[i]]<0:count[s1[left]]+=1left+=1ifi-left+1==len(s2):returnTruereturnFalse解析：滑动窗口法，维护一个长度为s2的窗口，统计窗口内字符频率，与s2比较。时间复杂度O(n)，空间复杂度O(n)。5.题目：找出数组中所有出现至少k次的元素。答案：pythondeffind_k_frequent(nums,k):fromcollectionsimportCountercount=Counter(nums)return[numfornum,freqincount.items()iffreq>=k]解析：使用`Counter`统计频率，筛选出现次数≥k的元素。时间复杂度O(n)，空间复杂度O(n)。五、动态规划（共5题，每题10分）1.题目：斐波那契数列的第n项（n≥0）。答案：pythondeffib(n):ifn==0:return0dp=[0](n+1)dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：动态规划计算斐波那契数列，`dp[i]=dp[i-1]+dp[i-2]`。时间复杂度O(n)，空间复杂度O(n)。2.题目：爬楼梯问题：假设你每次可以爬1或2阶，共有n阶，有多少种爬法？答案：pythondefclimb_stairs(n):dp=[0](n+1)dp[0]=1dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：类似斐波那契数列，`dp[i]=dp[i-1]+dp[i-2]`。时间复杂度O(n)，空间复杂度O(n)。3.题目：给定一个数组，返回其中最长连续递增子序列的长度。答案：pythondeflength_of_lcis(nums):ifnotnums:return0max_len=1current_len=1foriinrange(1,len(nums)):ifnums[i]>nums[i-1]:current_len+=1max_len=max(max_len,current_len)else:current_len=1returnmax_len解析：遍历数组，若当前数字大于前一个，则递增序列长度加1；否则重置为1。时间复杂度O(n)，空间复杂度O(1)。4.题目：给定一个背包容量为W的背包，以及若干物品的重量和价值，返回能装入背包的最大价值。答案：pythondefknapsack(W,weights,values):n=len(weights)dp=[[0](W+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,W+1):ifweights[i-1]<=w:dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])else:dp[i][w]=dp[i-1][w]returndp[n][W]解析：动态规划解背包问题，`dp[i][w]`表示前i个物品在容量为w时的最大价值。时间复杂度O(nW)，空间复杂度O(nW)。5.题目：判断一个字符串是否是另一个字符串的子序列。答案：pythondefis_subsequence(s,t):m,n=len(s),len(t)dp=[[0](n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):ifs[i-1]==t[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=dp[i-1][j]returndp[m][n]==m解析：动态规划解子序列问题，`dp[i][j]`表示`s[:i]`是`t[:j]`的子序列的长度。时间复杂度O(mn)，空间复杂度O(mn)。六、贪心算法（共5题，每题10分）1.题目：给定一个非负整数数组，返回数组中和最大的连续子数组的和。答案：pythondefmax_subarray_sum(nums):max_sum=current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum解析：贪心算法，`current_sum`表示以当前数字结尾的最大子数组和。时间复杂度O(n)，空间复杂度O(1)。2.题目：给定一个由正整数组成的数组，返回将所有数字按顺序排列后可以形成的最大数字。答案：pythondeflargest_number(nums):fromfunctoolsimportcmp_to_keynums=list(map(str,nums))nums.sort(key=cmp_to_key(lambdax,y:int(y+x)-int(x+y)))return''.join(nums)