算法通关村第十七关:青铜挑战-贪心其实很简单

这篇具有很好参考价值的文章主要介绍了算法通关村第十七关:青铜挑战-贪心其实很简单。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

青铜挑战-贪心其实很简单

1. 难以解释的贪心算法

贪心学习法则:直接做题,不考虑贪不贪心

贪心(贪婪)算法
是指在问题尽心求解时,在每一步选择中都采取最好或者最优(最有利)的选择,从而希望能够导致结果最好或者最优的算法

贪心算法所得到的结果不一定是最优的结果,但是都是相对近似最优解的结果

怎么知道什么时候改用贪心呢?
要求要解决的问题具有“最优子结构”

贪心怎么学?
将常见的贪心题都找出来看看大致是什么样子的,学一学就行了

贪心常见的应用场景?

  1. 排序问题:选择排序、拓扑排序
  2. 优先队列:堆排序
  3. 赫夫曼压缩编码
  4. 图里的 Prim、Fruska和Dijkstra算法
  5. 硬币找零问题
  6. 分数背包问题
  7. 并查集的按大小或者高度合并问题,或者排名
  8. 任务调度部分场景
  9. 一些复杂的近似算法

2. 贪心问题举例

2.1 分发饼干

LeetCode 455
https://leetcode.cn/problems/assign-cookies/

思路分析

既要满足小孩的胃口,也不要造成饼干的浪费;
大饼干既可以满足胃口大的孩子,也可以满足胃口小的孩子,就应该优先满足胃口大的;

局部最优:大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个
全局最优:喂饱尽可能多的孩子

贪心策略:考虑胃口,大饼干先喂饱大胃口,最后看能满足几个孩子的需要

  • 先将饼干数组和小孩数组排序
  • 然后从后向前比那里小孩数组,用大饼干优先满足胃口大的,并统计满足孩子的数量

算法通关村第十七关:青铜挑战-贪心其实很简单,算法

代码实现

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort(reverse=True)
        s.sort(reverse=True)
        s_len = len(s)
        s_index = 0
        count = 0
        for i in g:
            if s_index < s_len and i <= s[s_index]:
                s_index += 1
                count += 1
        return count
2.2 柠檬水找零

LeetCode860
https://leetcode.cn/problems/lemonade-change/

思路分析

分析下主要有三种情况

  1. 给的是5,直接收下
  2. 给的是10,给出1个5,此时必须要有1个5才行
  3. 给的是20,优先消耗1个10,再给1个5。如果没有10,给出3个5

局部最优:遇到账单20,优先消耗10,完成本次找零。10只能给20找零,5更万能

代码实现

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        count_5 = 0
        count_10 = 0

        for money in bills:
            if money == 5:
                count_5 += 1
            elif money == 10:
                count_5 -= 1
                count_10 += 1
            elif money == 20:
                if count_10 > 0:
                    count_10 -= 1
                    count_5 -= 1
                else:
                    count_5 -= 3
            if count_5 < 0 or count_10 < 0:
                return False
        return True
                
2.3 分发糖果

LeetCode 135
https://leetcode.cn/problems/candy/

思路分析

每个孩子至少一个糖果
相邻孩子评分更高的获得更多的糖果

  • 第一轮,从左到右
    • 只要右边的比左边的大,就一直加1
    • 如果右边比左边小,就设置为1
  • 第二轮,从右到左
    • 如果左边的比右边的大,在{i+1}的基础上,先加1再赋值给{i}
  • 每个位置i,从left[i]和right[i]中选最大就行了
第一轮
下标 0 1 2 3 4 5 6
得分 1 2 2 5 4 3 2
糖果 1 2 1 2 1 1 1

第二轮
下标 0 1 2 3 4 5 6
得分 1 2 2 5 4 3 2
糖果 1 2 1 4 3 2 1

选取最大
下标 0 1 2 3 4 5 6
得分 1 2 2 5 4 3 2
糖果 1 2 1 4 3 2 1




第一轮
下标 0 1 2 3 4
得分 1 3 4 5 2
糖果 1 2 3 4 1

第二轮
下标 0 1 2 3 4
得分 1 3 4 5 2
糖果 1 2 3 2 1

选取最大
下标 0 1 2 3 4
得分 1 3 4 5 2
糖果 1 2 3 4 1

代码实现文章来源地址https://www.toymoban.com/news/detail-700174.html

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy_list = [0] * n

        candy_list[0] = 1 
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candy_list[i] = candy_list[i-1] + 1
            else:
                candy_list[i] = 1
        
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                candy_list[i] = max(candy_list[i+1] + 1, candy_list[i])

        return sum(candy_list)

到了这里,关于算法通关村第十七关:青铜挑战-贪心其实很简单的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • [Go版]算法通关村第一关青铜——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月13日
    浏览(39)
  • 算法通关村第一关-链表青铜挑战笔记

    平时我们一般都是用数组,每个数组都会有一个相对应的索引,这样就使得数组能够方便的调用出对应索引得到需要的数据,但是这也造成了一个问题,那就是不好在数组中插入或者删除一个数据,例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就

    2024年02月15日
    浏览(43)
  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(43)
  • 《算法通关村第一关——链表青铜挑战笔记》

    链表中每个结点内部的“生态环境”。 数据域存储元素的值,指针域存放指针。 示例: c语言构造链表 可分为三步 1.创建头指针。 2.创建头结点,使头指针指向头结点。 3.循环创建结点,并使前一个结点指向当前结点。 1.)创建结点。 2.)使前一个结点指向当前结点。 3.)

    2024年02月15日
    浏览(40)
  • 算法通关村第一关———链表青铜挑战笔记

    通过类来构建节点,用next指针将节点连起来。 会有插入位置的范围问题,不能超出链表范围 会有删除位置的范围问题 构造双向链表 插入和删除都有三种情况,头中尾  

    2024年02月15日
    浏览(44)
  • 算法通关村第一关--链表青铜挑战笔记

    开始时间:2023年7月16日20:45:26 什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是hea

    2024年02月17日
    浏览(44)
  • 算法通关村第一关 | 链表青铜挑战笔记

    一、 什么是链表? 链表是一种比较简单、很常见的数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 二、链表的特点 链表是一种比较简单、很常见的数据结构,是线性表(List)的一种,是一种物理存

    2024年02月14日
    浏览(38)
  • 算法通关村第一关——链表青铜挑战笔记(单链表)

    在LeeCode中一般这样创建链表 要注意创建一个变量来遍历,不要把head丢掉了 count position - 1可以方便操作,还能防止下标越界(cur为null)

    2024年02月15日
    浏览(39)
  • 【无标题】算法通关村第一关——链表青铜挑战笔记

    算法通关村第一关——链表青铜挑战笔记 C语言是如何构造出链表的 0.定义节点结构 1.建立头指针 2.建立temp指针 3.将节点连起来 3.1 把p指向temp 3.2 设立循环节点a+temp指向a+temp变为a

    2024年02月15日
    浏览(36)
  • [Go版]算法通关村第一关——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月15日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包