PHP算法学习之分治法

发表于 | 更新于 | 分类于
本文字数： 3.1k | 阅读时长 ≈ 3 分钟

思考并回答以下问题：

简介

分治法，顾名思义就是分而治之，即把问题拆解为性质相同的小问题再处理。

分治法除了分治，名字里还少了一步，那就是合，也就是怎样通过小问题的答案得到拆分之前大问题的答案。

分治法的时间复杂度：分治法并没有像二分法一样每次丢掉一半无用的解，它只是做了分离，而分离的两部分都是需要处理的，所以分治法的时间复杂度是O(n)。特例情况是当分离的两部分继续分治处理出现重复计算的情况时，就会比O(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
class TreeNode
{
    public $val;
    public $left;
    public $right;

    function __construct($val, $left = null, $right = null)
    {
        $this->val = intval($val);
        $this->left = $left;
        $this->right = $right;
    }
}

function preorder(TreeNode $root = null)
{
    $result = [];

    // 治：当节点不存在时，返回空数组
    if ($root == null)
    {
        return $result;
    }

    // 分：分别求出当前节点左右子树的前序遍历结果
    $left = preorder($root->left);
    $right = preorder($root->right);

    // 合：因为是前序遍历，所以先添加当前节点的val，然后是左子树右子树
    $result[] = $root->val;
    $result = array_merge($result, $left, $right);

    return $result;
}

2、求二叉树的最大路径和

给一棵二叉树，找出从根节点出发的路径中，和最大的一条。

这条路径可以在任何二叉树中的节点结束，但是必须包含至少一个点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function maxPathSum(TreeNode $root = null)
{
    // 治：当节点不存在时，返回0
    if ($root == null)
    {
        return 0;
    }

    // 分：分别求出当前节点左右子树的最大路径和
    $left = maxPathSum($root->left);
    $right = maxPathSum($root->right);

    // 合：此处有坑，注意左右子树和都为负数的情况
    if ($left < 0 && $right < 0)
    {
        return $root->val;
    }
    else 
    {
        return $root->val + max($left, $right);
    }
}

3、求最近公共祖先

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)，给出的两个节点都在树中存在。

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
function lca(TreeNode $root = null, TreeNode $A, TreeNode $B)
{
    if ($root == null || $root == $A || $root == $B)
    {
        return $root;
    }

    $left = lca($root->left, $A, $B);
    $right = lca($root->right, $A, $B);

    if ($left && $right)
    {
        return $root;
    } 
    elseif($left)
    {
        return $left;
    } 
    elseif($right)
    {
        return $right;
    } 
    else 
    {
        return null;
    }
}

4、快速排序

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
<?php
 
$arr = [25,133,452,364,5876,293,607,365,8745,534,18,33];
 
function quick_sort($arr)
{
    // 判断是否需要继续
    if (count($arr) <= 1) 
    {
        return $arr;
    }
 
    $middle = $arr[0]; // 中间值
 
    $left = array(); // 小于中间值
    $right = array();// 大于中间值
 
    // 循环比较
    for ($i=1; $i < count($arr); $i++) 
    { 
        if ($middle < $arr[$i]) 
        {
            // 大于中间值
            $right[] = $arr[$i];
        } 
        else 
        {
 
            // 小于中间值
            $left[] = $arr[$i];
        }
    }
 
    // 递归排序两边
    $left = quick_sort($left);
    $right = quick_sort($right);
 
    // 合并排序后的数据，别忘了合并中间值
    return array_merge($left, array($middle), $right);
}
 
var_dump($arr);
var_dump(quick_sort($arr));
0%