分治法的思想与经典题目
分治法简介
分治法，即“分而治之”，就是将原问题分解为几个规模较小但是类似于原问题的子问题，递归求解这些子问题， 然后再合并这些问题的解来建立原问题的解。
分治法主定理
分治法通常遵守一种通用模式：在解决规模为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)
