程序员面试中常见的算法问题解析

2026年程序员面试中常见的算法问题解析一、数组与字符串问题（共5题，每题8分）1.题目：给定一个包含重复数字的数组，返回所有不重复的全排列。例如，输入`[1,1,2]`，输出`[[1,1,2],[1,2,1],[2,1,1]]`。要求：不能使用库函数，时间复杂度尽可能低。2.题目：实现一个函数，判断一个字符串是否是另一个字符串的子串，忽略大小写。例如，`isSubstring("Hello","lo")`返回`true`。要求：不能使用库函数，空间复杂度O(1)。3.题目：给定一个字符串，找到所有唯一字符的最长子串长度。例如，`"abcabcbb"`的最长无重复字符子串是`"abc"`，返回`3`。要求：时间复杂度O(n)，空间复杂度O(1)。4.题目：实现一个函数，将字符串中的每个字母移动到下一个字母（'z'变为'a'），其他字符不变。例如，`nextLetter("abcz")`返回`"bcda"`。要求：不能使用库函数，时间复杂度O(n)。5.题目：给定一个包含字母和数字的字符串，统计每个字母出现的次数，并按字母顺序排序。例如，`"aabbc"`返回`{'a':2,'b':2,'c':1}`。要求：不能使用库函数，时间复杂度O(nlogn)。二、链表问题（共4题，每题10分）1.题目：实现一个链表，包含头节点，支持`addFirst`和`addLast`操作。要求：时间复杂度O(1)，空间复杂度O(1)。2.题目：删除链表的倒数第n个节点。例如，给定链表`1->2->3->4->5`和`n=2`，返回`1->2->3->5`。要求：不能使用额外空间，时间复杂度O(n)。3.题目：判断链表是否存在环，并返回环的入口节点。例如，`1->2->3->2`存在环，返回`2`。要求：不能使用额外空间，时间复杂度O(n)。4.题目：合并两个有序链表，返回合并后的有序链表。例如，`1->3->5`和`2->4->6`，返回`1->2->3->4->5->6`。要求：时间复杂度O(n)，空间复杂度O(1)。三、栈与队列问题（共3题，每题9分）1.题目：用栈实现队列。即支持`enqueue`和`dequeue`操作。要求：时间复杂度O(1)，空间复杂度O(n)。2.題目：用队列实现栈。即支持`push`和`pop`操作。要求：时间复杂度O(1)，空间复杂度O(n)。3.题目：给定一个表达式，用两个栈判断括号是否匹配。例如，`"(()())"`返回`true`，`"(()"`返回`false`。要求：不能使用库函数，时间复杂度O(n)。四、树与图问题（共4题，每题10分）1.题目：二叉树的最大深度。例如，`[3,9,20,null,null,15,7]`的最大深度是`3`。要求：递归或迭代均可，时间复杂度O(n)。2.题目：二叉树的层序遍历。例如，`[3,9,20,null,null,15,7]`的层序遍历是`[3,9,20,15,7]`。要求：使用队列，时间复杂度O(n)。3.题目：给定一个无向图，判断是否存在环。例如，`[[1,2],[2,3],[3,4],[4,2]]`存在环。要求：使用深度优先搜索，时间复杂度O(n)。4.题目：二叉搜索树的最小深度。例如，`[2,2,5,null,null,5,null,4]`的最小深度是`2`。要求：递归或迭代均可，时间复杂度O(n)。五、动态规划问题（共3题，每题12分）1.题目：给定一个整数数组，返回连续子数组的最大和。例如，`[-2,1,-3,4,-1,2,1,-5,4]`的最大和是`6`（`[4,-1,2,1]`）。要求：时间复杂度O(n)，空间复杂度O(1)。2.题目：爬楼梯问题。给定`n`阶楼梯，每次可以爬1或2阶，返回爬到顶部的方案数。例如，`n=3`的方案数是`3`。要求：动态规划，时间复杂度O(n)，空间复杂度O(1)。3.题目：最长公共子序列。给定两个字符串，返回它们的最长公共子序列。例如，`"abcde"`和`"ace"`的最长公共子序列是`"ace"`。要求：动态规划，时间复杂度O(mn)，空间复杂度O(mn)。六、贪心算法问题（共3题，每题12分）1.题目：给定一个非负数组，每个元素代表爬楼梯的步数，返回最少需要多少步可以爬到顶部。例如，`[2,3,1,1,4]`的最少步数是`2`（`1->2`或`1->1->2`）。要求：贪心算法，时间复杂度O(n)，空间复杂度O(1)。2.题目：区间调度问题。给定若干区间，选择最多不重叠的区间。例如，`[[1,3],[2,4],[3,5]]`可以选择`[1,3]`和`[3,5]`。要求：贪心算法，时间复杂度O(nlogn)。3.题目：分数背包问题。给定若干物品，每个物品有价值和重量，背包容量为`W`，返回最大总价值。例如，`[[60,10],[100,20],[120,30]]`，`W=50`，最大价值是`180`（选择`60`和`120`）。要求：贪心算法，时间复杂度O(nlogn)。七、数学与位运算问题（共3题，每题9分）1.题目：判断一个数是否是2的幂。例如，`4`是，`5`不是。要求：不能使用库函数，时间复杂度O(1)。2.题目：给定一个数`n`，计算`n!`的末尾有多少个0。例如，`10!`的末尾有`2`个0。要求：时间复杂度O(logn)。3.题目：交换两个数的值，不能使用临时变量。例如，`a=5`，`b=10`，交换后`a=10`，`b=5`。要求：位运算，时间复杂度O(1)。答案与解析一、数组与字符串问题1.全排列：思路：回溯法。使用哈希集合记录已使用的数字，避免重复。代码：pythondefpermuteUnique(nums):res=[]used=[False]len(nums)defbacktrack(path):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)path.pop()used[i]=Falsenums.sort()backtrack([])returnres2.判断子串：思路：滑动窗口。忽略大小写后比较。代码：pythondefisSubstring(s1,s2):s1,s2=s1.lower(),s2.lower()iflen(s2)>len(s1):returnFalseforiinrange(len(s1)-len(s2)+1):ifs1[i:i+len(s2)]==s2:returnTruereturnFalse3.最长无重复子串：思路：滑动窗口。使用哈希集合记录字符，移动右指针。代码：pythondeflengthOfLongestSubstring(s):char_set=set()left=0max_len=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_len4.字母移动：思路：遍历字符串，将字母转换为下一个字母。代码：pythondefnextLetter(s):res=[]forcins:if'a'<=c<='z':res.append(chr(ord(c)+1)ifc!='z'else'a')elif'A'<=c<='Z':res.append(chr(ord(c)+1)ifc!='Z'else'A')else:res.append(c)return''.join(res)5.字母统计排序：思路：遍历字符串统计字母，排序后返回字典。代码：pythondefletterCount(s):count={}forcins:ifc.isalpha():count[c]=count.get(c,0)+1sorted_count=dict(sorted(count.items()))returnsorted_count二、链表问题1.链表操作：思路：使用头尾指针。代码：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextclassMyLinkedList:def__init__(self):self.head=ListNode(0)self.tail=self.headdefaddFirst(self,val):node=ListNode(val)node.next=self.head.nextself.head.next=nodeifself.tail==self.head:self.tail=nodedefaddLast(self,val):node=ListNode(val)self.tail.next=nodeself.tail=node2.删除倒数第n个节点：思路：快慢指针。代码：pythondefremoveNthFromEnd(head,n):dummy=ListNode(0,head)fast=slow=dummyfor_inrange(n+1):fast=fast.nextwhilefast:fast=fast.nextslow=slow.nextslow.next=slow.next.nextreturndummy.next3.判断环：思路：快慢指针。代码：pythondefdetectCycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone4.合并有序链表：思路：递归或迭代。代码：pythondefmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1orl2returndummy.next三、栈与队列问题1.栈实现队列：思路：使用两个栈，一个用于入队，一个用于出队。代码：pythonclassMyQueue:def__init__(self):self.in_stack=[]self.out_stack=[]defpush(self,x):self.in_stack.append(x)defpop(self):self.move()returnself.out_stack.pop()defmove(self):ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())2.队列实现栈：思路：使用两个队列，一个用于入队，一个用于出队。代码：pythonclassMyStack:def__init__(self):self.in_queue=[]self.out_queue=[]defpush(self,x):self.in_queue.append(x)defpop(self):self.move()returnself.out_queue.pop(0)defmove(self):ifnotself.out_queue:whileself.in_queue:self.out_queue.append(self.in_queue.pop(0))self.in_queue,self.out_queue=self.out_queue,self.in_queue3.括号匹配：思路：栈。代码：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcins:ifcinmapping:ifstackandstack[-1]==mapping[c]:stack.pop()else:returnFalseelse:stack.append(c)returnnotstack四、树与图问题1.二叉树最大深度：递归：pythondefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))迭代：pythondefmaxDepth(root):ifnotroot:return0queue=[root]depth=0whilequeue:level_size=len(queue)for_inrange(level_size):node=queue.pop(0)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)depth+=1returndepth2.层序遍历：pythondeflevelOrder(root):ifnotroot:return[]queue=[root]res=[]whilequeue:node=queue.pop(0)res.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnres3.图的环判断：pythondefhasCycle(graph):visited=set()rec_stack=set()defdfs(node):ifnodeinrec_stack:returnTrueifnodeinvisited:returnFalsevisited.add(node)rec_stack.add(node)forneighboringraph[node]:ifdfs(neighbor):returnTruerec_stack.remove(node)returnFalsefornodeingraph:ifdfs(node):returnTruereturnFalse4.二叉搜索树最小深度：pythondefminDepth(root):ifnotroot:return0ifnotroot.left:return1+minDepth(root.right)ifnotroot.right:return1+minDepth(root.left)return1+min(minDepth(root.left),minDepth(root.right))五、动态规划问题1.最大子数组和：pythondefmaxSubArray(nums):max_sum=nums[0]current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum2.爬楼梯：pythondefclimbStairs(n):ifn==1:return1dp=[0](n+1)dp[1],dp[2]=1,2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]3.最长公共子序列：pythondeflongestCommonSubsequence(text1,text2):m,n=len(text1),len(text2)dp=[[0](n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):iftext1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])return