2026年程序员算法面试题解析

2026年程序员算法面试题解析一、编程语言基础（共3题，每题10分）题目1（Java）：编写一个Java方法，实现判断一个整数是否为完全平方数。例如，输入9，返回true；输入10，返回false。要求时间复杂度为O(1)。答案与解析：javapublicbooleanisPerfectSquare(intnum){if(num<2)returntrue;longleft=2,right=num/2;while(left<=right){longmid=left+(right-left)/2;longsquare=midmid;if(square==num)returntrue;if(square<num)left=mid+1;elseright=mid-1;}returnfalse;}解析：采用二分查找法，因为完全平方数的平方根在1到num/2之间。通过二分可以快速缩小查找范围，但无法达到O(1)时间复杂度。若要求O(1)，可以使用数学公式：`sqrt(num)`向下取整后平方等于num，即`(int)Math.sqrt(num)(int)Math.sqrt(num)==num`。但题目要求明确指出O(1)，因此二分法是更合理的解法。题目2（Python）：实现一个Python函数，输入一个字符串，返回该字符串中所有唯一字符的列表（不区分大小写）。例如，输入"Hello"，返回['H','e','l','o']。答案与解析：pythondefunique_chars(s):s=s.lower()seen=set()unique=[]forcharins:ifcharnotinseen:seen.add(char)unique.append(char)returnunique解析：通过将字符串统一转换为小写，避免大小写重复统计。使用集合`seen`记录已出现的字符，列表`unique`存储唯一字符。遍历字符串时，若字符未在`seen`中，则添加到两者中。时间复杂度为O(n)，空间复杂度为O(n)。题目3（C++）：编写一个C++函数，输入一个无重复元素的数组，返回该数组所有可能的子集。例如，输入[1,2,3]，返回[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]。答案与解析：cppinclude<vector>usingnamespacestd;vector<vector<int>>subsets(vector<int>&nums){vector<vector<int>>result;vector<int>path;backtrack(nums,0,path,result);returnresult;}voidbacktrack(vector<int>&nums,intstart,vector<int>&path,vector<vector<int>>&result){result.push_back(path);for(inti=start;i<nums.size();++i){path.push_back(nums[i]);backtrack(nums,i+1,path,result);path.pop_back();}}解析：采用回溯算法，通过递归构建所有子集。`start`参数确保每个元素只被使用一次，避免重复子集。每次递归时，将当前路径`path`添加到结果`result`中，然后尝试添加下一个元素并继续递归。回溯时撤销添加的元素，继续遍历其他选择。时间复杂度为O(2^n)，空间复杂度为O(n)。二、数据结构（共4题，每题12分）题目4（链表）：设计一个单链表节点，并实现删除链表中的倒数第n个节点。例如，输入链表1->2->3->4->5和n=2，返回1->2->3->5。答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefremoveNthFromEnd(head,n):dummy=ListNode(0,head)fast=slow=dummyfor_inrange(n+1):fast=fast.nextwhilefast:fast=fast.nextslow=slow.nextslow.next=slow.next.nextreturndummy.next解析：使用双指针法，`fast`和`slow`初始指向哑节点。先让`fast`前移n+1步，然后同时移动`fast`和`slow`，直到`fast`到达末尾。此时`slow`的`next`即为待删除节点。时间复杂度为O(n)，空间复杂度为O(1)。题目5（栈）：给定一个只包含'('和')'的字符串，判断其是否为有效的括号组合。例如，输入"()[]{}",返回true；输入"([)]"，返回false。答案与解析：pythondefisValid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：使用栈记录左括号，遍历字符串时遇到右括号则与栈顶左括号匹配。若栈为空或栈顶不匹配，则无效。最后栈应为空。时间复杂度为O(n)，空间复杂度为O(n)。题目6（树）：给定一个二叉树，判断其是否为平衡二叉树。平衡二叉树是指任一节点的左右子树高度差不超过1。答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisBalanced(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，则整棵树不平衡。时间复杂度为O(n)，空间复杂度为O(n)。题目7（哈希表）：设计一个LRU（最近最少使用）缓存，支持get和put操作。LRU缓存最多容纳容量个元素，每次get或put操作后，最近使用的元素会被移动到最前面。答案与解析：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)==self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：使用哈希表`cache`记录键值对，列表`order`记录使用顺序。get时将键移到末尾表示最近使用，put时若超出容量则删除最久未使用的元素。时间复杂度为O(1)，空间复杂度为O(capacity)。题目8（图）：给定一个无向图，判断是否存在负权环。例如，输入邻接矩阵[[0,-1,2],[1,0,-3],[-1,3,0]]，返回true（因为0→1→2→0的权重为-2）。答案与解析：pythondefhasNegativeCycle(n,edges):dist=[float('inf')]ndist[0]=0for_inrange(n-1):foru,v,winedges:ifdist[u]!=float('inf')anddist[u]+w<dist[v]:dist[v]=dist[u]+wforu,v,winedges:ifdist[u]!=float('inf')anddist[u]+w<dist[v]:returnTruereturnFalse解析：使用Bellman-Ford算法，通过n-1轮松弛操作检查负权环。若在n轮后仍有松弛，则存在负权环。时间复杂度为O(nm)，空间复杂度为O(n)。三、动态规划（共3题，每题15分）题目9（爬楼梯）：假设你正在爬楼梯，每次可以爬1或2阶。给定n阶楼梯，返回不同的爬法总数。例如，n=3，返回3（1+1+1、1+2、2+1）。答案与解析：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]解析：使用动态规划，`dp[i]`表示爬到第i阶的方法数。状态转移方程为`dp[i]=dp[i-1]+dp[i-2]`。初始条件`dp[1]=1`，`dp[2]=2`。时间复杂度为O(n)，空间复杂度为O(n)。题目10（最长递增子序列）：给定一个无序数组，返回其最长递增子序列的长度。例如，输入[10,9,2,5,3,7,101,18]，返回4（[2,3,7,101]）。答案与解析：pythondeflengthOfLIS(nums):ifnotnums:return0dp=[1]len(nums)foriinrange(1,len(nums)):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)解析：使用动态规划，`dp[i]`表示以nums[i]结尾的最长递增子序列长度。遍历数组时，对于每个元素，检查其前面的所有元素，若nums[i]>nums[j]，则更新dp[i]。最后返回dp中的最大值。时间复杂度为O(n^2)，空间复杂度为O(n)。题目11（背包问题）：给定一个容量为W的背包和n个物品，每个物品有重量和价值，返回背包能装的最大价值。例如，n=4，W=7，物品重量[1,3,4,5]，价值[1,4,5,7]，返回9（选择物品1和4）。答案与解析：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时的最大价值。状态转移方程为：若物品i重量不超过w，则选择与不选择物品i的最大值；否则只能不选择。时间复杂度为O(nW)，空间复杂度为O(nW)。四、贪心算法（共2题，每题14分）题目12（跳跃游戏）：给定一个非负整数数组，表示每个位置可以跳跃的最大长度。判断是否能从数组起始位置跳到末尾。例如，输入[2,3,1,1,4]，返回true。答案与解析：pythondefcanJump(nums):max_reach=0fori,jumpinenumerate(nums):ifi>max_reach:returnFalsemax_reach=max(max_reach,i+jump)ifmax_reach>=len(nums)-1:returnTruereturnTrue解析：贪心选择当前能跳到的最远位置，不断更新最大可达范围`max_reach`。若任何时候无法到达当前索引，则返回false。若`max_reach`超过或等于末尾，则能跳到末尾。时间复杂度为O(n)，空间复杂度为O(1)。题目13（区间合并）：给定一个区间的集合，合并所有重叠的区间。例如，输入[[1,3],[2,6],[8,10],[15,18]]，返回[[1,6],[8,10],[15,18]]。答案与解析：pythondefmerge(intervals):ifnotintervals:return[]intervals.sort(key=lambdax:x[0])merged=[intervals[0]]forcurrentinintervals[1:]:last=merged[-1]ifcurrent[0]<=last[1]:last[1]=max(last[1],current[1])else:merged.append(current)returnmerged解析：首先按区间起始位置排序，然后贪心合并。若当前区间与合并区间的末尾重叠，则扩展合并区间的末尾；否则，添加新区间。时间复杂度为O(nlogn)，空间复杂度为O(n)。五、数学与位运算（共2题，每题13分）题目14（数字翻转）：给定一个32位整数，返回其反向后的整数。例如，输入123，返回321；输入-123，返回-321。假设环境不允许存储64位整数。答案与解析：pythondefreverse(x):rev=0whilex!=0:pop=x%10x//=10ifrev>231//10or(rev==231//10andpop>7):return0ifrev<-231//10or(rev==-231//10andpop<-8):return0rev=rev10+popreturnrev解析：通过模10和整除10分别获取最后一位和剩余部分，逐位构建反转数字。同时检查是否溢出（32位整数范围为-2^31到2^31-1）。时间复杂度为O(logx)，空间复杂度为O(1)。题目15（XOR运算）：给定两个非负整数a和b，返回aXORb的结果。例如，a=5（101），b=3（011），返回8（1000）。答案与解析：pythondefxorOperation(a,b):returna^b解析：直接使用异或运算符`^`，其规则为：对应位相同为0，不同为1。时间复杂度为O(1)，空间复杂度为O(1)。六、综合应用（共2题，每题16分）题目16（二分搜索）：给定一个升序数组和一个目标值，返回目标值的索引。若不存在，返回-1。例如，输入nums=[4,5,6,7,8,9],target=7，返回3。答案与解析：pythondefbinarySearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return