分治法总结

发表于 分类于 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

分治法总结

什么是分治算法

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 k 个规模较小，并且结构与原问题相似的子问题，递归 地解决这些子问题，然后再合并其结果，就得到原问题的解。

关于分治和递归的区别：

  • 分治算法是一种处理问题的思想;
  • 递归是一种编程技巧。

比较经典的应用就是归并排序（Merge Sort)以及 快速排序（Quick Sort)。

算法特征

分治所能解决的问题一般具有以下几个特征：

  1. 该问题的规模缩小到一定的程度 可以直接求解
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质
  3. 利用该问题分解出的子问题的解 可以合并 为该问题的解
  4. 该问题所分解出的各个子问题是相互独立的，即 子问题之间不包含公共的子问题

说明：

  1. 第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
  2. 第二条特征是应用分治算法的前提，他也是大多数问题可以满足的，此特征反映了 递归思想 的引用；
  3. 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心算法或动态规划法；
  4. 第四条特征涉及到 分治的效率，如果各子问题是不独立的，则分治要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治，但 一般用动态规划较好。

设计思路

设计过程分为三个步骤：

实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

  • 拆分 Divide：将原问题拆分成若干个子问题；
  • 解决 Conquer：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
  • 合并 Merge：将各个子问题的解合并，形成原问题的解。

分治的执行步骤可以分为三个阶段，即划分数据阶段、递归处理阶段和综合合并阶段。有些问题的划分阶段时间费用较多，有些问题则合并阶段的时间费用较多。

用分治解决： JZ33 二叉搜索树的后序遍历序列 问题

题目链接

题目：

分治法解决思路：

后序遍历顺序是左右根。所以一个要判断的数组的最后一个肯定是根。按照搜索树的性质可以找到比根小的结点：左子树。以及比根大的结点：右子树。问题就拆分成了判断左子树是否满足bst，以及判断右子树是否满足bst。最窄merge的条件是左子树是bst且右子树是bst。

解题代码：

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
#include <iterator>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size()==0){
            return false;
        }
        bool ret=versubtask(sequence, 0, sequence.size()-1);
        return ret;
    }
    bool versubtask(vector<int> sequence,int left,int right){         
         if(left>right){
            return true;
         }
         int rootval=sequence[right];
         int leftnew1=left;
         int rightnew1=left;
         while(rightnew1<right&&sequence[rightnew1]<rootval){
            rightnew1++;
         }    
         rightnew1=rightnew1-1;//重要
         
         int leftnew2=rightnew1+1;
         bool rightdata;
         //**重要** 检查右子树是否存在小于root的结点
         for(int i=leftnew2;i<right;i++){
            if (sequence[i]<rootval){
                return false;
            }
         }      
         bool leftdata=versubtask(sequence,leftnew1,rightnew1);
         //当右子树满足都大于根的条件时检查右子树是否是bst
         if(leftnew2<right){
             int rightnew2=right-1;
             rightdata=versubtask(sequence,leftnew2,rightnew2);  
         }
         else {
         {
           rightdata=true;
         }
         }
         return leftdata&&rightdata;
    }
};