做外贸的经常浏览的三个网站,网站怎样备案,工程建设项目管理办法实施细则,佛山行业网站建设一文了解贪心算法和回溯算法在前端中的应用一、贪心算法1、贪心算法是什么#xff1f;2、应用场景3、场景剖析#xff1a;零钱兑换二、回溯算法1、回溯算法是什么#xff1f;2、什么问题适合选用回溯算法解决#xff1f;2、应用场景3、场景剖析#xff1a;全排列三、贪心算… 一文了解贪心算法和回溯算法在前端中的应用一、贪心算法1、贪心算法是什么2、应用场景3、场景剖析零钱兑换二、回溯算法1、回溯算法是什么2、什么问题适合选用回溯算法解决2、应用场景3、场景剖析全排列三、贪心算法常见应用1、leetcode 455分发饼干2、leetcode 122买卖股票的最佳时机四、回溯算法常见应用1、leetcode 46全排列2、leetcode 78子集五、写在最后在我们日常的生活中经常会碰到贪心算法和回溯算法的应用场景。比如贪心算法常应用于最少硬币找零问题分数背包等问题。而回溯算法常用于迷宫求解、N皇后等问题。这两种各有各的优点也各有各的不足。
在下面的这篇文章中将讲解贪心算法和回溯算法的常见应用场景以及分析高频 leetcode 算法题。
一起来学习⑧
一、贪心算法
1、贪心算法是什么
贪心算法是算法设计中的一种方法。期盼通过每个阶段的局部最优选择从而达到全局的最优。结果不一定最优。
2、应用场景
最少硬币找零问题分数背包问题……
3、场景剖析零钱兑换
先用一张图来描述输入输出结果。 从上图中可以看到如果用贪心算法解决零钱兑换问题的话它会先从最大面额的硬币开始拿尽可能多的这种硬币找零。当无法再拿更多这种价值的硬币时开始拿第二大价值的硬币依次继续。
大家可以发现如果是第一种情况确实可以达到理论最优。但是如果是第二种情况的话还有一种更优的解法那就是6 3 3。所以说贪心算法并不总是能得到最优答案。
但是呢虽说不能总是能得到最优答案那我们为什么还有用它呢
比起动态规则算法而言贪心算法更简单、更快。虽然它并不总是能得到最优的答案但是综合来看它相对执行时间来说输出了一个可以接受的解。
二、回溯算法
1、回溯算法是什么
回溯算法是算法设计中的一种方法。回溯算法是一种渐进式寻找并构建问题解决方式的策略。回溯算法会先从一个可能的动作开始解决问题如果不行就回溯选择另一个动作直到将问题解决。
2、什么问题适合选用回溯算法解决
有很多路。这些路里面有死路有活路。通常需要递归来模拟所有的路。
2、应用场景
迷宫老鼠问题数独解题器骑士巡逻问题N皇后问题……
3、场景剖析全排列
先用一张图来战术输入输出的过程。 从上图中可以看到全排列 [1, 2, 3] 三个元素在递归的过程中会有很多种结果比如说[1, 1, 2][1, 2, 1], [1, 2, 2]之类的结果。那么当出现重复元素的时候就会出现死路这个时候就应该回退回去并去寻找下一条路活路走出去。这就是回溯算法要解决的问题。
三、贪心算法常见应用
引用leetcode的几道经典题目来强化贪心算法。
1、leetcode 455分发饼干
1题意
这里附上原题链接
假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。
输入输出示例
输入: g [1,2,3], s [1,1]输出: 1解释: 你有三个孩子和两块小饼干3个孩子的胃口值分别是1,2,3。虽然你有两块小饼干由于他们的尺寸都是1你只能让胃口值是1的孩子满足。所以你应该输出1。
2解题思路
既能满足孩子还消耗最少。先将“较小的饼干”分给“胃口较小”的孩子。
3解题步骤
对饼干数组和胃口数组升序降序。遍历饼干数组找到能满足第一个孩子的饼干。然后继续遍历饼干数组找到能满足第二、三、四、……、n个孩子的饼干。
4代码实现
/*** param {number[]} g 孩子胃口* param {number[]} s 饼干尺寸* return {number}*/
let findContentChildren function(g, s) {// 实现升序排序const sortFunc function(a, b){return a-b;}//对g进行升序排序即从小到大排序g.sort(sortFunc);//对s进行升序排序即从小到大排序s.sort(sortFunc);//定义初始值记录饼干能满足多少个孩子let i 0;//对排序后的饼干进行一一遍历并逐一与孩子的胃口比对如果能满足则对i进行1操作s.forEach(n {if(n g[i]){i 1;}});return i;
};console.log(findContentChildren([1, 2], [1, 2, 3]));2、leetcode 122买卖股票的最佳时机
1题意
这里附上原题链接
给定一个数组 prices 其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
输入输出示例
输入: prices [7,1,5,3,6,4]输出: 7解释: 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。
2解题思路
前提上帝视角知道未来的价格。局部最优建好就收见差就不动不做长远打算。
3解题步骤
新建一个变量用来统计总利润。遍历价格数组如果当前价格比昨天高就是昨天买今天卖否则就不交易。遍历结束后返回所有利润之和。
4代码实现
/*** param {number[]} prices* return {number}*/
let maxProfit function(prices) {//新建一个变量用来统计总利润let profit 0;//遍历价格数组for(let i 1; i prices.length; i){//如果当前价格prices[i]比昨天prices[i - 1]高就是昨天买今天卖//否则说明当前天数没买不进行交易if(prices[i] prices[i - 1]){//遍历过程中不断对利润进行相加profit prices[i] - prices[i-1];}}//遍历结束后返回所有利润之和return profit;
};console.log(maxProfit([7, 5, 4, 7]));四、回溯算法常见应用
引用leetcode的几道经典题目来强化回溯算法。
1、leetcode 46全排列
1题意
这里附上原题链接
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入输出示例
输入: nums [1,2,3]输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
2解题思路
要求①所有排列情况②没有重复元素。有出路、有死路。考虑回溯算法。
3解题步骤
用递归模拟出所有情况。遇到包含重复元素的情况就回溯。收集所有到达递归终点的情况并返回。
4代码实现
/*** param {number[]} nums* return {number[][]}*/
let permute function(nums) {// 1.定义一个变量收集所有结果的情况const res [];const backtrack (path) {// 4.递归的重点收集所有满足题目要求的数组if(path.length nums.length){res.push(path);return;}nums.forEach(n {// 3.在把元素放进去时该数组已有此元素那么此路为死路if(path.includes(n)){return;}backtrack(path.concat(n));});};// 2.递归时传入一个数组backtrack([]);return res;
};console.log(permute([1, 2, 3]));2、leetcode 78子集
1题意
这里附上原题链接
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入输出示例
输入: nums [1,2,3]输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
2解题思路
要求①所有子集②没有重复元素。有出路、有死路。考虑使用回溯算法。
3解题步骤
用递归模拟出所有情况。保证接的数字都是后面的数字。收集所有到达递归终点的情况并返回。
4代码实现
/*** param {number[]} nums* return {number[][]}*/var subsets function(nums) {//1.定义一个变量存放结果const res [];const backtrack (path, l, start) {// 4.到达路径终点时push到结果里面if(path.length l){res.push(path);return;}//3.不断遍历数组并将其添加到path中for(let i start; i nums.length; i){backtrack(path.concat(nums[i]), l, i 1);}}//2.子集的长度有可能是0-nums.length不等for(let i 0; i nums.length; i){// 三个参数分别指路径,路径数组的长度,起始的下标backtrack([], i, 0);}return res;
};console.log(subsets([1, 2, 3]));五、写在最后
贪心算法和回溯算法在前端的面试和笔试中也是非常经典的常考题。贪心算法相较于其他算法来说比较简单而回溯算法涉及到很多溯回问题逻辑较强建议大家在做题目时如果看不懂的情况下可以选择多调试代码一步一步跟着它的思路多调试几遍慢慢就能深入理解其逻辑了。
贪心算法和回溯算法在前端中的应用就讲到这里啦如有不理解或文章有误欢迎评论区留言或私信我交流~ 关注公众号 星期一研究室 第一时间关注技术干货更多有趣的专栏待你解锁~如果这篇文章对你有用记得点个赞加个关注再走哦~我们下期见
