群内编号：2-木铎铎
博文内容参考自DataWhale开源文档：
LeetCode分类训练 Task 1 分治

---

主要思想

分治算法的主要思想是将原问题递归地分成若干个子问题，直到子问题满足边界条件，停止递归。将子问题逐个击破(一般是同种方法)，将已经解决的子问题合并，最后，算法会层层合并得到原问题的答案。

分治算法的步骤

分：递归地将问题分解为各个的子问题(性质相同的、相互独立的子问题)；
治：将这些规模更小的子问题逐个击破；
合：将已解决的子问题逐层合并，最终得出原问题的解；

分治法适用的情况

原问题的计算复杂度随着问题的规模的增加而增加。
原问题能够被分解成更小的子问题。
子问题的结构和性质与原问题一样，并且相互独立，子问题之间不包含公共的子子问题。
原问题分解出的子问题的解可以合并为该问题的解。

举例：排序中的分治——归并排序

Python归并算法：

def merge(a, b):'''a and b are sublist waited to merge'''mrg = []i = 0j = 0while i < len(a) and j < len(b):if a[i] < b[j]:mrg.append(a[i])i += 1else:mrg.append(b[j])j += 1# once any one of the array is done, stop the loop aboveif i < len(a):mrg += a[i:]elif j < len(b):mrg += b[j:]return mrgdef mergeSort(lst):if len(lst) == 1:return lsts = len(lst) // 2a = mergeSort(lst[:s])b = mergeSort(lst[s:])# lst has been ordered while merging sublistslst = merge(a, b)return lstarr = [5, 7, 9, 3, 6, 1, 4, 2]
print(mergeSort(arr))# [1, 2, 3, 4, 5, 6, 7, 9]

算法应用

169. 多数元素

题目描述

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 [n/2] 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

解题思路

• 确定切分的终止条件

直到所有的子问题都是长度为 1 的数组，停止切分。

• 准备数据，将大问题切分为小问题

递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回

• 处理子问题得到子结果，并合并

1）长度为 1 的子数组中唯一的数显然是众数，直接返回即可。

2）如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。

3）如果他们的众数不同，比较两个众数在整个区间内出现的次数来决定该区间的众数

下面给出一段示例代码，请注意本题目所定义的众数是“在数组中出现次数大于 [n/2] 的元素”，这并不是统计学意义的众数，下面i出的程序也无法求出统计学众数。

class Solution:def majorityElement(self, nums: List[int]) -> int:if len(nums) == 1:return nums[0]else:s = len(nums) // 2a = self.majorityElement(nums[:s])b = self.majorityElement(nums[s:])if a == b:return aelif nums.count(a) > nums.count(b):return aelse:return b

这里举一个例子说明为何求不出统计学众数

lst = [2 ,2 ,2, 4, 4, 4 ,4 ,3, 3, 3]
print(majorityElement(lst))
# 3
'''
显然，4才是真正的众数，这里无法求出正确众数的原因是：
majorityElement()将lst切分为[2 ,2 ,2, 4, 4]和
[4 ,4 ,3, 3, 3]，分别求出其众数为2和3。
之后会看整个lst中2多还是3多，而不会看其他元素，从而导致错误。
这样做在所谓的众数数量多余总元素数量一半是是正确的，
但这个例子中，众数4并不满足这个定义。
'''

53. 最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大为6。

下面给出一个分治法解法，其中有一个问题可能比较难理解，就是说如果最大子序如果穿过中间是否能够正确的问题，答案是肯定的，这也是为什么要从中间点向两边求和的原因，最后一行return max(left,right,max_l+ max_r)中的max_l+ max_r其实就是在解决横跨中点的子数组存在性问题。

class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""# 【确定不断切分的终止条件】n = len(nums)if n == 1:return nums[0]# 【准备数据，并将大问题拆分为小的问题】left = self.maxSubArray(nums[:len(nums)//2])right = self.maxSubArray(nums[len(nums)//2:])# 【处理小问题，得到子结果】#　从右到左计算左边的最大子序和max_l = nums[len(nums)//2 -1] # max_l为该数组的最右边的元素tmp = 0 # tmp用来记录连续子数组的和for i in range( len(nums)//2-1 , -1 , -1 ):# 从右到左遍历数组的元素tmp += nums[i]max_l = max(tmp ,max_l)# 从左到右计算右边的最大子序和max_r = nums[len(nums)//2]tmp = 0for i in range(len(nums)//2,len(nums)):tmp += nums[i]max_r = max(tmp,max_r)# 【对子结果进行合并 得到最终结果】# 返回三个中的最大值return max(left,right,max_l+ max_r)

再给一个比较巧妙的方法

class Solution:def maxSubArray(self, nums: List[int]) -> int:for i in range(1, len(nums)):if nums[i - 1] > 0:nums[i] += nums[i - 1]return max(nums)作者：a_run
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/suan-fa-you-xiao-xing-de-yan-ge-zheng-ming-by-a_ru/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个方法好就好在巧妙地抓住了“出现正数”这个关键。首先因为题目要求的是求除最大和，那么肯定不会出现全是负数的数组，这样一来，正数的出现，以及，保持和始终为正，就成为了判断最大和的重要指标。
我们不妨先假设两个极端情况：

1. 全是正数。显然，这时最大和就是所有数的和；
2. 只有一个正数。显然，这时最大和就是这个正数。

现在我们可以考虑更加复杂的情况，那就是有多个正数，但是正数中间被负数分隔了，这时候就需要考虑第二个指标：保持和始终为正。

举个例子，[2, -1, -1, -2, 8, -1]，结果显然是8，原因是我们一直求和会发现，当索引到达3时，summation为-2，加上8会使总和减小，拿着时候我们放弃掉前面所有的和，直接从8开始考察新的子列，继续求和我们得到7。之后取max()得到了8.

50. Pow(x, n)

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0 n 是 32 位有符号整数，其数值范围是$[−2^{31}, 2^{31} − 1]$。

首先给出一个最直接的想法，不过这个做法在LeetCode上提交会超时：

class Solution:def myPow(self, x: float, n: int) -> float:power = 1if n < 0:x = 1/x for i in range(abs(n)):power *= xreturn power

这就是一个很简单的循环相乘的方法。
我们还有很多优化的空间，我们可以这样想，如果我们要算2的10次方，当我们一个个相乘时，要计算9次乘法，但实际上，$2*2=4$，而$2^{10} =(2^2)^5$，因此我们可以计算4次$2*2$乘积，这样我们总共只进行了5次运算，显然，当n越大，这样省下来的时间就越多，这些时间可以用来多打几把游戏。当然，你可能回想，为什么不计算有多少个$2^3$呢，这样是不是会节省更多时间？写这篇博客的时候，我认为是可以的，但是你必须讨论n被3除以后余数的问题，这比讨论奇数偶数麻烦一点，可能就没有必要了。

优化后代码如下：

class Solution:def myPow(self, x, n):power = 1if n < 0:x = 1/x n = -nif n == 0:return 1if n % 2 == 0:return self.myPow(x*x, n/2)else:return x*self.myPow(x*x, (n-1)/2)