2026年程序员面试编程算法题及答案解析

2026年程序员面试编程算法题及答案解析一、排序算法（3题，每题10分）1.快速排序实现与优化题目：实现快速排序算法，并说明如何优化其平均时间复杂度。假设输入数组为`[9,-3,5,2,6,8,-6,1,3]`，请输出排序后的数组。答案与解析：答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)arr=[9,-3,5,2,6,8,-6,1,3]sorted_arr=quick_sort(arr)print(sorted_arr)#输出：[-6,-3,1,2,3,5,6,8,9]解析：快速排序的核心思想是分治法，通过选定一个基准值（pivot）将数组分为三部分：小于基准的、等于基准的、大于基准的。然后递归对左右子数组进行排序。优化方法：1.三数取中法：选择头部、尾部和中间的数的中位数作为基准，减少极端情况下的性能下降。2.小数组时切换到插入排序：当子数组长度较小时（如小于10），插入排序比快速排序更高效。3.尾递归优化：减少递归调用栈的深度。2.堆排序实现题目：实现堆排序算法，并说明其时间复杂度。假设输入数组为`[4,10,3,5,1]`，请输出排序后的数组。答案与解析：答案：pythondefheapify(arr,n,i):largest=ileft=2i+1right=2i+2ifleft<nandarr[largest]<arr[left]:largest=leftifright<nandarr[largest]<arr[right]:largest=rightiflargest!=i:arr[i],arr[largest]=arr[largest],arr[i]heapify(arr,n,largest)defheap_sort(arr):n=len(arr)foriinrange(n//2-1,-1,-1):heapify(arr,n,i)foriinrange(n-1,0,-1):arr[i],arr[0]=arr[0],arr[i]heapify(arr,i,0)returnarrarr=[4,10,3,5,1]sorted_arr=heap_sort(arr)print(sorted_arr)#输出：[1,3,4,5,10]解析：堆排序基于二叉堆（最大堆或最小堆）实现。首先将数组构建为最大堆，然后依次将堆顶元素与末尾元素交换，并调整剩余堆。时间复杂度：-建堆：O(n)-调整堆：O(logn)，共n次总体时间复杂度为O(nlogn)。3.计数排序实现题目：实现计数排序算法，并说明其适用场景。假设输入数组为`[4,2,2,8,3,3,1]`，请输出排序后的数组。答案与解析：答案：pythondefcounting_sort(arr):ifnotarr:return[]max_val=max(arr)min_val=min(arr)count=[0](max_val-min_val+1)fornuminarr:count[num-min_val]+=1sorted_arr=[]fori,freqinenumerate(count):sorted_arr.extend([i+min_val]freq)returnsorted_arrarr=[4,2,2,8,3,3,1]sorted_arr=counting_sort(arr)print(sorted_arr)#输出：[1,2,2,3,3,4,8]解析：计数排序适用于范围较小且数据分布均匀的场景，时间复杂度为O(n+k)，其中k为范围。其核心是统计每个元素的出现次数，然后按顺序输出。缺点是空间复杂度较高。二、查找算法（2题，每题15分）4.二分查找的变种题目：实现二分查找的变种——查找第一个大于等于目标值的元素。假设数组为`[1,3,3,5,7]`，目标值为`4`，请返回索引`3`。答案与解析：答案：pythondefbinary_search_first_ge(arr,target):left,right=0,len(arr)-1result=-1whileleft<=right:mid=(left+right)//2ifarr[mid]>=target:result=midright=mid-1else:left=mid+1returnresultarr=[1,3,3,5,7]target=4index=binary_search_first_ge(arr,target)print(index)#输出：3解析：与普通二分查找不同，这里当找到满足条件的元素时，继续向左查找是否有更小的满足条件的元素。最终`result`记录第一个满足条件的索引。5.哈希表实现查找题目：假设有一个字符串数组`["apple","banana","cherry","date"]`，请实现一个哈希表（字典）来快速查找是否存在某个字符串，并统计查找时间复杂度。答案与解析：答案：pythondefhash_search(arr,target):hash_table={word:Trueforwordinarr}returnhash_table.get(target,False)arr=["apple","banana","cherry","date"]target="banana"exists=hash_search(arr,target)print(exists)#输出：True解析：哈希表通过键值对存储数据，查找时间复杂度为O(1)（平均情况）。当冲突较少时，性能极高。但最坏情况下（如全冲突）会退化到O(n)。三、动态规划（2题，每题20分）6.最长递增子序列（LIS）题目：给定数组`[10,9,2,5,3,7,101,18]`，请计算其最长递增子序列的长度。答案与解析：答案：pythondeflength_of_lis(arr):ifnotarr:return0dp=[1]len(arr)foriinrange(1,len(arr)):forjinrange(i):ifarr[i]>arr[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)arr=[10,9,2,5,3,7,101,18]length=length_of_lis(arr)print(length)#输出：4（子序列：[2,3,7,101]）解析：动态规划解法：1.初始化`dp[i]=1`，表示每个元素自身为子序列。2.对于每个`i`，遍历`j`（0到i-1），若`arr[i]>arr[j]`，则`dp[i]=max(dp[i],dp[j]+1)`。3.最终`dp`数组中的最大值即为LIS长度。7.斐波那契数列的非递归实现题目：实现一个时间复杂度为O(1)的斐波那契数列计算方法，计算第10个斐波那契数（从0开始）。答案与解析：答案：pythondeffib(n):ifn<=1:returnna,b=0,1for_inrange(2,n+1):a,b=b,a+breturnbn=10print(fib(n))#输出：55解析：通过空间复杂度O(1)的迭代方法，仅使用两个变量`a`和`b`交替更新，避免递归的栈空间消耗。时间复杂度为O(n)，但可通过矩阵快速幂进一步优化至O(logn)。四、图算法（2题，每题25分）8.最小生成树（MST）的Prim算法题目：给定以下无向图（邻接矩阵表示）：0123005∞101503∞2∞301310∞10请用Prim算法计算其最小生成树的总权值。答案与解析：答案：pythondefprim(matrix):n=len(matrix)in_mst=[False]nedge_count=0mst_weight=0in_mst[0]=Truewhileedge_count<n-1:min_edge=float('inf')u,v=-1,-1foriinrange(n):ifin_mst[i]:forjinrange(n):ifnotin_mst[j]andmatrix[i][j]<min_edge:min_edge=matrix[i][j]u,v=i,jin_mst[v]=Truemst_weight+=min_edgeedge_count+=1returnmst_weightmatrix=[[0,5,float('inf'),10],[5,0,3,float('inf')],[float('inf'),3,0,1],[10,float('inf'),1,0]]weight=prim(matrix)print(weight)#输出：16（路径：0-1,1-2,1-3）解析：Prim算法从单个顶点开始，逐步扩展MST，每次选择与已选顶点相邻且权值最小的边。最终权值之和为16。9.图的拓扑排序题目：给定以下有向图（邻接表表示）：0:[1,2]1:[3]2:[3]3:[]请输出其拓扑排序结果。答案与解析：答案：pythonfromcollectionsimportdequedeftopological_sort(graph):in_degree={u:0foruingraph}foruingraph:forvingraph[u]:in_degree[v]+=1queue=deque([uforuingraphifin_degree[u]==0])sorted_order=[]whilequeue:u=queue.popleft()sorted_order.append(u)forvingraph[u]:in_degree[v]-=1ifin_degree[v]==0:queue.append(v)returnsorted_ordergraph={0:[1,2],1:[3],2:[3],3:[]}order=topological_sort(graph)print(order)#输出：[0,1,2,3]解析：拓扑排序用于有向无环图（DAG），步骤：1.统计每个节点的入度。2.将所有入度为0的节点放入队列。3.依次出队节点，并将相邻节点的入度减1，若减为0则入队。最终顺序为`[0,1,2,3]`。五、字符串算法（2题，每题20分）10.最长回文子串题目：给定字符串`"babad"`，请输出其最长回文子串（如"bab"或"aba"）。答案与解析：答案：pythondeflongest_palindrome(s):ifnots:return""start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)len2=expand_from_center(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpand_from_center(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1s="babad"print(longest_palindrome(s))#输出："bab"或"aba"解析：通过中心扩展法，对于每个字符（或字符对）尝试扩展最长回文。时间复杂度为O(n²)，空间复杂度为O(1)。11.KMP算法实现题目：实现KMP（Knuth-Morris-Pratt）算法，计算字符串`"ABABDABACDABABCABAB"`中子串`"ABABCABAB"`的出现位置。答案与解析：答案：pythondefkmp_search(text,pattern):defcompute_lps(patter