分治算法详解

1. 什么是分治算法

    分治就是 “分而治之”，其本质就是将原问题分解成规模更小的子问题，然后将子问题求解的结果合并成原问题的答案。其实有很多算法本质上都是这个思想，比如说动态规划通过状态转移方程从子问题的最优解推导出全局的最优解，又比如说递归通过递推关系式将问题不断分解成和原问题相似但是规模更小的子问题。

2. 分治算法的解题步骤

分治的核心思想就是：递归（分解）+ 合并：
     递归分解：将原问题(大问题)分解成和原问题相似的子问题(小问题)。递归分解首先需要明确的就是递归函数的定义（一般和题目给出的函数类似）是什么，先不用管此时函数的内部是怎么实现的，明白函数的定义也就知道了我们需要给函数传递的参数是什么，而这个参数一般就是我们将原问题划分为子问题的依据。拿后面要讲解的归并排序和LeetCode 395.至少有K个重复字符的最长子串来举例：对于归并排序，假设我们有待排序序列：[a, b , c, d, e, f]，很自然就能想到需要定义一个能够对任意长度的待排序序列进行排序的函数，此时的参数就是任意长度的待排序序列，因此将原问题分解就可以通过将待排序序列不断分解为更短的子序列；同样对于至少有K个重复字符的最长子串来说，我们需要求出某个字符串中至少包含K个重复字符的最长子串，我们就可以定义递归函数来做这个事情，于是就有参数任意长度的字符串，所以我们分解原问题也就是将字符串分解不同的子串。
     合并：递归函数会对每个子问题求解出一个子解，合并就是将各个子问题的答案进行合并，求出原问题的答案，注意合并的形式可能是对各子问题的子解求最大值/最小值，也可能是将各子解合并在一起，需要根据具体题目进行分析。

3. 分治算法的例题

归并排序：
    1. 首先我们有待排序序列：4 6 2 3 1 8 7 5；
    2. 分治的第一个步骤就是递归分解原问题，前面我们已经分析了递归函数的作用就是对任意长度的序列进行排序，原问题的分解原带排序序列划分为带排序子序列，划分的方法是通过对半分解，接着涉及到递归中的终止条件，对于待序列排序来说，只包含一个元素的序列本身就有序了，也就是说原问题的分解过程分解到子序列中只包含一个元素就结束了；
    3. 分治的第二个步骤是合并，合并所做的事和分解相反，对于只包含一个元素的最简子序列来说，每个序列都是有序的，合并所做的事就是将各个有序的子序列合并后得到一个规模更大的有序子序列，并且继续合并子序列，直到子序列的大小等于原序列的大小。
下面这个图展示了上述归并排序的分治过程：

下面给出归并排序的代码：

#include<iostream>
#include<vector>
using namespace std;

void merge(int a[], int low, int mid, int high) {
    int* aux = new int[high - low + 1]; // 辅助数组，用来存在排序之前的元素
    for (int i = low; i <= high; i++) {//先将原始数组拷贝到辅助数组中
        aux[i - low] = a[i];
    }

    int i = 0;
    int j = mid - low + 1;
    int k = low;

	//比较[low, mid]和[mid+1, haigh]中的元素，将较小的元素放入排序后的数组（原数组）中
    while (i <= mid - low && j <= high - low) {
        if (aux[i] <= aux[j]) { 
            a[k] = aux[i];
            i++;
            k++;
        }
        else {
            a[k] = aux[j];
            j++;
            k++;
        }
    }
    //以下两个循环只有一个能为真
    //把左半边还剩余部分加入到数组中
    while (i <= mid - low) {
        a[k] = aux[i];
        i++;
        k++;
    }
    //把右半边还剩余部分加入到数组中
    while (j <= high - low) {
        a[k] = aux[j];
        j++;
        k++;
    }
}

void mergesort(int nums[], int low, int high) {
    if (low < high) {
		//分解
        int mid = low + (high - low) / 2;
        mergesort(nums, low, mid);
        mergesort(nums, mid + 1, high);
		//合并
        merge(nums, low, mid, high);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

LeetCode 395.至少有K个重复字符的最长子串

    递归分解：前面我们分析过递归函数的作用就是求任意长度的字符串s至少有K个重复字符的最长子串，并且谈到了原问题的分解是通过把字符串不断划分为子字符串，本题的难点就在子串的划分，如果按照常规的对半划分，就有可能把包含K个字符及以上的字符串划分为两个各不包含K个字符及以上的子串了，这与题意相违背。那该如何划分呢？看下面这个例子：
        1）假设我们有字符串：s = “aadcacdbddaa”，k = 2；
        2）可以看到在字符串 s 中字符 b 只出现一次，因此包含字符 b 的任何子串必不可能是最长子串，最长子串只会在 “aadcacd” 和 “ddaa” 之中；
        3）因此我们首先需要寻找字符串中出现次数少于 K 的字符 c，并把 s 按照 c 分割，这样就能把原问题进行分解了。
        4）接着是递归的终止条件，很明显如果一个子串 t 中的字符个数少于 K 个，那么一定不满足题意，直接返回0即可，另外当子串 t 中不存在字母个数少于 K 个的字母时，此时 t 必满足题意，直接返回子串 t 的长度。
    合并：前面递归分解能够求出各个子串中至少有K个重复字符的最长子串，而题目的意思是求字符串 s 中的最长子串，很明显 s 中的最长子串就是各子串中至少有K个重复字符的最长子串长度的最大值，因此这里的合并是求各子问题的最大值。
接着附上本题的代码：

class Solution {
public:
    int longestSubstring_dfs(string s, int k, int left, int right){
        if(right - left + 1 < k) return 0; //递归结束条件
        //统计个字母出现次数
        vector<int> count(26, 0); 
        for(int i = left; i <= right; i++)
            count[s[i] - 'a']++;
        //寻找字符个数大于0少于K的字母
        char c = 0;
        for(int i = 0 ; i < 26; i++){
            if(count[i] > 0 && count[i] < k){
                c = i + 'a';
                break;
            }
        }
        //如果c还是等于0，说明没有找到字符个数少于K个字母，直接返回当前子串
        if(c == 0) 
            return right - left + 1;

        //按照字母c对字符串s进行划分
        int res = 0;
        int i = left;
        while(i <= right){
            //如果开头的字母就等于c就跳过改字符
            while (i <= right && s[i] == c) 
                    i++;
            //如果当前子串已经不能再分割了，则结束循环
            if (i > right) break;
            
            int start = i;
            //寻找划分子串的结尾位置
            while (i <= right && s[i] != c)
                i++;
            //递归求解子串
            int len = longestSubstring_dfs(s, k, start, i - 1);
            //合并，也就是求各子串中的至少有K个重复字符的最长字串的最大值
            res = max(res, len); 
        }
        return res;
    }

    int longestSubstring(string s, int k) {
        int n = s.size();
        return longestSubstring_dfs(s, k, 0, n-1);
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

下面这些题目也都可以用分治去解题：
    LeetCode 108.将有序数组转为二叉树
    LeetCode 169.多数元素
    LeetCode 105. 从前序与中序遍历构造二叉树
    LeetCode 106.从中序与后序遍历中构造二叉树
    LeetCode 148.排序链表（链表版本的分治排序）

希望看了上面记录的一些笔记后能对你们有一点帮助，觉得不错的话不妨点个赞！