购物网站素材,国外云服务器厂商,江门市,网站功能定制一文了解分而治之和动态规则算法一、分而治之1、分而治之是什么#xff1f;2、应用场景3、场景剖析#xff1a;归并排序和快速排序二、动态规则1、动态规则是什么#xff1f;2、应用场景3、场景剖析#xff1a;斐波那契数列4、动态规则VS分而治之三、分而治之算法常见应用1… 一文了解分而治之和动态规则算法一、分而治之1、分而治之是什么2、应用场景3、场景剖析归并排序和快速排序二、动态规则1、动态规则是什么2、应用场景3、场景剖析斐波那契数列4、动态规则VS分而治之三、分而治之算法常见应用1、leetcode 374猜数字大小2、leetcode 226翻转二叉树3、leetcode 100相同的树4、leetcode 101对称二叉树四、动态规则算法常见应用1、leetcode 70爬楼梯2、leetcode 198打家劫舍3、leetcode 62不同路径五、结束语众多周知分而治之算法和动态规则算法是前端面试中的“宠儿”。而在我们的日常生活中这两个场景的应用也相对比较广泛。比如分而治之算法常用于翻转二叉树、快速搜索等场景中而动态规则算法则常用于最少硬币找零问题、背包问题等场景中。
在下面的这篇文章中将讲解分而治之和动态规则的常用场景以及对 leetcode 的一些经典例题进行解析。
一、分而治之
1、分而治之是什么
分而治之是算法设计中的一种方法。它将一个问题分成多个和原问题相似的小问题递归解决小问题再将结果合并以解决原来的问题。
2、应用场景
归并排序快速搜索二分搜索翻转二叉树……
3、场景剖析归并排序和快速排序
1场景一归并排序
分把数组从中间一分为二。解递归地递归的对两个子数组进行归并排序。合合并有序子数组。
2场景二快速排序
分选基准按照基准把数组分成两个子数组。解递归地对两个子数组进行快速排序。合对两个子数组进行合并。
二、动态规则
1、动态规则是什么
动态规则是算法设计中的一种方法它将一个问题分解为相互重叠的子问题通过反复求解子问题来解决原来的问题。 看到这里很多小伙伴会想着动态规则和分而治之不是解决同样的问题吗其实不是的。 注意 动态规则解决相互重叠的子问题。 分而治之解决的是相互独立的子问题。 这样说可能还有点抽象稍后将在第3点的时候做详细解析。 2、应用场景
最少硬币找零问题背包问题最长公共子序列矩阵链相乘……
3、场景剖析斐波那契数列
斐波那契数列是一个很典型的数学问题。斐波那契数列指的是这样一个数列 这个数列从第3项开始每一项都等于前两项之和。即
Fibonacci[n]{0,n01,n1Fibonacci[n−1]Fibonacci[n−2],n1Fibonacci[n] \begin{cases} 0,n0 \\ 1,n1 \\ Fibonacci[n-1]Fibonacci[n-2],n1 \end{cases} Fibonacci[n]⎩⎪⎨⎪⎧0,n01,n1Fibonacci[n−1]Fibonacci[n−2],n1
那么我们来梳理一下斐波那契数列是怎么运用动态规则算法的。主要有以下两点
定义子问题F(n)F(n - 1) F(n - 2)反复执行从2循环到n执行上述公式。
4、动态规则VS分而治之
看完上面的内容我们来梳理下动态规则和分而治之的区别。先用一张图展示两者的区别。 大家可以看到左边的斐波那契数列是将所有问题分解为若干个相互重叠的问题每个问题的解法都一样。
而右边的翻转二叉树左右子树是相互独立的需先翻转左右子树且在翻转过程中它们各自翻转互不干扰左子树干左子树的活右子树干右子树的活。
不像斐波那契数列那样每一层都是相互依赖的一层嵌套一层相互重叠。
这就是动态规则和分而治之的区别。
三、分而治之算法常见应用
引用leetcode的几道经典题目来强化分而治之算法。
1、leetcode 374猜数字大小
1题意
这里附上原题链接
猜数字游戏的规则如下
每轮游戏我都会从 1 到 n 随机选择一个数字。 请你猜选出我选的是哪个数字。如果你猜错了我会告诉你你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果返回值一共有 3 种可能的情况-11 或 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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题意
这里附上原题链接
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 2解题思路
两棵树根节点的值相同左子树相同右子树相同。符合“分、解、合”特性。考虑选择分而治之。
3解题步骤
分获取两棵树的左子树和右子树。解递归地判断两棵树的左子树是否相同右子树是否相同。合将上述结果合并如果根节点的值也相同两棵树就相同。
4代码实现
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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指向下一个数的值即dp1dp0 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){// 将第一列全部补上1f[i][0] 1;}for(let j 0; j n; j){// 将第一行全部补上1f[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 的题做多了慢慢就能举一反三了~ 关注公众号 星期一研究室 第一时间关注学习干货更多有趣的专栏待你解锁~如果这篇文章对你有用记得点个赞加个关注再走哦~我们下期见
