分治法：
1. 将问题拆分为几个子问题，并且这些子问题和原问题相似只是量级上小一些。
2. 递归地解决每一个子问题，然后结合这些子问题的解决方案构造出原问题的解决方案。
我们已经遇到过的问题：
1. 二分搜索
2. 归并排序
3. 快速排序
分治法例子：
练习1：快速指数：
能够快速计算出a的n次方
def Fast_pow(a, n): if n == 0: return 1.0 elif n < 0: return 1 / Fast_pow(a, -n) elif n % 2: # 奇数 return Fast_pow(a * a, n // 2) * a else: # 偶数 return Fast_pow(a * a, n // 2) print(Fast_pow(2, 5))
练习2：搜索峰值
数组中没有重复数，但可能存在多个峰值，返回任意一个峰值的index
You may imagine that num[-1] = num[n] = -∞.
def search_peak(alist): return peak_helper(alist, 0, len(alist) - 1) def peak_helper(alist, start, end): if start == end: return start if (start + 1 == end): if alist[start] > alist[end]: return start return end mid = (start + end) // 2 if alist[mid] > alist[mid - 1] and alist[mid] > alist[mid + 1]: return mid if alist[mid - 1] > alist[mid] and alist[mid] > alist[mid + 1]: return peak_helper(alist, start, mid - 1) return peak_helper(alist, mid + 1, end)
alist = [1, 2, 4, 4, 2, 5, 2]
print（search_peak(alist)+1）
练习3： 两数组交集：
给出2个大小不一的数组，找出这两个数组的交集
要求：输出中不能有重复
give nums1 = [1 2 2 1], nums2 = [2, 2], return[2]
def find_extra_fast(arr1, arr2): index = len(arr2) # left and right are end points denoting # the current range. left, right = 0, len(arr2) - 1 while (left <= right): mid = (left + right) // 2; # If middle element is same of both # arrays, it means that extra element # is after mid so we update left to mid+1 if (arr2[mid] == arr1[mid]): left = mid + 1 # If middle element is different of the # arrays, it means that the index we are # searching for is either mid, or before # mid. Hence we update right to mid-1. else: index = mid right = mid - 1; # when right is greater than left our # search is complete. return index
练习4： 计算逆序对
对数组做逆序对计数 - 距离数组的排序结果还有多远。如果一个数组已经排好序，那么逆序对个数为0
在形式上，如果有两个元素a[i], a[j],如果a[i]>a[j],且i<j,那么a[i]，a[j]构成一个逆序对
例如序列2,4,1,3,5, 有三个逆序对，分别为(2,1),(4,1),(4,3)
def merge(left, right): result = list() i,j = 0,0 inv_count = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 elif left[i] > right[j]: result.append(right[j]) j += 1 inv_count += len(left) - i result += left[i:] result += right[j:] return result, inv_count def count_invert(nums): if len(nums) < 2: return nums, 0 mid = len(nums)//2 left, inv_left = count_invert(nums[:mid]) right, inv_right = count_invert(nums[mid:]) merged, count = merge(left, right) count += (inv_left + inv_right) return merged, count arr = [1, 20, 4, 6, 5] print(count_invert(arr))
练习5：加和值最大的子序列问题
在一个一维数组中找到连续的子序列，且这个子序列的和加值最大
例如，一个数组序列为-2,1，-3,4，-1,2,1，-5,4
则这个序列对应的加和值最大的子序列为4，-1,2,1，加和值为6
def subarray2(alist): #动态规划 result = 0 local = 0 for i in alist: local = max(local + i, i) result = max(result, local) return result def subarray1(alist): #分治法 return subarray1_helper(alist, 0, len(alist)-1) def subarray1_helper(alist, left, right): if(left == right): return alist[left] mid = (left + right) // 2 return max(subarray1_helper(alist, left, mid), subarray1_helper(alist, mid+1, right), max_cross(alist, left, mid, right)) def max_cross(alist, left, mid, right): sum = 0 left_sum = 0 for i in range(mid, left-1,-1): sum += alist[i] if(sum > left_sum): left_sum = sum sum = 0 right_sum = 0 for i in range(mid+1, right+1): sum += alist[i] if(sum > right_sum): right_sum = sum return left_sum + right_sum alist = [-1, 2, -2, 5, -4, 3, 7] print(subarray1(alist))
练习:6：水槽问题
给定一个容量为C升的水槽，初始时给这个水槽装满水。每天都会给水槽中加入I升的水，若有溢出，则舍弃多余的水。另外在第i天,水槽中有i升的水会被喝掉，请计算在哪一天水槽的水被用完。
def water_problem(C, I): i = 1 day = 0 while(C > I): C = min(C - i + I, C) day += 1 i += 1 return day C, I = 5, 2 print(water_problem(C, I))
练习7：奇-偶数换序问题
给定一个含有2n个元素的数组，形式如{a1,a2,a3,...,b1,b2,...bn}，按照{a1,b1,a2,b2,...,an,bn}排序
举例：
输入：arr[] = {1,2,9,15}
输出：1 9 2 15
输入：arr[] = {1,2,3,4,5,6}
输出：1 4 2 5 3 6
def Shuffle_Array(alist, left, right): if(left == right -1): return mid = (left + right) // 2 mmid = (left + mid) // 2 temp = mid + 1 for i in range(mmid + 1, mid + 1): alist[i], alist[temp] = alist[temp], alist[i] temp += 1 Shuffle_Array(alist, left, mid) Shuffle_Array(alist, mid+1, right) a = [1,3,5,7,2,4,6,8] Shuffle_Array(a,0, len(a)-1) for i in range(len(a)): print(a[i], end=" ")
练习8：用最少的步数收集所有硬币
给定几摞硬币，这些硬币相邻排列，我们用最少的步数收集所有的硬币，其中每一步可以沿水平线或者垂直线连续收集
举例：
输入：height[] = [2 1 2 5 1]
数组中每个值代表对应摞的高度，此处给了我们5摞硬币，其中第一摞有2个硬币，第二摞有1个硬币，其余依次对应。
输出：4
def min_Steps(height): def min_Steps_helper(height, left, right, h): if left >= right: return 0 m = left for i in range(left, right): if height[i] < height[m]: m = i return min(right - left, min_Steps_helper(height, left, m, height[m])+ min_Steps_helper(height, m + 1, right, height[m])+ height[m] - h) return min_Steps_helper(height, 0, len(height), 0) height = [2,1,2,5,1] print(min_Steps(height))