2026年軟件工程師面試常見算法題解含答案一、排序算法（3題，每題10分）1.題目：實現快速排序（QuickSort）算法，并說明其平均時間復雜度和最壞情況時間復雜度。答案：快速排序是一種分治算法，核心思想是選擇一個基準值（pivot），將數組分為兩部分，使得左邊的元素都小于基準值，右邊的元素都大于基準值，然后遞歸地對左右兩部分進行排序。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)解析：-平均時間復雜度：O(nlogn)，因為每次分區(qū)操作的時間復雜度為O(n)，分區(qū)次數為logn。-最壞情況時間復雜度：O(n2)，當基準值選擇不均勻時（如已排序數組選擇最左或最右為基準），會導致不平衡分區(qū)。2.題目：實現歸并排序（MergeSort）算法，并解釋其穩(wěn)定性。答案：歸并排序也是一種分治算法，將數組遞歸地分成兩半，分別排序后再合并。pythondefmerge_sort(arr):iflen(arr)<=1:returnarrmid=len(arr)//2left=merge_sort(arr[:mid])right=merge_sort(arr[mid:])returnmerge(left,right)defmerge(left,right):result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresult解析：歸并排序是穩(wěn)定的排序算法，因為合并時相同元素的相對順序不會改變。時間復雜度始終為O(nlogn)，適用于鏈表和外部排序場景。3.題目：給定一個數組，實現堆排序（HeapSort），并說明其時間復雜度。答案：堆排序利用堆（通常是最大堆）的性質進行排序，步驟包括構建最大堆、交換堆頂與末尾元素、調整堆。pythondefheap_sort(arr):defheapify(arr,n,i):largest=ileft=2i+1right=2i+2ifleft<nandarr[left]>arr[largest]:largest=leftifright<nandarr[right]>arr[largest]:largest=rightiflargest!=i:arr[i],arr[largest]=arr[largest],arr[i]heapify(arr,n,largest)n=len(arr)foriinrange(n//2-1,-1,-1):heapify(arr,n,i)foriinrange(n-1,0,-1):arr[i],arr[0]=arr[0],arr[i]heapify(arr,i,0)returnarr解析：堆排序的時間復雜度為O(nlogn)，因為構建堆的時間復雜度為O(n)，每次調整堆的時間復雜度為O(logn)，共n次。適用于內存受限場景。二、鏈表問題（3題，每題10分）1.題目：實現反轉鏈表（ReverseLinkedList）函數。答案：使用迭代法或遞歸法反轉鏈表。python迭代法defreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：通過逐個節(jié)點反轉next指針，最終prev成為新的頭節(jié)點。時間復雜度O(n)，空間復雜度O(1)。2.題目：判斷鏈表是否存在環(huán)（CycleDetection），并實現檢測算法。答案：使用快慢指針（Floyd'sTortoiseandHare）算法。pythondefhas_cycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:returnTruereturnFalse解析：快指針每次移動兩步，慢指針每次移動一步，若存在環(huán)，快慢指針會相遇。時間復雜度O(n)，空間復雜度O(1)。3.題目：合并兩個有序鏈表，返回合并后的頭節(jié)點。答案：使用遞歸或迭代法合并。pythondefmerge_sorted_lists(l1,l2):ifnotl1:returnl2ifnotl2:returnl1ifl1.val<l2.val:l1.next=merge_sorted_lists(l1.next,l2)returnl1else:l2.next=merge_sorted_lists(l1,l2.next)returnl2解析：遞歸地比較兩個鏈表頭節(jié)點的值，選擇較小的節(jié)點作為新鏈表的頭，并遞歸處理剩余部分。時間復雜度O(n)，空間復雜度O(n)（遞歸棧）。三、棧與隊列（2題，每題10分）1.題目：實現一個棧，支持在頂部插入和刪除元素，并支持返回棧中最小元素的時間復雜度為O(1)。答案：使用輔助棧記錄當前最小值。pythonclassMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,x):self.stack.append(x)ifnotself.min_stackorx<=self.min_stack[-1]:self.min_stack.append(x)defpop(self):ifnotself.stack:returnNonetop=self.stack.pop()iftop==self.min_stack[-1]:self.min_stack.pop()returntopdefmin(self):ifnotself.min_stack:returnNonereturnself.min_stack[-1]解析：每次push時，若新元素小于等于當前最小值，則將其也push到min_stack；pop時若彈出元素等于當前最小值，則min_stack也pop。時間復雜度O(1)。2.題目：實現一個隊列，支持在隊首插入元素和在隊尾刪除元素。答案：使用兩個棧實現隊列。pythonclassQueueUsingStacks:def__init__(self):self.in_stack=[]self.out_stack=[]defenqueue(self,x):self.in_stack.append(x)defdequeue(self):ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())ifnotself.out_stack:returnNonereturnself.out_stack.pop()解析：enqueue時直接push到in_stack；dequeue時若out_stack為空，則將in_stack中的元素全部pop到out_stack，再從out_stackpop。時間復雜度O(1)（攤銷）。四、樹與二叉搜索樹（2題，每題10分）1.題目：給定一個二叉樹，實現中序遍歷（In-orderTraversal）算法。答案：使用遞歸或迭代法。python遞歸法definorder_traversal(root):ifnotroot:return[]returninorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)解析：中序遍歷的順序是左子樹、根節(jié)點、右子樹。遞歸法簡單直觀，時間復雜度O(n)，空間復雜度O(h)（h為樹的高度）。2.題目：實現二叉搜索樹（BST）的插入操作。答案：從根節(jié)點開始，遞歸地比較值，選擇左子樹或右子樹插入。pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinsert_into_bst(root,val):ifnotroot:returnTreeNode(val)ifval<root.val:root.left=insert_into_bst(root.left,val)else:root.right=insert_into_bst(root.right,val)returnroot解析：BST的性質是左子樹所有值小于根節(jié)點，右子樹所有值大于根節(jié)點。插入時根據此性質遞歸查找位置。時間復雜度O(h)，最壞為O(n)。五、動態(tài)規(guī)劃（2題，每題10分）1.題目：給定一個字符串，計算最長的回文子串（LongestPalindromicSubstring）的長度。答案：使用中心擴展法。pythondeflongest_palindrome(s):ifnots:return0start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)len2=expand_from_center(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returnend-start+1defexpand_from_center(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：遍歷每個字符，分別以單個字符和兩個字符為中心擴展，記錄最大長度。時間復雜度O(n2)，空間復雜度O(1)。2.題目：給定一個數組，計算最長遞增子序列（LongestIncreasingSubsequence,LIS）的長度。答案：使用動態(tài)規(guī)劃+二分查找優(yōu)化。pythondeflength_of_lis(nums):tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)else:tails[left]=numreturnlen(tails)解析：tails數組存儲當前最長遞增子序列的末尾元素。遍歷時用二分查找tails中的位置，更新或替換元素。時間復雜度O(nlogn)，空間復雜度O(n)。六、貪心算法（2題，每題10分）1.題目：給定一個非負整數數組，每次可以選擇一個元素減半（只能減偶數），求使數組元素之和最小的操作次數。答案：每次選擇最大的偶數元素減半。pythondefhalve_array(nums):importheapqnums=[-xforxinnums]#最小堆heapq.heapify(nums)sum_before=sum(nums)count=0whilesum(nums)>sum_before/2:max_num=-heapq.heappop(nums)halved=max_num/2heapq.heappush(nums,-halved)sum_before-=halvedcount+=1returncount解析：貪心策略是每次減少最大的偶數元素，可以更快地減少總和。時間復雜度O(nlogn)，空間復雜度O(n)。2.題目：給定一個字符串，找到最長的無重復字符的子串（LongestSubstringWithoutRepeatingCharacters）的長度。答案：使用滑動窗口法。pythondeflength_of_longest_substring(s):char_map={}left=0max_len=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len解析：維護一個左指針和字符映射表，當遇到重復字符時，將左指針移動到重復字符的下一個位置。時間復雜度O(n)，空間復雜度O(1)。七、哈希表（2題，每題10分）1.題目：給定一個數組，找出其中和為特定值的三元組（ThreeSum）的數量。答案：排序后使用雙指針法。pythondefthree_sum(nums,target):nums.sort()count=0n=len(nums)foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:current_sum=nums[i]+nums[left]+nums[right]ifcurrent_sum==target:count+=1whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifcurrent_sum<target:left+=1else:right-=1returncount解析：排序后，固定一個數，使用雙指針在剩余部分查找和為target的另外兩個數。時間復雜度O(n2)，空間復雜度O(1)。2.題目：判斷一個字符串是否是另一個字符串的子串（不區(qū)分大小寫，且允許字符重疊）。答案：使用哈希表記錄字符頻率，滑動窗口匹配。pythondefis_substring(s1,s2):s1,s2=s1.lower(),s2.lower()count_s2={}forcharins2