分治法的思想與經典題目
分治法簡介
分治法，即「分而治之」，就是將原問題分解為幾個規模較小但是類似於原問題的子問題，遞歸求解這些子問題， 然後再合併這些問題的解來建立原問題的解。
分治法主定理
分治法通常遵守一種通用模式：在解決規模為n的問題時，總是先遞歸地求解a個規模為n/b的子問題，然後在時間內將子問題的解合併起來。分治演算法的運行時間為：
分治演算法的時間複雜度
一般的，當a,b,d > 0且下式
成立時，有：
分治法的基本步驟
-
分解：分解原問題為若干子問題，這些子問題是原問題的規模最小的實例；
-
解決：解決這些子問題，遞歸地求解這些子問題。當子問題的規模足夠小，就可以直接求解；
-
合併：合併這些子問題的解成原問題的解。
分治法的使用條件
-
該問題的規模縮小到一定的程度就可以容易地解決；
-
隨著問題規模的減少，問題自然會容易解決。
-
該問題可以分解為若干個規模較小的相同問題；
-
分治法的前提。
-
利用該問題分解出的子問題的解可以合併為該問題的解；
-
分治法的前提。
-
該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。(非必需）
-
對於存在公共子問題的情況，使用分治演算法會存在重複計算的問題，使用動態規劃較為合適。
分治法的經典題目
50. Pow(x, n)
難度 中等
題目：實現 pow(x, n) ，即計算 x 的 n 次冪函數。
思路：
-
當我們要計算
時，我們可以先遞歸地計算出
，其中
表示對 aa 進行下取整；
-
根據遞歸計算的結果，如果 n 為偶數，那麼
；如果 n 為奇數，那麼
；
-
遞歸的邊界為 n=0，任意數的 0 次方均為 1。
class Solution: def myPow(self, x: float, n: int) -> float: """遞歸""" # 若x為0，直接返回0.0 if not x: return 0.0 def inner(m): # 規模最小的子問題的解 if m == 0: return 1. y = inner(m // 2) # 分解問題 # 合併子問題的解，冪為奇數或偶數時分開處理 return y * y if m % 2 == 0 else y * y * x return inner(n) if n >= 0 else 1. / inner(-n) # 處理冪為負數時的情況
思路：
-
通過循環
操作，每次把冪從 n 降至
，直至將冪降為 0 ；
-
設 res=1 ，則初始狀態
。在循環二分時，每當 n 為奇數時，將多出的一項 x 乘入 res ，則最終可化至
，返回 res 即可。
class Solution: def myPow(self, x: float, n: int) -> float: """迭代""" # 若x為0，直接返回0.0 if not x: return 0.0 # 處理冪為負數時的情況 if n < 0: x = 1 / x n = -n res = 1 while n: # 處理冪為奇數的情況 if n & 1: res *= x # 合併子問題的解 x *= x n >>= 1 # 分解問題 return res
53. 最大子序和
難度 簡單
題目：給定一個整數數組 nums，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
思路：按照數組中心將數組劃分為左右兩部分，最大子序要麼在左半部分，要麼在右半部分，要麼跨中心，這三種情況。跨中心的情況，再分治成中心點左側和右側的最大子序和問題。
class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) if n == 1: # 規模最小的子問題的解 return nums[0] else: # 分解問題 max_left = self.maxSubArray(nums[: n // 2]) # 求左半邊最大子序和 max_right = self.maxSubArray(nums[n // 2:]) # 求右半邊最大子序和 # 計算中間的最大子序和 # 從右到左計算左邊的最大子序和 max_l = nums[n // 2 - 1] tmp = 0 for i in range(n // 2 - 1, -1, -1): tmp += nums[i] max_l = max(tmp, max_l) # 從左到右計算右邊的最大子序和 max_r = nums[n // 2] tmp = 0 for i in range(n // 2, n): tmp += nums[i] max_r = max(tmp, max_r) # 返回三個中的最大值 return max(max_left, max_right, max_l + max_r)
169. 多數元素
難度 簡單
題目：給定一個大小為 n 的數組，找到其中的多數元素。多數元素是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。你可以假設數組是非空的，並且給定的數組總是存在多數元素。
思路：如果數 a 是數組 nums 的眾數，如果我們將 nums 分成兩部分，那麼 a 必定是其中一部分的眾數。這樣一來，我們就可以使用分治法解決這個問題：將數組分成左右兩部分，分別求出左半部分的眾數 a1 以及右半部分的眾數 a2，隨後在 a1 和 a2 中選出正確的眾數。
class Solution: def majorityElement(self, nums: List[int]) -> int: def inner(head, tail): # 規模最小的子問題的解 if head == tail: return nums[head] # 分解問題 mid = (tail - head) // 2 + head left = inner(head, mid) right = inner(mid+1, tail) if left == right: return left left_count = sum([1 for i in nums[head: tail+1] if i == left]) right_count = sum([1 for i in nums[head: tail+1] if i == right]) return left if left_count > right_count else right # 合併子問題的解 return inner(0, len(nums) - 1)
