1. 面試算法題解析分糖果問(wèn)題分糖果問(wèn)題是面試中常見(jiàn)的貪心算法題型主要考察對(duì)問(wèn)題本質(zhì)的理解和算法設(shè)計(jì)能力。典型題目描述如下有一群孩子站成一排每個(gè)孩子有一個(gè)評(píng)分。你需要給這些孩子分發(fā)糖果要求每個(gè)孩子至少分到一顆糖果評(píng)分更高的孩子必須比相鄰孩子獲得更多糖果這個(gè)問(wèn)題的關(guān)鍵在于理解評(píng)分與糖果分配之間的關(guān)系。我們先來(lái)看一個(gè)具體例子假設(shè)孩子評(píng)分?jǐn)?shù)組為 [1,3,2,2,1]那么最優(yōu)的糖果分配應(yīng)該是 [1,2,1,2,1]總共需要7顆糖果。1.1 貪心算法思路解析解決這個(gè)問(wèn)題的核心在于認(rèn)識(shí)到糖果分配需要滿足兩個(gè)方向的約束從左向右看如果右邊孩子評(píng)分更高則其糖果數(shù)必須比左邊多從右向左看如果左邊孩子評(píng)分更高則其糖果數(shù)必須比右邊多具體實(shí)現(xiàn)步驟如下初始化一個(gè)全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 復(fù)雜度分析與邊界條件時(shí)間復(fù)雜度O(n)因?yàn)槲覀冞M(jìn)行了兩次線性遍歷 空間復(fù)雜度O(n)需要額外的數(shù)組存儲(chǔ)糖果數(shù)需要注意的邊界條件空數(shù)組情況所有孩子評(píng)分相同的情況嚴(yán)格遞增或遞減的評(píng)分序列提示在實(shí)際面試中建議先處理邊界條件再實(shí)現(xiàn)核心算法邏輯這能展示你的代碼健壯性。2. 接雨水問(wèn)題詳解接雨水問(wèn)題是另一道經(jīng)典面試題考察對(duì)數(shù)組操作和雙指針技巧的掌握。題目描述如下給定n個(gè)非負(fù)整數(shù)表示每個(gè)寬度為1的柱子的高度圖計(jì)算按此排列的柱子下雨之后能接多少雨水。2.1 暴力解法與優(yōu)化思路最直觀的解法是對(duì)于每個(gè)柱子找到它左右兩側(cè)的最高柱子然后取兩者中的較小值減去當(dāng)前柱子的高度就是這個(gè)柱子能接的雨水量。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這個(gè)解法時(shí)間復(fù)雜度為O(n2)因?yàn)閷?duì)于每個(gè)元素都要掃描左右兩側(cè)。我們可以通過(guò)預(yù)處理來(lái)優(yōu)化2.2 動(dòng)態(tài)規(guī)劃優(yōu)化預(yù)先計(jì)算每個(gè)位置的左右最大值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這樣時(shí)間復(fù)雜度降為O(n)空間復(fù)雜度也是O(n)。2.3 雙指針終極優(yōu)化進(jìn)一步優(yōu)化空間復(fù)雜度到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這個(gè)解法的關(guān)鍵在于理解對(duì)于某個(gè)柱子我們只需要知道它左右兩側(cè)的最大值中較小的那個(gè)。3. 雙端隊(duì)列(deque)的應(yīng)用雙端隊(duì)列是一種重要的數(shù)據(jù)結(jié)構(gòu)在解決滑動(dòng)窗口問(wèn)題時(shí)特別有用。以LeetCode 239題滑動(dòng)窗口最大值為例3.1 問(wèn)題描述給定一個(gè)數(shù)組nums有一個(gè)大小為k的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到最右側(cè)。你需要找出每個(gè)窗口中的最大值。3.2 單調(diào)隊(duì)列解法使用雙端隊(duì)列維護(hù)一個(gè)單調(diào)遞減的隊(duì)列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() # 維護(hù)單調(diào)遞減隊(duì)列 while q and nums[q[-1]] num: q.pop() q.append(i) # 當(dāng)窗口形成后開(kāi)始記錄結(jié)果 if i k - 1: res.append(nums[q[0]]) return res這個(gè)算法的時(shí)間復(fù)雜度是O(n)因?yàn)槊總€(gè)元素最多被加入和移除隊(duì)列各一次。3.3 雙端隊(duì)列的其他應(yīng)用場(chǎng)景實(shí)現(xiàn)棧和隊(duì)列回文檢查樹(shù)的層次遍歷實(shí)現(xiàn)LRU緩存注意在Python中deque的popleft()操作是O(1)時(shí)間而list的pop(0)是O(n)時(shí)間這是deque的優(yōu)勢(shì)所在。4. 經(jīng)典排序算法實(shí)現(xiàn)與優(yōu)化排序算法是面試中的基礎(chǔ)考點(diǎn)下面介紹幾種常見(jiàn)排序算法的實(shí)現(xiàn)與優(yōu)化。4.1 快速排序的優(yōu)化實(shí)現(xiàn)標(biāo)準(zhǔn)快速排序在最壞情況下會(huì)退化為O(n2)我們可以通過(guò)以下方式優(yōu)化import random def quick_sort(nums): def partition(left, right): # 隨機(jī)選擇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)化點(diǎn)隨機(jī)選擇pivot避免有序數(shù)組的最壞情況三路快排處理大量重復(fù)元素小數(shù)組時(shí)切換為插入排序4.2 歸并排序的應(yīng)用歸并排序是穩(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歸并排序的擴(kuò)展應(yīng)用計(jì)算逆序?qū)ν獠颗判蛱幚泶笪募湵砼判虻淖罴堰x擇4.3 堆排序與優(yōu)先隊(duì)列堆排序可以用于解決Top K問(wèn)題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堆排序的特點(diǎn)時(shí)間復(fù)雜度O(nlogn)原地排序但不穩(wěn)定適合處理流式數(shù)據(jù)在實(shí)際面試中理解各種排序算法的適用場(chǎng)景比死記實(shí)現(xiàn)更重要。例如數(shù)據(jù)量小且基本有序插入排序需要穩(wěn)定性歸并排序內(nèi)存受限堆排序平均性能好快速排序