2026年軟件工程師面試算法題解析與編程練習(xí)一、排序與搜索算法（3題，每題10分）題目1（快速排序?qū)崿F(xiàn)與優(yōu)化）：編寫(xiě)一個(gè)快速排序算法，要求在平均時(shí)間復(fù)雜度為O(nlogn)的前提下，考慮對(duì)數(shù)組中含有大量重復(fù)元素的情況進(jìn)行優(yōu)化。請(qǐng)給出代碼實(shí)現(xiàn)，并簡(jiǎn)述優(yōu)化策略。題目2（二分查找變體）：給定一個(gè)包含重復(fù)元素的有序數(shù)組，請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，找到數(shù)組中某個(gè)目標(biāo)值的第一個(gè)或最后一個(gè)出現(xiàn)的位置。例如，輸入`[1,2,2,3,3,3,4]`和目標(biāo)值`3`，返回`3`的第一個(gè)位置`3`或最后一個(gè)位置`5`（根據(jù)題目要求選擇）。題目3（TopK問(wèn)題）：設(shè)計(jì)一個(gè)算法，在未排序的數(shù)組中找到第K大的元素。要求時(shí)間復(fù)雜度不超過(guò)O(nlogK)，并給出代碼實(shí)現(xiàn)。二、鏈表算法（2題，每題15分）題目4（刪除排序鏈表中的重復(fù)元素）：給定一個(gè)已排序的鏈表，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。例如，輸入`1->1->2->3->3`，輸出`1->2->3`。請(qǐng)給出代碼實(shí)現(xiàn)，并說(shuō)明是否可以使用額外空間。題目5（鏈表反轉(zhuǎn)與檢測(cè)）：實(shí)現(xiàn)一個(gè)函數(shù)，反轉(zhuǎn)鏈表，并檢測(cè)鏈表是否存在環(huán)。例如，輸入`1->2->3->4->2`（存在環(huán)），輸出反轉(zhuǎn)后的鏈表（需處理環(huán)的情況）。三、樹(shù)與圖算法（3題，每題10分）題目6（二叉樹(shù)的最大深度）：給定一個(gè)二叉樹(shù)，編寫(xiě)遞歸或迭代函數(shù)計(jì)算其最大深度。例如，輸入`[3,9,20,null,null,15,7]`，返回`3`。題目7（二叉搜索樹(shù)的后序遍歷驗(yàn)證）：判斷一個(gè)給定數(shù)組是否是二叉搜索樹(shù)的后序遍歷結(jié)果。例如，輸入`[7,6,5,4,3,2,1]`，返回`true`。題目8（無(wú)向圖的連通分量）：給定一個(gè)無(wú)向圖，使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）計(jì)算其連通分量的數(shù)量。例如，輸入鄰接矩陣`[[1,1,0],[1,1,0],[0,0,1]]`，返回`2`。四、動(dòng)態(tài)規(guī)劃（2題，每題15分）題目9（最長(zhǎng)遞增子序列）：給定一個(gè)整數(shù)數(shù)組，找到最長(zhǎng)遞增子序列的長(zhǎng)度。例如，輸入`[10,9,2,5,3,7,101,18]`，返回`4`（子序列`[2,3,7,101]`）。要求時(shí)間復(fù)雜度為O(nlogn)。題目10（背包問(wèn)題變種）：給定一個(gè)容量為`W`的背包和若干物品，每個(gè)物品有重量`weights`和價(jià)值`values`，求背包能裝下的最大價(jià)值。要求使用動(dòng)態(tài)規(guī)劃解決，并考慮完全背包或部分背包的情況。五、哈希表與字符串算法（2題，每題15分）題目11（有效的括號(hào)匹配）：給定一個(gè)字符串，判斷其中括號(hào)（`()`、`[]`、`{}`）是否有效匹配。例如，輸入`("{[]}")`，返回`true`；輸入`("{[}")`，返回`false`。請(qǐng)給出代碼實(shí)現(xiàn)。題目12（字符串的排列）：判斷一個(gè)字符串是否是另一個(gè)字符串的排列。例如，輸入`s="rat"`和`t="car"`，返回`true`。要求不使用額外數(shù)據(jù)結(jié)構(gòu)。六、數(shù)學(xué)與位操作（1題，20分）題目13（翻轉(zhuǎn)二進(jìn)制位）：給定一個(gè)32位無(wú)符號(hào)整數(shù)`n`，編寫(xiě)函數(shù)返回其二進(jìn)制位翻轉(zhuǎn)后的結(jié)果。例如，輸入`00000010100101000001111010011100`，返回`00011001011100000010100101000000`。答案與解析一、排序與搜索算法題目1（快速排序優(yōu)化）：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)優(yōu)化策略：-三數(shù)取中法：選擇頭、中、尾三個(gè)數(shù)的中間值作為pivot，避免最壞情況（已排序數(shù)組）。-小數(shù)組時(shí)使用插入排序：當(dāng)子數(shù)組長(zhǎng)度小于閾值（如10）時(shí)，插入排序效率更高。題目2（二分查找變體）：pythondeffind_first_or_last(arr,target,find_first=True):left,right=0,len(arr)-1result=-1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:result=midiffind_first:right=mid-1else:left=mid+1elifarr[mid]<target:left=mid+1else:right=mid-1returnresult解析：-`find_first=True`返回第一個(gè)匹配位置，`False`返回最后一個(gè)。-通過(guò)調(diào)整左右指針避免重復(fù)遍歷相同元素。題目3（TopK問(wèn)題）：pythonimportheapqdeffind_kth_largest(nums,k):returnheapq.nlargest(k,nums)[-1]解析：-使用`heapq.nlargest`提取前k大元素，時(shí)間復(fù)雜度O(nlogk)。-也可使用快速選擇算法（Quickselect），平均O(n)。二、鏈表算法題目4（刪除排序鏈表中的重復(fù)元素）：pythondefdelete_duplicates(head):current=headwhilecurrentandcurrent.next:ifcurrent.val==current.next.val:current.next=current.next.nextelse:current=current.nextreturnhead解析：-不使用額外空間，直接修改鏈表指針。題目5（鏈表反轉(zhuǎn)與檢測(cè)環(huán)）：pythondefreverse_and_detect_cycle(head):prev=Noneslow,fast=head,headwhilefastandfast.next:fast=fast.next.nextslow=slow.nextiffast==slow:#檢測(cè)環(huán)returnreverse_list(head)#先反轉(zhuǎn)，再處理環(huán)returnreverse_list(head)defreverse_list(head):prev,current=None,headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：-使用快慢指針檢測(cè)環(huán)（Floyd判環(huán)算法）。-若存在環(huán)，先反轉(zhuǎn)鏈表，再重新檢測(cè)環(huán)。三、樹(shù)與圖算法題目6（二叉樹(shù)的最大深度）：pythondefmax_depth(root):ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))解析：-遞歸計(jì)算左右子樹(shù)深度，取最大值加1。題目7（二叉搜索樹(shù)的后序遍歷驗(yàn)證）：pythondefverify_postorder(postorder):ifnotpostorder:returnTrueroot=postorder[-1]i=0whilei<len(postorder)-1andpostorder[i]<root:i+=1forjinrange(i,len(postorder)-1):ifpostorder[j]<postorder[-1]:returnFalsereturnverify_postorder(postorder[:i])andverify_postorder(postorder[i:-1])解析：-后序遍歷：左子樹(shù)<根<右子樹(shù)。通過(guò)分割左右子樹(shù)驗(yàn)證。題目8（無(wú)向圖的連通分量）：pythondefcount_connected_components(graph):visited=set()defdfs(node):forneighboringraph[node]:ifneighbornotinvisited:visited.add(neighbor)dfs(neighbor)count=0fornodeingraph:ifnodenotinvisited:dfs(node)count+=1returncount解析：-使用DFS遍歷所有未訪問(wèn)節(jié)點(diǎn)，每個(gè)連通分量計(jì)數(shù)加1。四、動(dòng)態(tài)規(guī)劃題目9（最長(zhǎng)遞增子序列）：pythondeflength_of_LIS(nums):tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midtails[left]=numreturnlen(tails)解析：-利用二分查找維護(hù)tails數(shù)組，時(shí)間復(fù)雜度O(nlogn)。題目10（背包問(wèn)題變種）：pythondefknapsack(W,weights,values):dp=[0](W+1)forwinweights:foriinrange(w,W+1):dp[i]=max(dp[i],dp[i-w]+values[weights.index(w)])returndp[W]解析：-完全背包：遍歷所有物品，更新dp數(shù)組。五、哈希表與字符串算法題目11（有效的括號(hào)匹配）：pythondefisValid(s):stack=[]mapping={'(':')','[':']','{':'}'}forcharins:ifcharinmapping:stack.append(char)elifstackandmapping[stack.pop()]==char:continueelse:returnFalsereturnnotstack解析：-使用棧匹配括號(hào)，時(shí)間復(fù)雜度O(n)。題目12（字符串的排列）：pythondefcheckInclusion(s1,s2):iflen(s1)>len(s2):returnFalsecount1,count2=[0]26,[0]26foriinrange(len(s1)):count1[ord(s1[i])-ord('a')]+=1count2[ord(s2[i])-ord('a')]+=1foriinrange(len(s1),len(s2)):ifcount1==count2:returnTruecount2[ord(s2[i])-ord('a')]+=1count2[ord(s2[i-len(s1)])-ord('a')