分而治之算法

作者: 贺鹏飞 分类: 数据可视化,数据结构和算法 发布时间: 2021-04-19 10:36

分而治之是算法设计中的一种方法,算法的一种设计思想。它将一个问题分成多个和原问题相似的小问题,递归解决小问题,再将结果合并一解决原来的问题。

使用场景一: 归并排序

分:把数组从中间一分为二。
解:递归地对两个子数组进行归并排序。
合:合并有序子数组。

使用场景二: 快速排序

分:选基准,按基准把数组分成两个子数组。
解:递归地对两个子数组进行快速排序。
合:对两个子数组进行合并。

举例算法题一:猜数字大小

猜数字游戏的规则如下:

每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):

-1:我选出的数字比你猜的数字小 pick < num 1:我选出的数字比你猜的数字大 pick > num
0:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num
返回我选出的数字。

示例 1:
输入:n = 10, pick = 6
输出:6

示例 2:
输入:n = 1, pick = 1
输出:1

示例 3:
输入:n = 2, pick = 1
输出:1

示例 4:
输入:n = 2, pick = 2
输出:2
 
提示:
1 <= n <= 2^31 – 1
1 <= pick <= n

解题思路

分:计算中间元素,分割数组。
解:递归地在较大或者较小数组进行二分搜索。
合:不需要此步,因为在子数组中搜到就返回了。

解题答案

var guessNumber = function(n){
    const rec = (low,high) =>{
        if(low > high){ return }
        const mid = Math.floor((low+high) / 2);
        const res = guess(mid);
        if(res === 0){
            return mid;
        }else if(res === 1){
            return rec(mid + 1,high);
        }else{
            return rec(1, mid - 1);
        }
    }
    return rec(1,n);
}

解题分析

时间复杂度 O(logn),空间复杂度 O(logn)

举例算法题二:翻转二叉树

翻转一棵二叉树。
示例:
输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路:

  • 先反转左右子树,再将子树换个位置。
  • 符合“分、解、和”特性。
  • 考虑用分而治之来做。

解题步骤:

分:获取左右子树。
解:递归地翻转左右子树。
合:将翻转后的左右子树换个位置放到根节点上。

解题答案:

var invertTree = function(root){
    if(!root){ return null; }
    return {
        val: root.val,
        left: invertTree(root.right),
        right: invertTree(root.left)
    }
}

解题分析:

时间复杂度O(n),空间复杂度 O(n)。

举例算法题三:相同的树

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

输入:p = [1,2], q = [1,null,2]
输出:false

示例 3:

输入:p = [1,2,1], q = [1,1,2]
输出:false

提示:

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

解题思路:

  • 两棵树:根节点的值相同,左子树相同,右子树相同
  • 符合“分、解、和”特性。
  • 考虑用分而治之来做。

解题步骤:

分:获取两个树的左子树和右子树。
解:递归地判断两个数的左子树是否相同,右子树是否相同。
合:将上述结果合并,如果根节点的值也相同,树就相同。

解题答案:

var inSameTree = function(p,q){
    if(!p && !q){ return true} //如果两个都为空
    if( p && q && p.val === q.val && 
        inSameTree(p.left,q.left )&& 
        inSameTree(p.right,q.right)
     ){
         return true;
     }
     return false;
}

举例算法题四:对称二叉树

给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

解题思路:

  • 转化为:左右子树是否镜像。
  • 分解为:树1的左子树和树2的右子树是否镜像,树1的右子树和树2的左子树是否镜像。
  • 符合“分、解、和”特性,考虑用分而治之来做。

解题步骤:

分:获取两个树的左子树和右子树。
解:递归地判断树1的左子树和树2的右子树是否镜像,树1的右子树和树2的左子树是否镜像。
合:如果上述都成立,且根节点值也相同,两个树就镜像。

解题答案:

var isSymmetric = function(root){
    if(!root) return true;
    const isMirror = (l, r) => {
        if(!l && !r) return true;
        if(l && r && l.val === r.val &&
            isMirror(l.left, r.right)&&
            isMirror(l.right, r.left)
          ){
              return true;
          }
          return false;
    }
    return isMirror(root.left, root.right);
}

解题分析:

时间复杂度O(n),空间复杂度 O(LogN)和O(n)。

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注