2025年高频算法面试题及答案

2025年高频算法面试题及答案现有一个二叉树结构的房屋群，每个节点代表一栋房屋且包含一定金额，相邻的房屋（有直接父子关系）无法同时被抢劫，要求计算能抢劫到的最大金额。解决此问题需采用树型动态规划，核心在于为每个节点维护两种状态：选择当前节点时的最大金额（此时子节点不能选），不选择当前节点时的最大金额（此时子节点可选或不选）。通过后序遍历递归计算每个节点的这两种状态值，最终根节点的两种状态中的最大值即为答案。具体实现时，定义递归函数返回一个长度为2的数组，其中第一个元素表示不选当前节点的最大金额，第二个元素表示选当前节点的最大金额。对于当前节点node：不选node时，左右子节点可选或不选，因此最大金额为左子节点两种状态的最大值加上右子节点两种状态的最大值。选node时，左右子节点不能选，因此最大金额为node的金额加上左子节点不选时的金额（数组第一个元素）加上右子节点不选时的金额。递归终止条件为节点为空，返回[0,0]。最终取根节点两种状态的最大值。示例代码（Python）：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefrob(root:TreeNode)->int:defdfs(node):ifnotnode:return[0,0]left=dfs(node.left)right=dfs(node.right)不选当前节点：左右子节点可选或不选的最大值之和not_choose=max(left[0],left[1])+max(right[0],right[1])选当前节点：左右子节点必须不选choose=node.val+left[0]+right[0]return[not_choose,choose]res=dfs(root)returnmax(res[0],res[1])```时间复杂度O(n)，n为节点数，每个节点仅遍历一次；空间复杂度O(h)，h为树的高度，由递归栈深度决定。给定课程总数numCourses和先修关系数组prerequisites（其中prerequisites[i]=[a,b]表示课程b必须先修课程a），以及若干查询数组queries（每个查询为[u,v]），要求判断是否存在从u到v的先修路径（即u是v的先修课程或先修的先修）。该问题需计算课程之间的传递闭包，即所有间接先修关系。可通过拓扑排序结合动态规划的方式预处理每个节点的可达节点集合。具体步骤为：1.构建图的邻接表，并统计每个节点的入度。2.初始化每个节点的可达集合（初始时仅包含自身）。3.使用队列进行拓扑排序，每次取出入度为0的节点u，遍历其所有直接后继v：a.将u的可达集合合并到v的可达集合中（因为u的所有先修课程也是v的先修）。b.将v的入度减1，若减为0则加入队列。4.预处理完成后，对于每个查询[u,v]，只需检查u是否在v的可达集合中。示例代码（Python）：```pythondefcheckIfPrerequisite(numCourses,prerequisites,queries):fromcollectionsimportdeque邻接表，入度数组，可达集合数组adj=[[]for_inrange(numCourses)]in_degree=[0]numCoursesreachable=[set()for_inrange(numCourses)]fora,binprerequisites:adj[a].append(b)in_degree[b]+=1初始化可达集合（每个节点自身可达）foriinrange(numCourses):reachable[i].add(i)拓扑排序q=deque()foriinrange(numCourses):ifin_degree[i]==0:q.append(i)whileq:u=q.popleft()forvinadj[u]:u的所有可达节点都是v的可达节点reachable[v].update(reachable[u])in_degree[v]-=1ifin_degree[v]==0:q.append(v)处理查询return[uinreachable[v]foru,vinqueries]```时间复杂度O(n²+m)，n为课程数，m为先修关系数，每个节点的可达集合合并操作最多进行n次；空间复杂度O(n²)，用于存储可达集合。给定字符串s，求其最长回文子序列的长度。回文子序列是指可由原字符串删除某些字符（不改变顺序）得到的回文序列，子序列不要求连续。动态规划是解决此类问题的有效方法。定义dp[i][j]为字符串s中从索引i到j的子串的最长回文子序列长度。状态转移方程如下：当i==j时，子串只有一个字符，dp[i][j]=1。当s[i]==s[j]时，i和j的字符可作为回文的两端，因此dp[i][j]=dp[i+1][j-1]+2（若i+1>j-1，即中间无字符时，结果为2）。当s[i]!=s[j]时，最长回文子序列可能由i到j-1或i+1到j的子串得到，因此dp[i][j]=max(dp[i][j-1],dp[i+1][j])。填充dp数组时需按子串长度从小到大遍历，即先计算所有长度为1的子串，再计算长度为2的，直到长度为n（n为s长度）。最终dp[0][n-1]即为答案。示例代码（Python）：```pythondeflongestPalindromeSubseq(s:str)->int:n=len(s)dp=[[0]nfor_inrange(n)]初始化长度为1的子串foriinrange(n):dp[i][i]=1按子串长度从2到n遍历forlengthinrange(2,n+1):foriinrange(nlength+1):j=i+length1ifs[i]==s[j]:iflength==2:dp[i][j]=2else:dp[i][j]=dp[i+1][j-1]+2else:dp[i][j]=max(dp[i][j-1],dp[i+1][j])returndp[0][n-1]```时间复杂度O(n²)，n为字符串长度，需填充n×n的dp数组；空间复杂度O(n²)，可通过滚动数组优化至O(n)。给定字符串s和t，找出s中包含t所有字符的最短子串（称为最小覆盖子串），若不存在则返回空字符串。滑动窗口算法适用于此类子串覆盖问题。核心思想是用左右指针维护一个窗口，通过移动右指针扩大窗口直到包含t的所有字符，再移动左指针缩小窗口以找到最小长度。具体步骤如下：1.统计t中各字符的出现次数（需求字典need），并记录需要满足的字符种类数（need_types）。2.初始化左右指针left=0，右指针right=0，窗口内字符计数（window），以及已满足需求的字符种类数（valid）。3.移动right指针，将s[right]加入window。若该字符是need中的字符且window中的计数等于need中的计数，则valid加1。4.当valid等于need_types时，尝试移动left指针缩小窗口：a.记录当前窗口的起始位置和长度。b.将s[left]从window中移除，若该字符是need中的字符且window中的计数小于need中的计数，则valid减1，此时停止移动left。5.遍历结束后，最小的窗口即为答案。示例代码（Python）：```pythondefminWindow(s:str,t:str)->str:fromcollectionsimportdefaultdictneed=defaultdict(int)window=defaultdict(int)forcint:need[c]+=1need_types=len(need)left=right=0valid=0记录最小窗口的起始和长度start=0min_len=float('inf')whileright<len(s):c=s[right]right+=1ifcinneed:window[c]+=1ifwindow[c]==need[c]:valid+=1当窗口满足条件时收缩左边界whilevalid==need_types:更新最小窗口ifrightleft<min_len:start=leftmin_len=rightleftd=s[left]left+=1ifdinneed:ifwindow[d]==need[d]:valid-=1window[d]-=1returns[start:start+min_len]ifmin_len!=float('inf')else''```时间复杂度O(n+m)，n为s长度，m为t长度，每个字符最多被左右指针各访问一次；空间复杂度O(|Σ|)，Σ为字符集大小。给定二叉树的根节点root和两个节点p、q，找出它们的最近公共祖先（LCA）。最近公共祖先定义为同时是p和q的祖先的节点中深度最大的那个。递归法是解决此问题的高效方法。后序遍历二叉树，利用递归的返回值传递信息：若当前子树中存在p或q，则返回该节点；若同时存在p和q，则返回当前节点作为LCA。具体逻辑如下：递归终止条件：当前节点为空，或等于p/q，直接返回当前节点。递归左子树得到left，递归右子树得到right：a.若left和right都不为空，说明当前节点是LCA（左右子树各包含p/q）。b.若left为空，返回right（p/q在右子树中）。c.若right为空，返回left（p/q在左子树中）。示例代码（Python）：```pythonclassTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=NonedeflowestCommonAncestor(root:TreeNode,p:TreeNode,q:TreeNode)->TreeNode:ifnotrootorroot==porroot==q:returnrootleft=lowestCommonAncestor(root.left,p,q)right=lowestCommonAncestor(root.right,p,q)ifleftandright:左右子树各有一个目标节点returnrootreturnleftifleftelseright目标节点在左或右子树```时间复杂度O(n)，n为节点数，每个节点仅访问一次；空间复杂度O(h)，h为树的高度，由递归栈深度决定。给定非负整数数组nums，数组中每个元素nums[i]表示从位置i最多可以跳跃nums[i]步，要求计算到达数组最后一个位置的最少跳跃次数（假设总能到达）。贪心算法可在线性时间内解决此问题。核心思想是在每一步跳跃中选择能跳得最远的位置，以最小化跳跃次数。具体步骤如下：1.初始化当前能到达的最远位置end=0，下一步能到达的最远位置max_pos=0，跳跃次数count=0。2.遍历数组（不访问最后一个元素，因为到达最后一个位置后无需再跳）：a.更新max_pos为max(max_pos,i+nums[i])。b.当i到达end时（说明当前跳跃范围已用尽），需要进行一次跳跃：i.count加1。ii.将end更新为max_pos（下一步的最远位置）。iii.若end已能到达或超过最后一个位置，提前返回count。示例代码（Python）：```pythondefjump(nums:list[int])->int:n=len(nums)ifn==1:return0end=max_pos=count=0foriinrange(n):max_pos=max(max_pos,i+nums[i])ifi==end:到达当前跳跃的边界count+=1end=max_posifend>=n1:已能到达终点breakreturncount```时间复杂度O(n)，n为数组长度，每个元素仅访问一次；空间复杂度O(1)。给定两个大小分别为m和n的正序数组nums1和nums2，要求找出这两个数组的中位数，时间复杂度需为O(log(min(m,n)))。二分查找是满足时间复杂度要求的关键。核心思路是将两个数组分别划分为左右两部分，使得左半部分的所有元素小于等于右半部分的所有元素，且左半部分的元素个数等于总长度的一半（或总长度一半加一）。具体步骤如下：1.确保nums1是较短的数组（若m>n，交换nums1和nums2），以减少二分次数。2.初始化二分范围i在[0,m]之间（i表示nums1前i个元素属于左半部分），则nums2的分割点j=(m+n+1)//2i（确保左半部分总元素数为总长度的一半或一半加一）。3.比较nums1[i-1]（左半部分nums1的最大元素）和nums2[j]（右半部分nums2的最小元素），以及nums2[j-1]和nums1[i]，调整i的范围：a.若nums1[i-1]>nums2[j]，说明i过大，需减小i。b.若nums2[j-1]>nums1[i]，说明i过小，需增大i。4.找到正确的分割点后，根据总长度的奇偶性计算中位数：a.总长度为奇数时，中位数是左半部分的最大值。b.总长度为偶数时，中位数是左半部分最大值和右半部分最小值的平均值。示例代码（Python）：```pythondeffindMedianSortedArrays(nums1:list[int],nums2:list[int])->float:确保nums1是较短的数组iflen(nums1)>len(nums2):nums1,nums2=nums2,nums1m,n=len(nums1),len(nums2)total=m+nhalf=(total+1)//2左半部分的元素个数（奇偶通用）二分查找nu