2026年实战编程宝典算法面试现场写代码指南

2026年实战编程宝典：算法面试现场写代码指南一、数组与字符串（共5题，每题8分）1.题目：给定一个整数数组`nums`和一个目标值`target`，请找出数组中和为目标值的三元组数量。示例：输入：`nums=[1,2,3,4,5]`,`target=9`输出：`3`（三元组为(1,3,5),(2,3,4),(1,4,4)）2.题目：请实现一个函数`replaceSpaces`，将字符串中的所有空格替换为`%20`。示例：输入：`s="Wearehappy."`输出：`"We%20are%20happy."`3.题目：给定一个字符串`s`，请判断其是否为有效的括号字符串（只包含`()`、`[]`、`{}`，且括号正确匹配）。示例：输入：`s="{[]()}"`输出：`true`4.题目：请实现一个函数`longestSubstring`，返回字符串中不包含重复字符的最长子串长度。示例：输入：`s="abcabcbb"`输出：`3`（最长子串为"abc"）5.题目：给定一个整数数组`nums`，请返回数组中乘积最大的三个数的乘积。示例：输入：`nums=[1,2,3,4]`输出：`24`（最大乘积为342）二、链表（共4题，每题10分）1.题目：请实现一个函数`reverseList`，反转一个单链表。示例：输入：`1->2->3->4`输出：`4->3->2->1`2.题目：给定两个单链表`l1`和`l2`，请合并它们为一个新的单链表，合并后的链表按升序排列。示例：输入：`l1=1->4->5`,`l2=1->3->4`输出：`1->1->3->4->4->5`3.题目：请判断一个链表是否存在环，并返回环的入口节点。示例：输入：`1->2->3->4->2`（存在环，环从节点2开始）输出：`2`4.题目：给定一个单链表`head`，请删除链表中的节点`val`，假设链表中所有值唯一。示例：输入：`head=1->2->3->4`,`val=3`输出：`1->2->4`三、树与二叉搜索树（共4题，每题10分）1.题目：请实现一个函数`inorderTraversal`，非递归遍历二叉树的中序遍历。示例：输入：`root=[1,null,2,3]`（二叉树结构为1->null->2->3）输出：`[1,3,2]`2.题目：给定一个二叉搜索树`root`，请查找其中值最接近`target`的节点，并返回其值。示例：输入：`root=[4,2,5,1,3]`,`target=3.714286`输出：`4`3.题目：请实现一个函数`insertIntoBST`，将一个值插入到二叉搜索树中，并返回插入后的树根。示例：输入：`root=[4,2,7,1,3]`,`val=5`输出：`[4,2,7,1,3,null,null,null,null,null,5]`4.题目：给定一个二叉树`root`，请判断其是否为平衡二叉树（左右子树高度差不超过1）。示例：输入：`root=[3,9,20,null,null,15,7]`输出：`true`四、动态规划（共4题，每题12分）1.题目：给定一个数组`nums`，请返回其中最长的上升子序列的长度。示例：输入：`nums=[10,9,2,5,3,7,101,18]`输出：`4`（最长上升子序列为[2,3,7,101]）2.题目：给定一个整数`n`，请计算`n`的不同子集的数量。示例：输入：`n=5`输出：`32`3.题目：给定一个字符串`s`，请返回其中不同字母排列组合的数量。示例：输入：`s="abc"`输出：`6`（排列组合为"abc","acb","bac","bca","cab","cba"）4.题目：给定一个整数`k`和一个数组`prices`，请计算最多进行`k`次交易（每次交易必须买入再卖出）的最大利润。示例：输入：`prices=[1,2,4,5,2,9]`,`k=2`输出：`13`（第一次交易买入1卖出5，第二次交易买入2卖出9）五、堆与优先队列（共3题，每题10分）1.题目：请实现一个函数`topKFrequent`，返回数组中出现频率最高的`k`个元素。示例：输入：`nums=[1,1,1,2,2,3]`,`k=2`输出：`[1,2]`2.题目：请实现一个函数`mergeKLists`，合并`k`个排序链表，返回合并后的头节点。示例：输入：`lists=[[1,4,5],[1,3,4],[2,6]]`输出：`1->1->2->3->4->4->5->6`3.题目：给定一个整数数组`nums`，请返回其中第`k`大的元素。示例：输入：`nums=[3,2,1,5,6,4]`,`k=2`输出：`5`六、图与广度优先搜索（共3题，每题12分）1.题目：给定一个无向图`graph`（邻接表形式），请判断其是否为二分图（可以用两种颜色染色，相邻节点颜色不同）。示例：输入：`graph=[[1,3],[0,2],[1,3],[0,2]]`输出：`true`2.题目：给定一个`mxn`的网格`grid`，请返回从左上角到右下角的最短路径长度（只能向下或向右移动）。示例：输入：`grid=[[0,0,0],[0,1,0],[0,0,0]]`输出：`2`3.题目：给定一个无向图`graph`（邻接表形式），请返回所有节点的最短路径长度（从节点0开始）。示例：输入：`graph=[[1,2],[0,3],[0,3],[1,2]]`输出：`[0,1,1,2]`答案与解析一、数组与字符串1.答案：pythondefthreeSum(nums,target):nums.sort()n=len(nums)count=0foriinrange(n):left,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:count+=1left+=1right-=1eliftotal<target:left+=1else:right-=1returncount解析：先排序，然后固定一个数，用双指针遍历剩下的两个数，如果和等于目标值则计数，并移动指针避免重复。2.答案：pythondefreplaceSpaces(s):returns.replace('','%20')解析：直接使用字符串的`replace`方法将空格替换为`%20`。3.答案：pythondefisValid(s):stack=[]mapping={'(':')','[':']','{':'}'}forcharins:ifcharinmapping:stack.append(char)else:ifnotstackormapping[stack.pop()]!=char:returnFalsereturnnotstack解析：用栈存储左括号，遇到右括号时检查是否匹配，若不匹配则返回`false`。4.答案：pythondeflongestSubstring(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_len解析：滑动窗口，左指针右移时删除重复字符，右指针右移时添加字符，更新最大长度。5.答案：pythondefmaximumProduct(nums):nums.sort()n=len(nums)returnmax(nums[0]nums[1]nums[-1],nums[-1]nums[-2]nums[-3])解析：最大乘积可能来自前两个最小数和最大数，或后三个最大数，取两者最大值。二、链表1.答案：pythondefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：迭代反转链表，依次将节点指向前一个节点。2.答案：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解析：合并两个有序链表，依次比较节点值，将较小节点连接到结果链表。3.答案：pythondefdetectCycle(head):slow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：快慢指针判断环，若相遇则找到环的入口。4.答案：pythondefdeleteNode(head,val):dummy=ListNode(0)dummy.next=headcurrent=dummywhilecurrent.nextandcurrent.next.val!=val:current=current.nextifcurrent.next:current.next=current.next.nextreturndummy.next解析：用虚拟头节点处理头节点删除的情况，然后查找并删除指定节点。三、树与二叉搜索树1.答案：pythondefinorderTraversal(root):stack,res=[],[]current=rootwhilecurrentorstack:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()res.append(current.val)current=current.rightreturnres解析：非递归中序遍历，用栈记录节点，先遍历左子树，再访问节点，最后遍历右子树。2.答案：pythondefclosestValue(root,target):closest=root.valcurrent=rootwhilecurrent:ifabs(current.val-target)<abs(closest-target):closest=current.valiftarget<current.val:current=current.lefteliftarget>current.val:current=current.rightelse:breakreturnclosest解析：在BST中，根据目标值与节点值的比较方向选择子树，同时更新最接近值。3.答案：pythondefinsertIntoBST(root,val):ifnotroot:returnTreeNode(val)ifval<root.val:root.left=insertIntoBST(root.left,val)else:root.right=insertIntoBST(root.right,val)returnroot解析：递归插入，根据值与当前节点比较方向选择子树，直到找到空位置插入。4.答案：pythondefisBalanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：后序遍历检查每个节点的高度，同时判断左右子树是否平衡。四、动态规划1.答案：pythondeflengthOfLIS(nums):dp=[1]len(nums)foriinrange(1,len(nums)):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)解析：DP数组记录以每个位置结尾的最长上升子序列长度，遍历更新。2.答案：pythondefsubsetsCount(n):return1<<n#2^n解析：每个节点有选或不选两种选择，总子集数量为2^n。3.答案：pythondefpermutationCount(s):frommathimportfactorialcounter={}forcharins:counter[char]=counter.get(char,0)+1result=factorial(len(s))forvincounter.values():result//=factorial(v)returnresult解析：用排列组合公式计算，考虑重复字母的排列数。4.答案：pythondefmaxProfit(prices,k):ifnotpricesork==0:return0dp=[[0](k+1)for_inrange(2)]for_inrange(k):dp[1][_]=-prices[0]foriinrange(1,len(prices)):dp[i%2][0]=0forjinrange(1,k+1):dp[i%2][j]=max(dp[(i-1)%2][j],dp[(i-1)%2][j-1]+prices[i])returndp[(len(prices)-1)%2][k]解析：状态转移方程，用滚动数组优化空间，记录第i天第j次交易的最大利润。五、堆与优先队列1.答案：pythondeftopKFrequent(nums,k):fromcollectionsimportCountercount=Counter(nums)heap=[]fornum,freqincount.items():heapq.heappush(heap,(-freq,num))iflen(heap)>k:heapq.heappop(heap)return[numfor_,numinheap]解析：用最小堆维护前k个高频元素，堆大小限制为k。2.答案：pythondefmergeKLists(lists):min_heap=[]fori,headinenumerate(lists):ifhead:heapq.heappush(min_heap,(head.val,i,head))dummy=ListNode(0)current=dummywhilemin_heap:_,i,node=heapq.heappop(min_heap)current.next=nodecurrent=current.nextifnode.next:heapq.heappush(min_heap,(node.next.val,i,node.next))returndummy.next解析：用最小堆维护k个链表头部，每次弹出最小节点并推进下一个节点。3.答案：pythondeffindKthLargest(nums,k):importheapqreturnheapq.nlargest(k,nums)[-1]解析：用`nlargest`获取前k大元素，取最后一个即为第k大。六、图与广度优先搜索1.答案：pythondefisBipartite(graph):color={}fornodeinrange(len(graph)):ifnodenotincolor:color[node]=0queue=[node]whilequeue:current=queue.pop(0)forneighboringraph[current]:ifneighborincolor:ifcolor[neighbor]==color[current]:returnFalseelse:color[neighbor]=1-color[current]queue.append(neighbor)