一文了解分而治之和动态规则算法在前端中的应用

简介: 该文章详细介绍了分而治之策略和动态规划算法在前端开发中的应用,并通过具体的例子和LeetCode题目解析来说明这两种算法的特点及使用场景。

分而治之和动态规则

众多周知,分而治之算法和动态规则算法是前端面试中的“宠儿”。而在我们的日常生活中,这两个场景的应用也相对比较广泛。比如,分而治之算法常用于翻转二叉树、快速搜索等场景中,而动态规则算法,则常用于最少硬币找零问题、背包问题等场景中。

在下面的这篇文章中,将讲解分而治之和动态规则的常用场景以及对 leetcode 的一些经典例题进行解析。

一、分而治之

1、分而治之是什么?

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

2、应用场景

  • 归并排序
  • 快速搜索
  • 二分搜索
  • 翻转二叉树
  • ……

3、场景剖析:归并排序和快速排序

(1)场景一:归并排序

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

(2)场景二:快速排序

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

二、动态规则

1、动态规则是什么?

  • 动态规则是算法设计中的一种方法;
  • 它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。

看到这里,很多小伙伴会想着,动态规则和分而治之不是解决同样的问题吗?其实不是的。

注意:

  • 动态规则解决相互重叠的子问题。

  • 分而治之解决的是相互独立的子问题。

这样说可能还有点抽象,稍后将在第3点的时候做详细解析。

2、应用场景

  • 最少硬币找零问题
  • 背包问题
  • 最长公共子序列
  • 矩阵链相乘
  • ……

3、场景剖析:斐波那契数列

斐波那契数列是一个很典型的数学问题。斐波那契数列指的是这样一个数列:

斐波那契数列

这个数列从第3项开始,每一项都等于前两项之和。即:

Fibonacci[n]= $\begin{cases} 0,n=0 \\ 1,n=1 \\ Fibonacci[n-1]+Fibonacci[n-2],n>1 \end{cases}$ ​

那么我们来梳理一下,斐波那契数列是怎么运用动态规则算法的。主要有以下两点:

  • 定义子问题:F(n)=F(n - 1) + F(n - 2);
  • 反复执行:从2循环到n,执行上述公式。

4、动态规则VS分而治之

看完上面的内容,我们来梳理下动态规则和分而治之的区别。先用一张图展示两者的区别。

动态规则和分而治之的区别

大家可以看到,左边的斐波那契数列是将所有问题分解为若干个相互重叠的问题,每个问题的解法都一样。

右边的翻转二叉树,左右子树是相互独立的,需先翻转左右子树,且在翻转过程中,它们各自翻转,互不干扰,左子树干左子树的活,右子树干右子树的活。

不像斐波那契数列那样,每一层都是相互依赖的,一层嵌套一层,相互重叠。

这就是动态规则和分而治之的区别。

三、分而治之算法常见应用

引用leetcode的几道经典题目来强化分而治之算法

1、leetcode 374:猜数字大小

(1)题意

这里附上原题链接

猜数字游戏的规则如下:

  • 每轮游戏,我都会从 1n 随机选择一个数字。 请你猜选出我选的是哪个数字。
  • 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):

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

返回我选出的数字。

(2)解题思路

  • 二分搜索,同样具备“分、解、合”的特性。
  • 考虑选择分而治之。

(3)解题步骤

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

(4)代码实现

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return                 -1 if num is lower than the guess number
 *                         1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
let guessNumber = function(n) {
   

    const rec = (low, high) => {
   
        if(low > high){
   
            return;
        }

       // 1.计算中间元素,分割数组
        const mid = Math.floor((low + high) / 2);

        // 2.与猜测的数字进行比较
        const res = guess(mid);

        // 3.递归地在较大或者较小子数组进行二分搜索
        if(res === 0){
   
            return mid;
        }else if(res === 1){
   
            return rec(mid + 1, high);
        }else{
   
            return rec(low, mid - 1);
        }
    }
    return rec(1, n);
};

2、leetcode 226:翻转二叉树

(1)题意

这里附上原题链接

翻转一棵二叉树。

翻转二叉树

(2)解题思路

  • 先翻转左右子树,再将子树换个位置。
  • 符合“分、解、合”特性。
  • 考虑选择分而治之。

(3)解题步骤

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

(4)代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
 var invertTree = function(root) {
   
    if(!root){
   
        return null;
    }
    return{
   
        //1.根节点值不变
        val:root.val,
        //2.递归地将左子树与右子树结点变换
        left:invertTree(root.right),
        //3.递归地将右子树与左子树结点变换
        right:invertTree(root.left)
    }
};

3、leetcode 100:相同的树

(1)题意

这里附上原题链接

给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

相同的树

(2)解题思路

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

(3)解题步骤

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

(4)代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
let isSameTree = function(p, q) {
   
    if(!p && !q){
   
        return true;
    }
    /**
     * 判断条件:
     * 1.p树和q树同时存在;
     * 2.每遍历一个节点,两棵树的节点值都存在;
     * 3.递归左子树,比较每个节点值;
     * 4.递归右子树,比较每个节点值。
     */
    if(p && q && p.val === q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    ){
   
        return true;
    }
    return false;
};

4、leetcode 101:对称二叉树

(1)题意

这里附上原题链接

给定一个二叉树,检查它是否是镜像对称的。

对称二叉树

(2)解题思路

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

(3)解题步骤

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

(4)代码实现

let isSymmetric = function(root){
   
    if(!root){
   
        return true;
    }

    const isMirror = (l, r) => {
   
        if(!l && !r){
   
            return true;
        }

        /**
         * 判断条件:
         * 1.左子树和右子树同时存在;
         * 2.左子树和右子树的根节点相同;
         * 3.左子树的左节点和右子树的右节点镜像相同;
         * 4.左子树的右结点和右子树的左结点镜像相同
         */
        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);
}

四、动态规则算法常见应用

引用leetcode的几道经典题目来强化动态规则算法

1、leetcode 70:爬楼梯

(1)题意

这里附上原题链接

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

**注意:**给定 n 是一个正整数。

(2)解题思路

  • 爬到第n阶可以在第n - 1阶爬1个台阶,或者在第n - 2阶爬2个台阶。
  • F(n) = F(n - 1) + F(n - 2)。
  • 使用动态规则。

(3)解题步骤

  • 定义子问题:F(n) = F(n - 1) + F(n - 2)。
  • 反复执行:从2循环到n,执行上述公式。

(4)代码实现

 /*
 * @param {number} n
 * @return {number}
 */
// 数组方法
var climbStairs = function(n) {
   
    if(n < 2){
   
        return 1;
    }
     // 记录第0阶和第1阶可以走多少步
    const dp = [1, 1];
    // 从第2阶开始遍历,直至第5阶
    for(let i = 2; i <= n; i++){
   
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

如果dp用一维数组来记录的话,时间复杂度和空间复杂度都为O(n),这样子的话效率还是偏低的。

那么有什么方法可以来降低它的复杂度呢?

可以采用变量的方法。从上面的代码中我们可以看出,dp的值用一个数组存着,一直在线性增长。那么这个时候我们可以考虑把这个一维数组变换成单变量的形式,不断进行替换,来降低空间复杂度

下面用代码实现一遍。

let climbStairs2 = function(n){
   
    if(n < 2){
   
        return 1;
    }
    //定义一个变量,记录 n - 2 时的台阶数
    let dp0 = 1;
    //定义一个变量,记录 n - 1 时的台阶数
    let dp1 = 1;
    for(let i = 2; i <= n; i++){
   
        const temp = dp0;
        //每遍历一次,就让dp0指向下一个数的值,即dp1
        dp0 = dp1;
        //每遍历一次,就让dp1指向dp1下一个数的值,即前两个数的和,也就是dp1和原来dp0的值
        dp1 = dp1 + temp;
    }
    return dp1;
}

从上面的代码中可以看出,没有了数组或者像矩阵一样线性增长的数组,空间复杂度就变为了O(1)。

2、leetcode 198:打家劫舍

(1)题意

这里附上原题链接

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

(2)解题思路

  • f(k) = 从前k个房屋中能偷窃到的最大数额。
  • Ak = 第k个房屋的钱数。
  • f(k) = max(f(k - 2) + Ak, f(k - 1))。
  • 考虑使用动态规则。

(3)解题步骤

  • 定义子问题:f(k) = max(f(k - 2) + Ak, f(k - 1))。
  • 反复执行:从2循环到n,执行上述公式。

(4)代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */

let rob1 = function(nums) {
   
    if(nums.length === 0){
   
        return 0;
    }
    // 前0个房屋和前1个房屋能劫持到的金钱数
    const dp = [0,nums[0]];
    for(let i = 2; i <= nums.length; i++){
   
        dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    }
    return dp[nums.length];
};

与爬楼梯同样,如果dp用一维数组来记录的话,时间复杂度和空间复杂度都为O(n),这样子的话效率还是偏低的。

那这个时候就可以采用单变量的方法,来降低空间复杂度

下面用代码实现一遍。

let rob2 = function(nums) {
   
    if(nums.length === 0){
   
        return 0;
    }
    let dp0 = 0;
    let dp1 = nums[0];
    for(let i = 2; i <= nums.length; i++){
   
        const dp2 = Math.max(dp0 + nums[i - 1], dp1);
        dp0 = dp1;
        dp1 = dp2;
    }
    return dp1;
};

此时空间复杂度自然也就变为O(1)了。

3、leetcode 62:不同路径

(1)题意

这里附上原题链接

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

不用路径

(2)解题思路

  • 每一步只能向下或者向右移动一步,因此想要走到(i,j),如果向下走一步,那么从(i-1,j)走过来;如果向右走一步,那么从(i,j-1)走过来。
  • f(i, j) = f(i-1, j) + f(i, j-1)。
  • 使用动态规则。

(3)解题步骤

  • 定义子问题:f(i, j) = f(i-1, j) + f(i, j-1)。
  • 反复执行:从2循环到n,执行上述公式。

(4)代码实现

let uniquePaths = function(m, n){
   
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i = 0; i < m; i++){
   
        // 将第一列全部补上1
        f[i][0] = 1;
    }
    for(let j = 0; j < n; j++){
   
        // 将第一行全部补上1
        f[0][j] = 1;
    }

    for(let i = 1; i < m; i++){
   
        for(let j = 1; j < n; j++){
   
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}

五、结束语

分而治之和动态规则算法在前端中的应用还是挺多的,特别是在面试或笔试的时候会经常出现这类题目,大家可以在此之外再继续多刷刷此类 leetcode 的题,做多了慢慢就能举一反三了~

  • 关注公众号 星期一研究室 ,第一时间关注学习干货,更多有趣的专栏待你解锁~
  • 如果这篇文章对你有用,记得点个赞加个关注再走哦~
  • 我们下期见!🥂🥂🥂
相关文章
|
16天前
|
移动开发 缓存 前端开发
深入理解前端路由:原理、实现与应用
本书《深入理解前端路由:原理、实现与应用》全面解析了前端路由的核心概念、工作原理及其实现方法,结合实际案例探讨了其在现代Web应用中的广泛应用,适合前端开发者和相关技术人员阅读。
|
19天前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
18天前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
37 1
|
18天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
47 1
|
22天前
|
自然语言处理 前端开发 JavaScript
深入理解前端中的 “this” 指针:从基础概念到复杂应用
本文全面解析前端开发中“this”指针的运用,从基本概念入手,逐步探讨其在不同场景下的表现与应用技巧,帮助开发者深入理解并灵活掌握“this”的使用。
|
22天前
|
存储 前端开发 JavaScript
前端中对象的深度应用与最佳实践
前端对象应用涉及在网页开发中使用JavaScript等技术创建和操作对象,以实现动态交互效果。通过定义属性和方法,对象可以封装数据和功能,提升代码的组织性和复用性,是现代Web开发的核心技术之一。
|
23天前
|
JavaScript 前端开发 测试技术
构建高效可维护的前端应用
构建高效可维护的前端应用
|
19天前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法及应用
探索人工智能中的强化学习:原理、算法及应用
|
12天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
19天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。