分治法 Divide and Conquer思想及实际应用

分治思想

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);
        }
    }

//combine
void 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);
}