广州做网站的公网站建设三把火科技

广州做网站的公,网站建设三把火科技,惠州中小企业网站制作,公司logo是什么意思哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第九篇#xff01; 小时候排排坐分果果#xff0c;老师总是说“表现好的要多给”。今天这道题就是把这个场景算法化了。#xff08;后续代码示例都改为javascript#xff0c;助力前端面试#xff09; 规则#…哈喽各位我是前端小L。欢迎来到贪心算法专题第九篇 小时候排排坐分果果老师总是说“表现好的要多给”。今天这道题就是把这个场景算法化了。后续代码示例都改为javascript助力前端面试规则每个孩子至少分配到1个糖果。相邻的孩子中评分高的孩子必须获得更多的糖果。难点“相邻”意味着既要看左边又要看右边。 比如[1, 3, 2]中间的3比左边1大所以糖果要比左边多。中间的3比右边2大所以糖果也要比右边多。 如果我们同时考虑两边很容易把自己绕进去。力扣 135. 分发糖果https://leetcode.cn/problems/candy/题目分析输入ratings数组。输出最少需要的糖果总量。例子[1, 0, 2]分发[2, 1, 2]解释中间的0必须有 1 个。左边的1比0高所以给 2 个。右边的2比0高也给 2 个。总共 5 个。核心思维两次贪心 (Two-Pass Greedy)既然同时考虑左右两边很难那我们就把规则拆开一次只考虑一边第一步只看左边 (Left to Right)规则只要ratings[i] ratings[i-1]那么candies[i]就必须比candies[i-1]多一个。操作从左往右遍历。如果评分涨了糖果就在前一个人的基础上1否则评分降了或相等只给保底的1个。第二步只看右边 (Right to Left)规则只要ratings[i] ratings[i1]那么candies[i]就必须比candies[i1]多一个。操作从右往左遍历。关键冲突解决 当我们从右往左遍历时发现ratings[i] ratings[i1]我们本来想把candies[i]设为candies[i1] 1。 但是candies[i]在第一步中已经有了一个数值为了满足左边规则。贪心策略为了同时满足左边和右边的规则我们取最大值。 即candies[i] Math.max(candies[i], candies[i1] 1)。算法流程初始化创建一个长度为n的数组candies默认全部填充1每人至少一个。左 - 右遍历for (let i 1; i n; i)如果ratings[i] ratings[i-1]则candies[i] candies[i-1] 1。右 - 左遍历for (let i n - 2; i 0; i--)如果ratings[i] ratings[i1]则candies[i] Math.max(candies[i], candies[i1] 1)。求和把candies数组里的数加起来。代码实现 (JavaScript)JavaScript/** * param {number[]} ratings * return {number} */ var candy function(ratings) { let n ratings.length; // 每个人至少一个糖果 let candies new Array(n).fill(1); // 1. 先从左往右遍历 (只比较左边的孩子) // 策略如果右边评分比左边高糖果 左边 1 for (let i 1; i n; i) { if (ratings[i] ratings[i - 1]) { candies[i] candies[i - 1] 1; } } // 2. 再从右往左遍历 (只比较右边的孩子) // 策略如果左边评分比右边高糖果 max(当前值, 右边 1) // 注意倒序遍历从倒数第二个开始 for (let i n - 2; i 0; i--) { if (ratings[i] ratings[i 1]) { // 为什么要取 max // candies[i] 目前的值是满足了“左规则”的 // candies[i1] 1 是为了满足“右规则”的 // 要想同时满足左右必须取两者中较大的那个 candies[i] Math.max(candies[i], candies[i 1] 1); } } // 3. 统计总数 let sum 0; for (let i 0; i n; i) { sum candies[i]; } return sum; };深度图解 (脑补)假设ratings [1, 3, 4, 5, 2]初始状态[1, 1, 1, 1, 1]左 - 右31:[1, 2, 1, 1, 1]43:[1, 2, 3, 1, 1]54:[1, 2, 3, 4, 1]25: 不变。结果[1, 2, 3, 4, 1]满足了左边大的比右边多右 - 左比较 5 和 2ratings[3](5) ratings[4](2)。现有candies[3] 4。右边推导candies[4] 1 1 1 2。取 max(4, 2) 4。candies[3]还是 4。说明为了满足左边给的4个已经足够覆盖右边的需求了。比较 4 和 5ratings[2] ratings[3]不处理。...最终[1, 2, 3, 4, 1]和为 11。再看个反例[1, 2, 8, 5, 4](中间有个山峰)左 - 右[1, 2, 3, 1, 1](8比2大给3个5比8小给1个)右 - 左4: 1个5: 比4大max(1, 11) 2。数组变[..., 3, 2, 1]8: 比5大max(3, 21) 3。数组变[..., 3, 2, 1]注意这里 8 既比左边大又比右边大最后它拿了 3 个依然保持了峰值地位。复杂度分析时间复杂度O(N)遍历了两次数组正向一次反向一次求和一次。3N依然是O(N)。空间复杂度O(N)需要一个candies数组来存储结果。总结Hard 题也不过如此这道题之所以被标记为 Hard是因为如果试图在一个循环里搞定左右两边代码会变得极其复杂需要回溯修改。 但一旦使用了**“两次贪心分别处理”**的策略这道题就瞬间降维成了两道 Easy 题的叠加。记住这个套路当你发现一个元素需要同时满足左右两个邻居的约束时试着先满足一边再满足另一边。下一题预告根据身高重建队列接下来这道题LC 406同样是关于**“两个维度”**的权衡。每个人有两个属性h(身高),k(前面比我高的人数)。你需要给所有人重新排队让每个人的k属性都成立。面对这种由(h, k)两个数字控制的乱序队列我们应该先按身高排还是先按人数排 贪心策略教我们核心维度优先次要维度插空。下期见