2026年程序员面试算法题集及解答技巧

2026年程序员面试算法题集及解答技巧1.数组与字符串问题（3题，每题10分）题目1（10分）给定一个包含重复数字的数组，返回所有不重复的全排列。例如，输入`[1,1,2]`，返回`[[1,1,2],[1,2,1],[2,1,1]]`。题目2（10分）实现一个函数，判断一个字符串是否是另一个字符串的子序列。例如，`isSubsequence("abc","ahbgdc")`返回`true`，`isSubsequence("axc","ahbgdc")`返回`false`。题目3（10分）给定一个字符串，找到最长的不含重复字符的子串长度。例如，`longestSubstring("abcabcbb")`返回`3`（"abc"`）。2.哈希表问题（2题，每题15分）题目4（15分）设计一个LRU（最近最少使用）缓存系统，支持`get`和`put`操作。`get(key)`返回键对应的值，如果不存在返回`-1`。`put(key,value)`将键值对插入缓存，如果键已存在，则更新其值。缓存容量为固定大小，超出时删除最久未使用的项。题目5（15分）给定一个字符串数组，返回其中出现次数超过一半的字符。假设一定存在这样的字符。3.树与图问题（3题，每题12分）题目6（12分）给定一个二叉树，判断它是否是平衡二叉树。一个二叉树每个节点的左右子树的深度差不超过1。题目7（12分）给定一个无向图，找到其最小生成树。可以使用Prim或Kruskal算法实现。题目8（12分）给定一个二叉搜索树，实现`BSTIterator`类，支持按中序遍历顺序逐个返回节点的值。例如：pythonclassBSTIterator:def__init__(self,root:TreeNode):初始化代码defnext(self)->int:返回下一个值defhasNext(self)->bool:返回是否还有下一个值4.动态规划问题（2题，每题20分）题目9（20分）给定一个整数数组，表示股票价格，设计一个算法找出最大利润。你可以选择在任意一天买入，并在之后的任意一天卖出。返回最大利润，如果没有利润返回0。例如，`maxProfit([7,1,5,3,6,4])`返回`5`（买入1，卖出6）。题目10（20分）给定一个字符串，找出不重叠的子串的最大数量。子串不能重新排序，但可以删除某些字符。例如，`maxNumOfSubstrings("abab")`返回`3`（"a","b","a"）。5.排序与搜索问题（2题，每题15分）题目11（15分）给定一个二维矩阵，每行和每列都按升序排列，找出矩阵中第k小的元素。例如，`kthSmallest([[1,5,9],[10,11,13],[12,13,15]],8)`返回`13`。题目12（15分）实现二分查找的变体：给定一个升序数组和一个目标值，返回目标值第一次出现的索引。如果不存在返回`-1`。例如，`searchFirstOccurrence([1,2,2,2,3,4,5],2)`返回`1`。答案与解析答案1（10分）使用回溯法，但需要处理重复元素。可以排序数组，然后跳过重复的元素。pythondefpermuteUnique(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()res=[]used=[False]len(nums)backtrack([],used,res)returnres解析：排序后通过`used`数组记录已使用的元素，同时跳过相同元素的前一个未使用元素，避免重复排列。答案2（10分）双指针法。一个指针在长字符串中移动，另一个在短字符串中移动。pythondefisSubsequence(s,t):i,j=0,0whilei<len(s)andj<len(t):ifs[i]==t[j]:i+=1j+=1returni==len(s)解析：通过两个指针分别遍历两个字符串，如果`s`中的字符在`t`中按顺序出现，则`i`最终会等于`s`的长度。答案3（10分）滑动窗口法。使用哈希表记录字符最后出现的位置。pythondeflongestSubstring(s):left=0max_len=0last_pos={}fori,charinenumerate(s):ifcharinlast_posandlast_pos[char]>=left:left=last_pos[char]+1last_pos[char]=imax_len=max(max_len,i-left+1)returnmax_len解析：通过滑动窗口维护不重复的子串，当遇到重复字符时移动窗口的左边界。答案4（15分）使用双向链表+哈希表实现LRU。pythonclassLRUCache:classNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=Nonedef__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=self.Node(0,0)self.tail=self.Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_front(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_front(node)else:node=self.Node(key,value)self.cache[key]=nodeself._add_to_front(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove_node(lru)delself.cache[lru.key]def_move_to_front(self,node):self._remove_node(node)self._add_to_front(node)def_add_to_front(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_node解析：双向链表维护访问顺序，哈希表记录键到节点的映射。`get`操作将节点移动到头部，`put`操作在头部插入新节点，如果超出容量则删除尾部节点。答案5（15分）哈希表记录每个字符的出现次数。pythondefmajorityElement(nums):count={}fornuminnums:count[num]=count.get(num,0)+1ifcount[num]>len(nums)//2:returnnumreturn-1解析：遍历数组时记录每个字符的出现次数，一旦某个字符的出现次数超过数组长度的一半，立即返回。答案6（12分）判断二叉树是否平衡，需要递归检查每个节点的左右子树高度差不超过1，且左右子树都是平衡的。pythonclassSolution:defisBalanced(self,root:TreeNode)->bool: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)<=1_,balanced=check(root)returnbalanced解析：递归计算每个节点的高度，同时检查左右子树是否平衡。如果任何子树不平衡或高度差超过1，则整棵树不平衡。答案7（12分）使用Kruskal算法实现最小生成树。pythonclassUnionFind:def__init__(self,n):self.parent=list(range(n))deffind(self,x):ifself.parent[x]!=x:self.parent[x]=self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):fx,fy=self.find(x),self.find(y)iffx!=fy:self.parent[fy]=fxdefminimumSpanningTree(n,edges):edges.sort(key=lambdax:x[2])uf=UnionFind(n)mst=[]foru,v,winedges:ifuf.find(u)!=uf.find(v):uf.union(u,v)mst.append((u,v,w))returnmst解析：Kruskal算法通过按边权重排序，然后依次合并不形成环的边。Union-Find数据结构用于检测环。答案8（12分）使用栈实现中序遍历。pythonclassBSTIterator:def__init__(self,root:TreeNode):self.stack=[]self._push_left(root)defnext(self)->int:ifnotself.hasNext():return-1node=self.stack.pop()ifnode.right:self._push_left(node.right)returnnode.valdefhasNext(self)->bool:returnlen(self.stack)>0def_push_left(self,node):whilenode:self.stack.append(node)node=node.left解析：通过栈记录遍历过程，`next`方法返回栈顶元素并继续遍历右子树，`hasNext`检查栈是否为空。答案9（20分）动态规划。记录到当前天为止的最大利润。pythondefmaxProfit(prices):ifnotprices:return0min_price=prices[0]max_profit=0foriinrange(1,len(prices)):ifprices[i]<min_price:min_price=prices[i]elifprices[i]-min_price>max_profit:max_profit=prices[i]-min_pricereturnmax_profit解析：遍历价格数组，记录当前最低价格，并计算当前价格与最低价格的差值，更新最大利润。答案10（20分）贪心算法。从左到右遍历，每次选择不重叠的子串。pythondefmaxNumOfSubstrings(s):n=len(s)intervals=[]foriinrange(n):min_char=max_char=s[i]forjinrange(i,n):min_char=min(min_char,s[j])max_char=max(max_char,s[j])iford(min_char)<=ord(max_char):intervals.append((i,j))breakintervals.sort(key=lambdax:x[1])count=0end=-1forstart,end_iinintervals:ifstart>end:count+=1end=end_ireturncount解析：对于每个字符，找到包含它的最小和最大字符范围，确保不重叠。然后按结束位置排序，选择不重叠的子串。答案11（15分）二分查找结合计数。pythondefkthSmallest(matrix,k):n=len(matrix)defcount_less_equal(x):count=0row,col=n-1,0whilerow