分治算法：

what: 是一个将母问题分为相同子问题来简化计算的算法

How: 基本有三步，

将问题转化为相同的小问题
递归解相同的小问题
将上述小问题的结果综合并返回

Why:

主要是重复利用堆栈，效率上的提升主要是针对计算数量级逐级快速递增的，解决的问题主要是计算量大

POW(X,n)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 数据预处理
        res = 1.0 
        if n ==0:
            return res
        if n < 0:
            x = 1 /x
            n = -n 
        # 问题划分
        if n%2 == 0:
            res = self.myPow(x*x, n/2)
            return res
        else:
            res1 = self.myPow(x, n-1)
            # 集合所有的结果
            res = res1*x
            return res

注意：

从解决问题的角度，算法只用

def myPow(self, x: float, n: int) -> float:
    # 数据预处理
    res = 1.0 
    if n ==0:
        return res
    if n < 0:
        x = 1 /x
        n = -n 
    # 问题划分
    res1 = self.myPow(x, n-1)
    # 集合所有的结果
    res = res1*x
    return res

但是会导致一个问题

递归的栈爆了，采取稍微减少点

def myPow(self, x: float, n: int) -> float:
    # 数据预处理
    res = 1.0 
    if n ==0:
        return res
    if n == 1:
        return x
    if n == -1:
        return 1.0/x
    if n < 0:
        x = 1 /x
        n = -n 
    # 问题划分
    if n%2 == 0:
        res = self.myPow(x*x, n//2)
        return res
    else:
        res1 = self.myPow(x*x, (n-1)//2)
        # 集合所有的结果
        res = res1*x
        return res

53. 最大子序和

分治思路：

一个序列中的最大子序列和可以分为三个部分，左半部分的子序列和，右半部分的子序列和，从中间开始的最大子序和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 结束条件
        if len(nums) == 1:
            return nums[0]
        if nums is None or len(nums) == 0:
            return None
        # 划分子问题
        max_sum_l = self.maxSubArray(nums[:len(nums)//2])
        max_sum_r = self.maxSubArray(nums[len(nums)//2:])
        # 从中间开始
        m_left = nums[len(nums)//2 - 1]
        m_right = nums[len(nums)//2]
        temp = 0
        for i in range(len(nums)//2 - 1, -1, -1):
            temp += nums[i]
            m_left = max(m_left, temp)
        temp = 0
        for i in range(len(nums)//2, len(nums)):
            temp += nums[i]
            m_right = max(m_right, temp)
        return max(max_sum_l, max_sum_r, m_right+m_left)

这个算法不是很好，计算的复杂度还是O（n）的，因为每一次的决策是否加入后面的序列可以根据上一次的计算结果，采用动态规划也可以，提前算好每一次前几个序列和和，还可以减少空间复杂度

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        # 存储每一步的最优结果
        dp[0] = nums[0]
        max_num = nums[0]
        for i in range(1, len(nums)):
            # 对于每一次更新加入i个数字后的序列的最佳子序列和
            dp[i] = max(dp[i-1]+nums[i], nums[i])
            if dp[i] > max_num:
                max_num = dp[i]
        return max_num

169. 多数元素

对于这种求出现次数的问题，python中collection模块中的Count 很好用, 但是本文没有使用该方法，一个简单的思路是用一个dict来统计出现的次数，然后便利这个字典求出最大次数的即可

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        table = {}
        for i in nums:
            if i in table.keys():
                table[i] += 1
            else:
                table[i] = 1
        max_freq = 0

        for key in table.keys():
            if table[key] > max_freq:
                max_freq = table[key]
                temp = key
        return temp

但是这个不是我们的目标，我们的目标是学会利用分治的思想

传统的分治思想对于数组来说，基本上就是从空间上划数组的范围达到分解问题再组合，这个题目其实利用了一个假设，就是如果一个数字出现的次数最多，要么在左边数量最多，要么在右边数量最多

按照这个假设就可以做题了，首先分为两个部分，然后再来求两边的哪一个最大，如果分到只剩下这一个就返回这个数值

def majorityElement(self, nums) -> int:
    if nums is None:
        return None
    if len(nums) == 1:
        return nums[0]
    left = self.majorityElement(nums[: len(nums) // 2])
    right = self.majorityElement(nums[len(nums) // 2:])
    if right == left:
        return right
    else:
        # N+N
        return right if nums.count(right) > nums.count(left) else left

使用分治的算法其实相比哈希的方法更慢，因为最后都有个查询次数的遍历，反而计算量更大

最佳的办法还是使用Conter 方法最快，然后使用most_commen 函数找最常见的，然后返回

from collections import Counter
   def majorityElement(self, nums) -> int:
        c = Counter(nums)
        return c.most_common(1)[0][0]

还有利用条件n/2 的，先排序再取中间值，虽然速度很快，但是计算复杂度是nlog(n)的，速度快只是运气好主频高而已