2026年算法面试题深度解析

2026年算法面试题深度解析1.数组与字符串（5题，每题8分）题目1：给定一个包含重复整数的数组，返回数组中不同数字的平方组成的升序数组。要求时间复杂度不超过O(n)。示例：输入：`[-4,-1,0,1,2]`输出：`[0,1,1,4,16]`题目2：实现一个函数，统计字符串中每个字符出现的次数，并返回一个字典。要求不使用内置的统计函数。示例：输入：`"hello"`输出：`{'h':1,'e':1,'l':2,'o':1}`题目3：给定两个字符串`s`和`t`，判断`t`是否是`s`的子串。要求不使用内置的子串函数。示例：输入：`s="hello",t="ll"`输出：`True`题目4：将一个32位的有符号整数`x`转换成字符串，要求不使用任何库函数。注意处理负数和整数溢出问题。示例：输入：`x=123`输出：`"123"`题目5：给定一个字符串`s`，找到其中最长的无重复字符的子串长度。示例：输入：`"abcabcbb"`输出：`3`（"abc"）2.链表（4题，每题10分）题目6：实现一个函数，删除链表的倒数第`n`个节点。要求只遍历一次链表。示例：输入：`head=[1,2,3,4,5],n=2`输出：`[1,2,3,5]`题目7：判断一个链表是否为回文链表。要求空间复杂度O(1)。示例：输入：`head=[1,2,2,1]`输出：`True`题目8：给定两个非空链表，返回它们的交点节点（假设链表相交则相交部分首节点相同）。示例：输入：`list1=[4,1,8],list2=[5,0,1,8]`输出：`nodewithvalue8`题目9：反转一个链表。示例：输入：`head=[1,2,3,4,5]`输出：`[5,4,3,2,1]`3.栈与队列（3题，每题12分）题目10：用栈实现队列。要求实现`push`和`pop`操作。示例：操作序列：`["MyQueue","push","push","pop","push","pop"]`输出：`[null,null,null,1,null,2]`题目11：判断一个字符串是否是有效的括号组合（只考虑`()`、`[]`、`{}`）。示例：输入：`"()[]{}"`输出：`True`题目12：用队列实现栈。要求实现`push`和`pop`操作。示例：操作序列：`["MyStack","push","push","pop","pop"]`输出：`[null,null,null,2,null,1]`4.树与图（5题，每题10分）题目13：给定二叉树，返回其最大深度。示例：输入：`[3,9,20,null,null,15,7]`输出：`3`题目14：二叉树层序遍历（按从上到下、从左到右的顺序返回每一层的节点值）。示例：输入：`[3,9,20,null,null,15,7]`输出：`[[3],[9,20],[15,7]]`题目15：判断二叉树是否是平衡二叉树（左右子树高度差不超过1）。示例：输入：`[3,1,2,null,null,null,null]`输出：`False`题目16：给定一个图，使用BFS（广度优先搜索）遍历所有节点，并返回遍历顺序。示例：输入：`graph={0:[1,2],1:[2],2:[0,3],3:[]}`输出：`[0,1,2,3]`题目17：给定一个图，使用DFS（深度优先搜索）遍历所有节点，并返回遍历顺序。示例：输入：`graph={0:[1,2],1:[2],2:[0,3],3:[]}`输出：`[0,1,2,3]`（顺序可能因递归实现不同）5.哈希表（3题，每题12分）题目18：设计一个LRU（最近最少使用）缓存，支持`get`和`put`操作。要求`get`和`put`操作的时间复杂度为O(1)。示例：操作序列：`["LRUCache","put","put","get","put","get","put","get","get"]`输入：`[2,1,2,2,1,1,2,2,2]`输出：`[null,null,null,1,null,-1,null,2,2]`题目19：给定一个字符串`s`，统计其中字母的频率，并返回字母按频率降序排列的字符串。若频率相同，则按字母升序排列。示例：输入：`"tree"`输出：`"eetr"`题目20：设计一个通用的哈希函数，用于将任意键映射到固定大小的哈希表中。要求考虑冲突解决策略（如链地址法）。示例：输入：`key="example",tableSize=10`输出：`hashIndex=6`（假设使用简单的取模法）6.动态规划（4题，每题12分）题目21：给定一个整数数组，返回连续子数组的最大和。示例：输入：`[-2,1,-3,4,-1,2,1,-5,4]`输出：`6`（子数组[4,-1,2,1]）题目22：给定一个字符串，判断是否可以通过删除一些字符使其变为回文串。示例：输入：`"racecar"`输出：`True`题目23：给定两个字符串，返回它们的最长公共子序列的长度。示例：输入：`s1="abcde",s2="ace"`输出：`3`（子序列"ace"）题目24：爬楼梯问题：给定一个楼梯，每次可以爬1或2阶，返回爬到顶部的不同方法总数。要求使用动态规划解决。示例：输入：`n=3`输出：`3`（方法：1+1+1,1+2,2+1）7.排序与搜索（4题，每题10分）题目25：快速排序：给定一个数组，使用快速排序算法进行原地排序。示例：输入：`[10,7,8,9,1,5]`输出：`[1,5,7,8,9,10]`题目26：二分查找：给定一个有序数组和一个目标值，返回目标值的索引。若不存在则返回-1。示例：输入：`nums=[1,2,3,4,5],target=3`输出：`2`题目27：在二维矩阵中查找一个目标值。矩阵每一行和每一列都按升序排列。示例：输入：`matrix=[[1,4,7],[2,5,8],[3,6,9]],target=5`输出：`True`题目28：实现一个计数排序算法，用于对非负整数数组进行排序。示例：输入：`nums=[4,2,2,8,3,3,1]`输出：`[1,2,2,3,3,4,8]`8.数学与位运算（3题，每题12分）题目29：给定两个正整数`a`和`b`，返回它们的乘积，但不能使用乘法运算符``。示例：输入：`a=5,b=3`输出：`15`题目30：实现一个函数，判断一个整数是否是素数。示例：输入：`n=17`输出：`True`题目31：给定一个非负整数，返回它的二进制表示中1的个数。示例：输入：`n=11`（二进制`1011`）输出：`3`答案与解析1.数组与字符串题目1：pythondefsortedSquares(nums):left,right=0,len(nums)-1result=[]whileleft<=right:ifnums[left]2>nums[right]2:result.append(nums[left]2)left+=1else:result.append(nums[right]2)right-=1returnresult[::-1]解析：双指针法。从两端向中间遍历，比较平方值大小，将较大的平方值加入结果，最后反转结果列表。时间复杂度O(n)。题目2：pythondefcount_chars(s):count={}forcharins:count[char]=count.get(char,0)+1returncount解析：遍历字符串，使用字典记录每个字符的出现次数。时间复杂度O(n)。题目3：pythondefis_substring(s,t):iflen(t)>len(s):returnFalseforiinrange(len(s)-len(t)+1):ifs[i:i+len(t)]==t:returnTruereturnFalse解析：滑动窗口法。遍历`s`，检查每个长度为`t`的子串是否等于`t`。时间复杂度O(nm)。题目4：pythondefint_to_string(x):ifx==0:return"0"neg=x<0x=abs(x)digits=[]whilex:digits.append(str(x%10))x//=10ifneg:digits.append('-')return''.join(digits[::-1])解析：反向构建字符串。从个位开始，逐位取余并反转，处理负数和溢出。时间复杂度O(log|x|)。题目5：pythondeflength_of_longest_substring(s):left=0max_len=0seen={}forright,charinenumerate(s):ifcharinseenandseen[char]>=left:left=seen[char]+1seen[char]=rightmax_len=max(max_len,right-left+1)returnmax_len解析：滑动窗口法。记录每个字符上次出现的位置，若重复则移动左指针。时间复杂度O(n)。2.链表题目6：pythondefremoveNthFromEnd(head,n):dummy=ListNode(0,head)left=right=dummyfor_inrange(n+1):right=right.nextwhileright:left=left.nextright=right.nextleft.next=left.next.nextreturndummy.next解析：快慢指针法。左指针和右指针初始间距为n，右指针到末尾时左指针指向目标节点前一个。时间复杂度O(n)。题目7：pythondefisPalindrome(head):stack=[]slow=fast=headwhilefastandfast.next:stack.append(slow.val)slow=slow.nextfast=fast.next.nextiffast:slow=slow.nextwhileslow:ifslow.val!=stack.pop():returnFalseslow=slow.nextreturnTrue解析：分为两步：1.快指针到末尾时，慢指针走到中间，同时将前半部分值压栈；2.比较后半部分值与栈顶值。空间复杂度O(n/2)=O(n)。题目8：pythondefgetIntersectionNode(headA,headB):ifnotheadAornotheadB:returnNonea,b=headA,headBwhilea!=b:a=a.nextifaelseheadBb=b.nextifbelseheadAreturna解析：交叉遍历法。若相交，两指针最终会相遇；若不相交，都会走到None。时间复杂度O(n)。题目9：pythondefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：迭代反转法。逐个节点反转next指针。时间复杂度O(n)。3.栈与队列题目10：pythonclassMyQueue:def__init__(self):self.in_stack=[]self.out_stack=[]defpush(self,x):self.in_stack.append(x)defpop(self):self.move_in_to_out()returnself.out_stack.pop()defpeek(self):self.move_in_to_out()returnself.out_stack[-1]defmove_in_to_out(self):ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())解析：两个栈实现队列。`push`压入`in_stack`，`pop`和`peek`时将`in_stack`的元素移动到`out_stack`。时间复杂度O(n)。题目11：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：栈匹配法。遍历字符串，遇到右括号时检查栈顶是否匹配。时间复杂度O(n)。题目12：pythonclassMyStack:def__init__(self):self.queue=[]defpush(self,x):self.queue.append(x)defpop(self):for_inrange(len(self.queue)-1):self.queue.append(self.queue.pop(0))returnself.queue.pop(0)defpeek(self):for_inrange(len(self.queue)-1):self.queue.append(self.queue.pop(0))top=self.queue.pop(0)self.queue.append(top)returntop解析：一个队列实现栈。`push`直接入队，`pop`和`peek`时将前n-1个元素重新入队。时间复杂度O(n)。4.树与图题目13：pythondefmaxDepth(root):ifnotroot:return0left=maxDepth(root.left)right=maxDepth(root.right)returnmax(left,right)+1解析：递归法。最大深度等于左右子树深度的最大值加1。时间复杂度O(n)。题目14：pythondeflevelOrder(root):ifnotroot:return[]result=[]queue=[root]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresult解析：BFS层序遍历。使用队列记录每一层节点。时间复杂度O(n)。题目15：pythondefisBalanced(root):defcheck(node):ifnotnode:return0left=check(node.left)right=check(node.right)ifabs(left-right)>1orleft==-1orright==-1:return-1returnmax(left,right)+1returncheck(root)!=-1解析：递归法。检查每个节点的高度差，若不平衡则提前返回-1。时间复杂度O(n)。题目16：pythondefBFS(graph):visited=set()queue=[]result=[]queue.append(next(iter(graph)))#Startfromanynodewhilequeue:node=queue.pop(0)ifnodenotinvisited:visited.add(node)result.append(node)forneighboringraph[node]:ifneighbornotinvisited:queue.append(neighbor)returnresult解析：BFS遍历。使用队列和访问集合。时间复杂度O(V+E)。题目17：pythondefDFS(graph):visited=set()result=[]defdfs(node):visited.add(node)result.append(node)forneighboringraph[node]:ifneighbornotinvisited:dfs(neighbor)dfs(next(iter(graph)))#Startfromanynodereturnresult解析：DFS遍历。使用递归和访问集合。时间复杂度O(V+E)。5.哈希表题目18：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)解析：双向链表+哈希表。哈希表记录键值对，双向链表记录访问顺序。时间复杂度O(1)。题目19：pythondeffrequencySort(s:str)->str:count={}forcharins:count[char]=count.get(char,0)+1return''.join(sorted(s,key=lambdax:(-count[x],x)))解析：统计频率后按频率降序、字母升序排序。时间复杂度O(nlogn)。题目20：pythondefhash_function(key,tableSize):returnhash(key)%tableSize解析：简单取模法。使用内置`hash`函数。时间复杂度O(1)。6.动态规划题目21：pythondefmaxSubArray(nums):max_sum=current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum解析：贪心+DP。`current_sum`记录当前子数组和，若为负则重置。时间复杂度O(n)。题目22：pythondefvalidPalindrome(s:str)->bool:left,right=0,len(s)-1whileleft<right:ifs[left]!=s[right]:returnFalseleft+=1right-=1returnTrue解析：双指针法。从两端向中间检查，若遇到不等则尝试跳过其中一个字符。时间复杂度O(n)。题目23：pythondeflongestCommonSubsequence(text1:str,text2:str)->int: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])returndp[m][n]解析：DP二维数组。`dp[i][j]`表示前i个字符和前j个字符的最长公共子序列长度。时间复杂度O(mn)。题目24：pythondefclimbStairs(n:int)->int:ifn==1:return1dp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]解析：DP一维数组。`dp[i]`表示爬到第i阶的方法数。时间复杂度O(n)。7.排序与搜索题目25：pythondefquickSort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquickSort(left)+middle+quickSort(right)解析：分治法。选择基准值，将数组分为小于、等于、大于三部分。时间复杂度O(nlogn)。题目26：pythondefbinarySearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1解析：二分查找。不断缩小搜索范围。时间复杂度O(logn)。题目27：pythondefsearchMatrix(matrix,target):ifnotmatrixornotmatrix[0]:returnFalsem,n=len(matrix),len(matrix[0])left,right=0,mn-1whilele