1. 面試算法題解析分糖果問題分糖果問題是面試中常見的貪心算法題型主要考察對問題本質的理解和算法設計能力。典型題目描述如下有一群孩子站成一排每個孩子有一個評分。你需要給這些孩子分發(fā)糖果要求每個孩子至少分到一顆糖果評分更高的孩子必須比相鄰孩子獲得更多糖果這個問題的關鍵在于理解評分與糖果分配之間的關系。我們先來看一個具體例子假設孩子評分數(shù)組為 [1,3,2,2,1]那么最優(yōu)的糖果分配應該是 [1,2,1,2,1]總共需要7顆糖果。1.1 貪心算法思路解析解決這個問題的核心在于認識到糖果分配需要滿足兩個方向的約束從左向右看如果右邊孩子評分更高則其糖果數(shù)必須比左邊多從右向左看如果左邊孩子評分更高則其糖果數(shù)必須比右邊多具體實現(xiàn)步驟如下初始化一個全1的糖果數(shù)組candies從左向右遍歷如果ratings[i] ratings[i-1]則candies[i] candies[i-1]1從右向左遍歷如果ratings[i] ratings[i1]則candies[i] max(candies[i], candies[i1]1)最后累加candies數(shù)組得到總糖果數(shù)def candy(ratings): n len(ratings) candies [1] * n # 從左向右遍歷 for i in range(1, n): if ratings[i] ratings[i-1]: candies[i] candies[i-1] 1 # 從右向左遍歷 for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: candies[i] max(candies[i], candies[i1]1) return sum(candies)1.2 復雜度分析與邊界條件時間復雜度O(n)因為我們進行了兩次線性遍歷 空間復雜度O(n)需要額外的數(shù)組存儲糖果數(shù)需要注意的邊界條件空數(shù)組情況所有孩子評分相同的情況嚴格遞增或遞減的評分序列提示在實際面試中建議先處理邊界條件再實現(xiàn)核心算法邏輯這能展示你的代碼健壯性。2. 接雨水問題詳解接雨水問題是另一道經典面試題考察對數(shù)組操作和雙指針技巧的掌握。題目描述如下給定n個非負整數(shù)表示每個寬度為1的柱子的高度圖計算按此排列的柱子下雨之后能接多少雨水。2.1 暴力解法與優(yōu)化思路最直觀的解法是對于每個柱子找到它左右兩側的最高柱子然后取兩者中的較小值減去當前柱子的高度就是這個柱子能接的雨水量。def trap_brute(height): res 0 n len(height) for i in range(1, n-1): left_max max(height[:i]) right_max max(height[i1:]) res max(0, min(left_max, right_max) - height[i]) return res這個解法時間復雜度為O(n2)因為對于每個元素都要掃描左右兩側。我們可以通過預處理來優(yōu)化2.2 動態(tài)規(guī)劃優(yōu)化預先計算每個位置的左右最大值def trap_dp(height): if not height: return 0 n len(height) left_max [0] * n right_max [0] * n left_max[0] height[0] for i in range(1, n): left_max[i] max(left_max[i-1], height[i]) right_max[-1] height[-1] for i in range(n-2, -1, -1): right_max[i] max(right_max[i1], height[i]) res 0 for i in range(n): res min(left_max[i], right_max[i]) - height[i] return res這樣時間復雜度降為O(n)空間復雜度也是O(n)。2.3 雙指針終極優(yōu)化進一步優(yōu)化空間復雜度到O(1)def trap(height): left, right 0, len(height)-1 left_max right_max 0 res 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: res left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: res right_max - height[right] right - 1 return res這個解法的關鍵在于理解對于某個柱子我們只需要知道它左右兩側的最大值中較小的那個。3. 雙端隊列(deque)的應用雙端隊列是一種重要的數(shù)據(jù)結構在解決滑動窗口問題時特別有用。以LeetCode 239題滑動窗口最大值為例3.1 問題描述給定一個數(shù)組nums有一個大小為k的滑動窗口從數(shù)組的最左側移動到最右側。你需要找出每個窗口中的最大值。3.2 單調隊列解法使用雙端隊列維護一個單調遞減的隊列from collections import deque def maxSlidingWindow(nums, k): q deque() res [] for i, num in enumerate(nums): # 移除超出窗口范圍的元素 while q and q[0] i - k: q.popleft() # 維護單調遞減隊列 while q and nums[q[-1]] num: q.pop() q.append(i) # 當窗口形成后開始記錄結果 if i k - 1: res.append(nums[q[0]]) return res這個算法的時間復雜度是O(n)因為每個元素最多被加入和移除隊列各一次。3.3 雙端隊列的其他應用場景實現(xiàn)棧和隊列回文檢查樹的層次遍歷實現(xiàn)LRU緩存注意在Python中deque的popleft()操作是O(1)時間而list的pop(0)是O(n)時間這是deque的優(yōu)勢所在。4. 經典排序算法實現(xiàn)與優(yōu)化排序算法是面試中的基礎考點下面介紹幾種常見排序算法的實現(xiàn)與優(yōu)化。4.1 快速排序的優(yōu)化實現(xiàn)標準快速排序在最壞情況下會退化為O(n2)我們可以通過以下方式優(yōu)化import random def quick_sort(nums): def partition(left, right): # 隨機選擇pivot避免最壞情況 pivot_idx random.randint(left, right) nums[pivot_idx], nums[right] nums[right], nums[pivot_idx] pivot nums[right] i left for j in range(left, right): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] return i def sort(left, right): if left right: return p partition(left, right) sort(left, p-1) sort(p1, right) sort(0, len(nums)-1) return nums優(yōu)化點隨機選擇pivot避免有序數(shù)組的最壞情況三路快排處理大量重復元素小數(shù)組時切換為插入排序4.2 歸并排序的應用歸并排序是穩(wěn)定的O(nlogn)算法特別適合鏈表排序和外部排序def merge_sort(nums): if len(nums) 1: return nums mid len(nums) // 2 left merge_sort(nums[:mid]) right merge_sort(nums[mid:]) return merge(left, right) def merge(left, right): res [] i j 0 while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res歸并排序的擴展應用計算逆序對外部排序處理大文件鏈表排序的最佳選擇4.3 堆排序與優(yōu)先隊列堆排序可以用于解決Top K問題import heapq def heap_sort(nums): heapq.heapify(nums) res [] while nums: res.append(heapq.heappop(nums)) return res def top_k(nums, k): heap nums[:k] heapq.heapify(heap) for num in nums[k:]: if num heap[0]: heapq.heappop(heap) heapq.heappush(heap, num) return heap堆排序的特點時間復雜度O(nlogn)原地排序但不穩(wěn)定適合處理流式數(shù)據(jù)在實際面試中理解各種排序算法的適用場景比死記實現(xiàn)更重要。例如數(shù)據(jù)量小且基本有序插入排序需要穩(wěn)定性歸并排序內存受限堆排序平均性能好快速排序