2025年高頻算法面試題及答案現(xiàn)有一個(gè)二叉樹(shù)結(jié)構(gòu)的房屋群，每個(gè)節(jié)點(diǎn)代表一棟房屋且包含一定金額，相鄰的房屋（有直接父子關(guān)系）無(wú)法同時(shí)被搶劫，要求計(jì)算能搶劫到的最大金額。解決此問(wèn)題需采用樹(shù)型動(dòng)態(tài)規(guī)劃，核心在于為每個(gè)節(jié)點(diǎn)維護(hù)兩種狀態(tài)：選擇當(dāng)前節(jié)點(diǎn)時(shí)的最大金額（此時(shí)子節(jié)點(diǎn)不能選），不選擇當(dāng)前節(jié)點(diǎn)時(shí)的最大金額（此時(shí)子節(jié)點(diǎn)可選或不選）。通過(guò)后序遍歷遞歸計(jì)算每個(gè)節(jié)點(diǎn)的這兩種狀態(tài)值，最終根節(jié)點(diǎn)的兩種狀態(tài)中的最大值即為答案。具體實(shí)現(xiàn)時(shí)，定義遞歸函數(shù)返回一個(gè)長(zhǎng)度為2的數(shù)組，其中第一個(gè)元素表示不選當(dāng)前節(jié)點(diǎn)的最大金額，第二個(gè)元素表示選當(dāng)前節(jié)點(diǎn)的最大金額。對(duì)于當(dāng)前節(jié)點(diǎn)node：不選node時(shí)，左右子節(jié)點(diǎn)可選或不選，因此最大金額為左子節(jié)點(diǎn)兩種狀態(tài)的最大值加上右子節(jié)點(diǎn)兩種狀態(tài)的最大值。選node時(shí)，左右子節(jié)點(diǎn)不能選，因此最大金額為node的金額加上左子節(jié)點(diǎn)不選時(shí)的金額（數(shù)組第一個(gè)元素）加上右子節(jié)點(diǎn)不選時(shí)的金額。遞歸終止條件為節(jié)點(diǎn)為空，返回[0,0]。最終取根節(jié)點(diǎn)兩種狀態(tài)的最大值。示例代碼（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)不選當(dāng)前節(jié)點(diǎn)：左右子節(jié)點(diǎn)可選或不選的最大值之和not_choose=max(left[0],left[1])+max(right[0],right[1])選當(dāng)前節(jié)點(diǎn)：左右子節(jié)點(diǎn)必須不選choose=node.val+left[0]+right[0]return[not_choose,choose]res=dfs(root)returnmax(res[0],res[1])```時(shí)間復(fù)雜度O(n)，n為節(jié)點(diǎn)數(shù)，每個(gè)節(jié)點(diǎn)僅遍歷一次；空間復(fù)雜度O(h)，h為樹(shù)的高度，由遞歸棧深度決定。給定課程總數(shù)numCourses和先修關(guān)系數(shù)組prerequisites（其中prerequisites[i]=[a,b]表示課程b必須先修課程a），以及若干查詢(xún)數(shù)組queries（每個(gè)查詢(xún)?yōu)閇u,v]），要求判斷是否存在從u到v的先修路徑（即u是v的先修課程或先修的先修）。該問(wèn)題需計(jì)算課程之間的傳遞閉包，即所有間接先修關(guān)系?？赏ㄟ^(guò)拓?fù)渑判蚪Y(jié)合動(dòng)態(tài)規(guī)劃的方式預(yù)處理每個(gè)節(jié)點(diǎn)的可達(dá)節(jié)點(diǎn)集合。具體步驟為：1.構(gòu)建圖的鄰接表，并統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度。2.初始化每個(gè)節(jié)點(diǎn)的可達(dá)集合（初始時(shí)僅包含自身）。3.使用隊(duì)列進(jìn)行拓?fù)渑判?，每次取出入度?的節(jié)點(diǎn)u，遍歷其所有直接后繼v：a.將u的可達(dá)集合合并到v的可達(dá)集合中（因?yàn)閡的所有先修課程也是v的先修）。b.將v的入度減1，若減為0則加入隊(duì)列。4.預(yù)處理完成后，對(duì)于每個(gè)查詢(xún)[u,v]，只需檢查u是否在v的可達(dá)集合中。示例代碼（Python）：```pythondefcheckIfPrerequisite(numCourses,prerequisites,queries):fromcollectionsimportdeque鄰接表，入度數(shù)組，可達(dá)集合數(shù)組adj=[[]for_inrange(numCourses)]in_degree=[0]numCoursesreachable=[set()for_inrange(numCourses)]fora,binprerequisites:adj[a].append(b)in_degree[b]+=1初始化可達(dá)集合（每個(gè)節(jié)點(diǎn)自身可達(dá)）foriinrange(numCourses):reachable[i].add(i)拓?fù)渑判騫=deque()foriinrange(numCourses):ifin_degree[i]==0:q.append(i)whileq:u=q.popleft()forvinadj[u]:u的所有可達(dá)節(jié)點(diǎn)都是v的可達(dá)節(jié)點(diǎn)reachable[v].update(reachable[u])in_degree[v]-=1ifin_degree[v]==0:q.append(v)處理查詢(xún)r(jià)eturn[uinreachable[v]foru,vinqueries]```時(shí)間復(fù)雜度O(n2+m)，n為課程數(shù)，m為先修關(guān)系數(shù)，每個(gè)節(jié)點(diǎn)的可達(dá)集合合并操作最多進(jìn)行n次；空間復(fù)雜度O(n2)，用于存儲(chǔ)可達(dá)集合。給定字符串s，求其最長(zhǎng)回文子序列的長(zhǎng)度?；匚淖有蛄惺侵缚捎稍址畡h除某些字符（不改變順序）得到的回文序列，子序列不要求連續(xù)。動(dòng)態(tài)規(guī)劃是解決此類(lèi)問(wèn)題的有效方法。定義dp[i][j]為字符串s中從索引i到j(luò)的子串的最長(zhǎng)回文子序列長(zhǎng)度。狀態(tài)轉(zhuǎn)移方程如下：當(dāng)i==j時(shí)，子串只有一個(gè)字符，dp[i][j]=1。當(dāng)s[i]==s[j]時(shí)，i和j的字符可作為回文的兩端，因此dp[i][j]=dp[i+1][j-1]+2（若i+1>j-1，即中間無(wú)字符時(shí)，結(jié)果為2）。當(dāng)s[i]!=s[j]時(shí)，最長(zhǎng)回文子序列可能由i到j(luò)-1或i+1到j(luò)的子串得到，因此dp[i][j]=max(dp[i][j-1],dp[i+1][j])。填充dp數(shù)組時(shí)需按子串長(zhǎng)度從小到大遍歷，即先計(jì)算所有長(zhǎng)度為1的子串，再計(jì)算長(zhǎng)度為2的，直到長(zhǎng)度為n（n為s長(zhǎng)度）。最終dp[0][n-1]即為答案。示例代碼（Python）：```pythondeflongestPalindromeSubseq(s:str)->int:n=len(s)dp=[[0]nfor_inrange(n)]初始化長(zhǎng)度為1的子串foriinrange(n):dp[i][i]=1按子串長(zhǎng)度從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]```時(shí)間復(fù)雜度O(n2)，n為字符串長(zhǎng)度，需填充n×n的dp數(shù)組；空間復(fù)雜度O(n2)，可通過(guò)滾動(dòng)數(shù)組優(yōu)化至O(n)。給定字符串s和t，找出s中包含t所有字符的最短子串（稱(chēng)為最小覆蓋子串），若不存在則返回空字符串?；瑒?dòng)窗口算法適用于此類(lèi)子串覆蓋問(wèn)題。核心思想是用左右指針維護(hù)一個(gè)窗口，通過(guò)移動(dòng)右指針擴(kuò)大窗口直到包含t的所有字符，再移動(dòng)左指針縮小窗口以找到最小長(zhǎng)度。具體步驟如下：1.統(tǒng)計(jì)t中各字符的出現(xiàn)次數(shù)（需求字典need），并記錄需要滿(mǎn)足的字符種類(lèi)數(shù)（need_types）。2.初始化左右指針left=0，右指針right=0，窗口內(nèi)字符計(jì)數(shù)（window），以及已滿(mǎn)足需求的字符種類(lèi)數(shù)（valid）。3.移動(dòng)right指針，將s[right]加入window。若該字符是need中的字符且window中的計(jì)數(shù)等于need中的計(jì)數(shù)，則valid加1。4.當(dāng)valid等于need_types時(shí)，嘗試移動(dòng)left指針縮小窗口：a.記錄當(dāng)前窗口的起始位置和長(zhǎng)度。b.將s[left]從window中移除，若該字符是need中的字符且window中的計(jì)數(shù)小于need中的計(jì)數(shù)，則valid減1，此時(shí)停止移動(dòng)left。5.遍歷結(jié)束后，最小的窗口即為答案。示例代碼（Python）：```pythondefminWindow(s:str,t:str)->str:fromcollectionsimportdefaultdictneed=defaultdict(int)window=defaultdict(int)forcint:need[c]+=1need_types=len(need)left=right=0valid=0記錄最小窗口的起始和長(zhǎng)度start=0min_len=float('inf')whileright<len(s):c=s[right]right+=1ifcinneed:window[c]+=1ifwindow[c]==need[c]:valid+=1當(dāng)窗口滿(mǎn)足條件時(shí)收縮左邊界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''```時(shí)間復(fù)雜度O(n+m)，n為s長(zhǎng)度，m為t長(zhǎng)度，每個(gè)字符最多被左右指針各訪問(wèn)一次；空間復(fù)雜度O(|Σ|)，Σ為字符集大小。給定二叉樹(shù)的根節(jié)點(diǎn)root和兩個(gè)節(jié)點(diǎn)p、q，找出它們的最近公共祖先（LCA）。最近公共祖先定義為同時(shí)是p和q的祖先的節(jié)點(diǎn)中深度最大的那個(gè)。遞歸法是解決此問(wèn)題的高效方法。后序遍歷二叉樹(shù)，利用遞歸的返回值傳遞信息：若當(dāng)前子樹(shù)中存在p或q，則返回該節(jié)點(diǎn)；若同時(shí)存在p和q，則返回當(dāng)前節(jié)點(diǎn)作為L(zhǎng)CA。具體邏輯如下：遞歸終止條件：當(dāng)前節(jié)點(diǎn)為空，或等于p/q，直接返回當(dāng)前節(jié)點(diǎn)。遞歸左子樹(shù)得到left，遞歸右子樹(shù)得到right：a.若left和right都不為空，說(shuō)明當(dāng)前節(jié)點(diǎn)是LCA（左右子樹(shù)各包含p/q）。b.若left為空，返回right（p/q在右子樹(shù)中）。c.若right為空，返回left（p/q在左子樹(shù)中）。示例代碼（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:左右子樹(shù)各有一個(gè)目標(biāo)節(jié)點(diǎn)returnrootreturnleftifleftelseright目標(biāo)節(jié)點(diǎn)在左或右子樹(shù)```時(shí)間復(fù)雜度O(n)，n為節(jié)點(diǎn)數(shù)，每個(gè)節(jié)點(diǎn)僅訪問(wèn)一次；空間復(fù)雜度O(h)，h為樹(shù)的高度，由遞歸棧深度決定。給定非負(fù)整數(shù)數(shù)組nums，數(shù)組中每個(gè)元素nums[i]表示從位置i最多可以跳躍nums[i]步，要求計(jì)算到達(dá)數(shù)組最后一個(gè)位置的最少跳躍次數(shù)（假設(shè)總能到達(dá)）。貪心算法可在線性時(shí)間內(nèi)解決此問(wèn)題。核心思想是在每一步跳躍中選擇能跳得最遠(yuǎn)的位置，以最小化跳躍次數(shù)。具體步驟如下：1.初始化當(dāng)前能到達(dá)的最遠(yuǎn)位置end=0，下一步能到達(dá)的最遠(yuǎn)位置max_pos=0，跳躍次數(shù)count=0。2.遍歷數(shù)組（不訪問(wèn)最后一個(gè)元素，因?yàn)榈竭_(dá)最后一個(gè)位置后無(wú)需再跳）：a.更新max_pos為max(max_pos,i+nums[i])。b.當(dāng)i到達(dá)end時(shí)（說(shuō)明當(dāng)前跳躍范圍已用盡），需要進(jìn)行一次跳躍：i.count加1。ii.將end更新為max_pos（下一步的最遠(yuǎn)位置）。iii.若end已能到達(dá)或超過(guò)最后一個(gè)位置，提前返回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:到達(dá)當(dāng)前跳躍的邊界count+=1end=max_posifend>=n1:已能到達(dá)終點(diǎn)breakreturncount```時(shí)間復(fù)雜度O(n)，n為數(shù)組長(zhǎng)度，每個(gè)元素僅訪問(wèn)一次；空間復(fù)雜度O(1)。給定兩個(gè)大小分別為m和n的正序數(shù)組nums1和nums2，要求找出這兩個(gè)數(shù)組的中位數(shù)，時(shí)間復(fù)雜度需為O(log(min(m,n)))。二分查找是滿(mǎn)足時(shí)間復(fù)雜度要求的關(guān)鍵。核心思路是將兩個(gè)數(shù)組分別劃分為左右兩部分，使得左半部分的所有元素小于等于右半部分的所有元素，且左半部分的元素個(gè)數(shù)等于總長(zhǎng)度的一半（或總長(zhǎng)度一半加一）。具體步驟如下：1.確保nums1是較短的數(shù)組（若m>n，交換nums1和nums2），以減少二分次數(shù)。2.初始化二分范圍i在[0,m]之間（i表示nums1前i個(gè)元素屬于左半部分），則nums2的分割點(diǎn)j=(m+n+1)//2i（確保左半部分總元素?cái)?shù)為總長(zhǎng)度的一半或一半加一）。3.比較nums1[i-1]（左半部分nums1的最大元素）和nums2[j]（右半部分nums2的最小元素），以及nums2[j-1]和nums1[i]，調(diào)整i的范圍：a.若nums1[i-1]>nums2[j]，說(shuō)明i過(guò)大，需減小i。b.若nums2[j-1]>nums1[i]，說(shuō)明i過(guò)小，需增大i。4.找到正確的分割點(diǎn)后，根據(jù)總長(zhǎng)度的奇偶性計(jì)算中位數(shù)：a.總長(zhǎng)度為奇數(shù)時(shí)，中位數(shù)是左半部分的最大值。b.總長(zhǎng)度為偶數(shù)時(shí)，中位數(shù)是左半部分最大值和右半部分最小值的平均值。示例代碼（Python）：```pythondeffindMedianSortedArrays(nums1:list[int],nums2:list[int])->float:確保nums1是較短的數(shù)組iflen(nums1)>len(nums2):nums1,nums2=nums2,nums1m,n=len(nums1),len(nums2)total=m+nhalf=(total+1)//2左半部分的元素個(gè)數(shù)（奇偶通用）二分查找nu