分治思想
Divide and Conquer，即为分治法，基于分支递归的一种解决问题的思想方法。
分治分治，“分而治之”的意思，就是把一个复杂的原问题分成一个或多个相同子问题，而每个子问题有可以递归地执行，直到子问题简单到可以直接求解，最后原问题的解即为所有子问题解的合并。
算法步骤
一、Divide
将问题分解为一个或多个子问题。
二、Conquer
递归地解决每个子问题。
三、Combine
合并子问题的结果。
分治的应用
一、mergesort
对一个数组array进行排序。
1、Divide
将数组array分为两个子数组subarray。
2、Conquer
递归地mergesort每个subarray。
3、Combine
对两个已排序的子数组subarray进行合并。
C++实现
//mergesort实现void mergeSort(T array[], int p, int r) {if (p < r) {int q = (p + r) / 2;mergeSort(array, p, q);mergeSort(array, q + 1, r);merge(array, p, q, r);}}
//combinevoid merge(T array[], int p, int q, int r) {if (!(p <= q && q< r)) {return;}int len1 = q - p + 1;int len2 = r - q;T array1[len1];T array2[len2];for (int i = 0; i < len1; i++) {array1[i] = array[p + i];}for (int j = 0; j < len2; j++) {array2[j] = array[q + 1 + j];}int i = 0;int j = 0;int k = p;while (k <= r && i < len1 && j < len2) {if (array1[i] <= array2[j]) {array[k++] = array1[i++];} else {array[k++] = array2[j++];}}while (i < len1) {array[k++] = array1[i++];}while (j < len2) {array[k++] = array2[j++];}}
二、binary search
在一个有序数组array中查找元素x。
1、Divide
将x与数组array的中值进行比较，确定后续待查的子数组subarray。
2、Conquer
递归地在subarray中查找x。
3、Combine
trivial
C++实现
//力扣704题//binarySearch 实现int binarySearch(vector<int>& nums, int p, int q, int x) {if (p <= q) {int mid = p + (q - p) / 2;if (nums[mid] == x) {return mid;} else if (x > nums[mid]) {return recurse(nums, mid + 1, q, x);} else {return recurse(nums, p, mid - 1, x);}} else {return -1;}}
//调用方法binarySearch(nums, 0, nums.size() - 1, x);
三、链表翻转
翻转一个单链表
输入：1->2->3->4->5->6->NULL
输出：6->5->4->3->2->1->NULL
1、Divide
将原始链表分为头节点head与子链表head->next。
2、Conquer
先翻转head节点，然后递归地翻转子链表head->nex。
3、Combine
trivial
C++实现
//力扣206题/*** Definition for singly-linked list.* struct ListNode {*int val;*ListNode *next;*ListNode(int x) : val(x), next(NULL) {}* };*/
ListNode* reverseList(ListNode* head) {return recurse(NULL, head);}ListNode* recurse(ListNode* pre, ListNode* head) {if (head == NULL) {return pre;}ListNode* next = head->next;head->next = pre;return recurse(head, next);}
四、计算x的n次幂
计算x的n次幂，n为整数。
1、Divide
将n分为两个n/2大小的整数。
2、Conquer
递归地计算x的n/2次幂。
3、Combine
将两个结果乘积合并。
C++实现
//力扣50题double quickMul(double x, long long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}
double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
