? 分治算法的思想是將原問題遞歸分成若干個子問題，直到問題滿足邊界條件，停止遞歸，最后算法層層合并，得到原問題的答案。
? 分治算法適用情況：
1. 原問題的計算復雜度隨著問題的規(guī)模的增加而增加。
2. 原問題能夠被分解為更小的子問題。
3. 子問題的結(jié)構(gòu)和性質(zhì)與原問題一樣，并且互相獨立，子問題之間不包含公共的子子問題。
4. 原問題分解出的子問題的解可以合并為該問題的解。
分治算法練習1：
leetcode #50 Pow(x, n)
難度中等474
實現(xiàn)pow(x,n)，即計算 x 的 n 次冪函數(shù)
這道題目要求計算n個x相乘的結(jié)果?？梢酝ㄟ^循環(huán)n次*=暴力求解，時間復雜度為O(n)。
通過分治思想可以將求解過程分解為若干個子問題，從而降低時間復雜度。
舉例來說，2 ^ 8可以被分解 2 ^ 4 * 2 ^ 4，繼續(xù)分解為 2 ^ 2 * 2 ^ 2，繼續(xù)分解為 2 ^ 1 * 2 ^ 1，2的1次方為本身，作為邊界條件直接返回。
需要注意的是如果n（初始的n或者遞歸過程中出現(xiàn)的冪次）為奇數(shù)，則分解為 x * x ^ (n//2)? x ^ (n//2)
如果n為負數(shù)，則最后的邊界條件為-1，返回x的倒數(shù)。
代碼如下：
class?Solution:
????def?myPow(self,?x:?float,?n:?int)?->?float:
????????if?n?==?1:
????????????return?x
????????if?n?==?-1:?
????????????return?1/x???
????????if?n?==?0:
????????????return?1???
????????if?n?%?2?==?0:
????????????return?self.myPow(x,?n//2)?**?2 if?n?%?2?==?0 else?x?*?self.myPow(x,?n//2)?**?2
時間復雜度為O(logn)。
分治算法練習2：
leetcode #53
給定一個整數(shù)數(shù)組 nums?，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。
解法1：動態(tài)規(guī)劃
這道題較優(yōu)解法是動態(tài)規(guī)劃，并且比分治法更好想一些。
如果前i個元素和為負數(shù)，那么后面的子序列和無論多大，加上前i個元素只會起到副作用。
狀態(tài)轉(zhuǎn)移方程：
for i in range(1, len(nums)-1)
dp[i] = nums[i]?if dp[i-1] < 0 else dp[i] = max(dp[i-1]+nums[i]
初始條件，建立和nums長度相等的一個列表dp，第一個元素為nums的第一個元素。
空間復雜度優(yōu)化：由于后一個dp元素只和前一個有關(guān)，所以可以把長為n的列表空間縮小為一個元素的空間
代碼如下：
class?Solution:
????def?maxSubArray(self,?nums:?List[int])?->?int:
????????i?=?0
? ? ? ? dp =?nums[0]
? ? ? ? max_val = dp
????????while?i?<=?len(nums)-2:
????????????i?+=?1
????????????if dp <?0:???
? ? ? ? ? ? ? ? dp =?nums[i]
????????????else:
? ? ? ? ? ? ? ? dp +=?nums[i]
????????????max_val?=?max(max_val,dp)????????
????????return?max_val
時間復雜度：O(n)
解法2：分治算法
將原問題遞歸分為左子問題和右子問題，分別輸出左子區(qū)間和右子區(qū)間中的最大和連續(xù)子序列的結(jié)果，再計算跨越中線的最大和連續(xù)子序列結(jié)果，三者進行比較，輸出最大值作為該層的輸出值。
終止條件：當子區(qū)間長度為1時，直接返回這一個元素。
代碼如下：
class?Solution:
????def?maxSubArray(self,?nums:?List[int])?->?int:
? ? ? ? n = len(nums)
? ? ? ? return nums[0] if n == 1
? ? ? ? #左子問題的解
? ? ? ? left = self.maxSubArray(nums[:n//2])
????????#右子問題的解
? ? ? ? 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(left, right, max_l+max_r)
時間復雜度：O(nlogn)
分治算法練習3：
leetcode #169 多數(shù)元素
給定一個大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。
你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。
問題可以分解為左子區(qū)間的眾數(shù)，和右子區(qū)間的眾數(shù)在整個區(qū)數(shù)內(nèi)統(tǒng)計各自出現(xiàn)的次數(shù)并進行比較，返回多的那個數(shù)。
代碼如下：
class?Solution:
????def?majorityElement(self,?nums,?lo=0,?hi=None):
????????def?majority_element_rec(lo,?hi):
????????????if?lo?==?hi:
????????????????return?nums[lo]
????????????mid?=?(hi-lo)//2?+?lo
????????????left?=?majority_element_rec(lo,?mid)
????????????right?=?majority_element_rec(mid+1,?hi)
????????????# 終止條件：如果子區(qū)間只有一個元素，則直接返回這個元素
????????????if?left?==?right:
????????????????return?left
????????????# 統(tǒng)計左子區(qū)間返回的數(shù)和右子區(qū)間返回的數(shù)在原區(qū)間出現(xiàn)的次數(shù)，并比較
????????????left_count?=?sum(1?for?i?in?range(lo,?hi+1)?if?nums[i]?==?left)
????????????right_count?=?sum(1?for?i?in?range(lo,?hi+1)?if?nums[i]?==?right)
????????????return?left?if?left_count?>?right_count?else?right
????????return?majority_element_rec(0,?len(nums)-1)
時間復雜度：O(nlogn)
????????
