? 分治算法的思想是將原問題遞歸分成若干個(gè)子問題植袍，直到問題滿足邊界條件拯欧，停止遞歸，最后算法層層合并桨武，得到原問題的答案肋拔。
? 分治算法適用情況：
1. 原問題的計(jì)算復(fù)雜度隨著問題的規(guī)模的增加而增加。
2. 原問題能夠被分解為更小的子問題呀酸。
3. 子問題的結(jié)構(gòu)和性質(zhì)與原問題一樣凉蜂，并且互相獨(dú)立，子問題之間不包含公共的子子問題性誉。
4. 原問題分解出的子問題的解可以合并為該問題的解窿吩。
分治算法練習(xí)1：
leetcode #50 Pow(x, n)
難度中等474
實(shí)現(xiàn)pow(x,n)，即計(jì)算 x 的 n 次冪函數(shù)
這道題目要求計(jì)算n個(gè)x相乘的結(jié)果错览∪已悖可以通過循環(huán)n次*=暴力求解，時(shí)間復(fù)雜度為O(n)倾哺。
通過分治思想可以將求解過程分解為若干個(gè)子問題轧邪，從而降低時(shí)間復(fù)雜度。
舉例來說羞海，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為負(fù)數(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
時(shí)間復(fù)雜度為O(logn)勺远。
分治算法練習(xí)2：
leetcode #53
給定一個(gè)整數(shù)數(shù)組 nums?橙喘，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和胶逢。
解法1：動(dòng)態(tài)規(guī)劃
這道題較優(yōu)解法是動(dòng)態(tài)規(guī)劃厅瞎，并且比分治法更好想一些。
如果前i個(gè)元素和為負(fù)數(shù)初坠，那么后面的子序列和無論多大和簸，加上前i個(gè)元素只會(huì)起到副作用。
狀態(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長度相等的一個(gè)列表dp锁保，第一個(gè)元素為nums的第一個(gè)元素。
空間復(fù)雜度優(yōu)化：由于后一個(gè)dp元素只和前一個(gè)有關(guān)半沽，所以可以把長為n的列表空間縮小為一個(gè)元素的空間
代碼如下：
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
時(shí)間復(fù)雜度：O(n)
解法2：分治算法
將原問題遞歸分為左子問題和右子問題爽柒，分別輸出左子區(qū)間和右子區(qū)間中的最大和連續(xù)子序列的結(jié)果，再計(jì)算跨越中線的最大和連續(xù)子序列結(jié)果者填，三者進(jìn)行比較浩村，輸出最大值作為該層的輸出值。
終止條件：當(dāng)子區(qū)間長度為1時(shí)占哟，直接返回這一個(gè)元素心墅。
代碼如下：
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)
時(shí)間復(fù)雜度：O(nlogn)
分治算法練習(xí)3：
leetcode #169 多數(shù)元素
給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素榨乎。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素怎燥。
你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素蜜暑。
問題可以分解為左子區(qū)間的眾數(shù)铐姚，和右子區(qū)間的眾數(shù)在整個(gè)區(qū)數(shù)內(nèi)統(tǒng)計(jì)各自出現(xiàn)的次數(shù)并進(jìn)行比較，返回多的那個(gè)數(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ū)間只有一個(gè)元素，則直接返回這個(gè)元素
????????????if?left?==?right:
????????????????return?left
????????????# 統(tǒng)計(jì)左子區(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)
時(shí)間復(fù)雜度：O(nlogn)
????????
