【LeetCode-135】分发糖果(贪心)

这篇具有很好参考价值的文章主要介绍了【LeetCode-135】分发糖果(贪心)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode135.分发糖果

题目描述

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中,评分高的孩子必须获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

示例 1:

  • 输入: [1,0,2]
  • 输出: 5
  • 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

  • 输入: [1,2,2]
  • 输出: 4
  • 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这已满足上述两个条件。
解法1:贪心

这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼

先确定右边评分大于左边的情况(也就是从前向后遍历)

此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个,所以贪心:candyVec[i] = candyVec[i - 1] + 1

代码如下:

// 从前向后
for (int i = 1; i < ratings.size(); i++) {
    if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}

如图:
【LeetCode-135】分发糖果(贪心),LeetCode,leetcode,算法,职场和发展,贪心算法,java

再确定左孩子大于右孩子的情况(从后向前遍历)

遍历顺序这里有同学可能会有疑问,为什么不能从前向后遍历呢?

因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果,所以 要从后向前遍历。

如果从前向后遍历,rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。如图:
【LeetCode-135】分发糖果(贪心),LeetCode,leetcode,算法,职场和发展,贪心算法,java

所以确定左孩子大于右孩子的情况一定要从后向前遍历!

如果 ratings[i] > ratings[i + 1],此时candyVec[i](第i个小孩的糖果数量)就有两个选择了,一个是candyVec[i + 1] + 1(从右边这个加1得到的糖果数量),一个是candyVec[i](之前比较右孩子大于左孩子得到的糖果数量)。

那么又要贪心了,局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。

局部最优可以推出全局最优。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 1]的糖果多
【LeetCode-135】分发糖果(贪心),LeetCode,leetcode,算法,职场和发展,贪心算法,java文章来源地址https://www.toymoban.com/news/detail-819633.html

代码实现
class Solution {
    /**
         分两个阶段
         1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 1
         2、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大
    */
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyVec = new int[len];
        candyVec[0] = 1;
        for (int i = 1; i < len; i++) {
            candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
        }

        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int num : candyVec) {
            ans += num;
        }
        return ans;
    }
}

到了这里,关于【LeetCode-135】分发糖果(贪心)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode刷题笔记【25】:贪心算法专题-3(K次取反后最大化的数组和、加油站、分发糖果)

    参考前文 参考文章: LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和) LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II) LeetCode链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ 首先 sor

    2024年02月09日
    浏览(42)
  • Day34 贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果

    思路 第一步,从前向后遍历,遇到负数将其变为正数,同时K– 第二步:如果K还大于0,那么反复转变数值最小的元素,将K用完 第三步:求和 方法一(暴力) leetcode超时(35/40) 方法二(贪心)

    2024年01月19日
    浏览(40)
  • 第八章 贪心算法 part03 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果 (day34补)

    给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组: 选择某个下标 i  并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后,返回数组 可能的最大和 。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -100

    2024年02月11日
    浏览(34)
  • LeetCode-455-分发饼干-贪心算法

    题目描述: 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] = g[i],我们可以将这个饼干 j 分配

    2024年02月10日
    浏览(41)
  • LeetCode:455. 分发饼干——贪心算法

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 贪心算法是在每个阶段选取 局部 最优解,最终得到 全局最优解 的一种思想。贪心算法与动态规划的思路相似,但贪心算法要在每个阶段选择最优解,而这个最优解不一定是全局最优解

    2023年04月15日
    浏览(37)
  • LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)

    贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。 感觉像

    2024年02月09日
    浏览(50)
  • 【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   findContentChildren ( self ,  g :  List [ int ],  s

    2024年02月04日
    浏览(52)
  • 算法训练day31贪心算法理论基础Leetcode455分发饼干376摆动序列53最大子序和

    文章链接 代码随想录 (programmercarl.com) 说实话贪心算法并没有固定的套路 。 最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧 。 面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了 。 刷题或者面

    2024年02月20日
    浏览(45)
  • 力扣算法刷题Day34|贪心:K次取反后最大化的数组和 加油站 分发糖果

    力扣题目:# 1005.K次取反后最大化的数组和  刷题时长:10min 解题方法:贪心 复杂度分析 时间O(n) 空间O(1) 问题总结 无 本题收获 贪心思路:两次贪心 在包含正负无序的整数数组中,如何转变K次正负,让数组和达到最大 局部最优:让绝对值大的负数变为正数,当前数值达到

    2024年02月09日
    浏览(51)
  • C++力扣题目1005--K次取反后最大化的数组和 134--加油站 135--分发糖果

    力扣题目链接(opens new window) 给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。) 以这种方式修改数组后,返回数组可能的最大和。 示例 1: 输入:A = [4,2,3],

    2024年01月21日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包