代码随想录10:贪心算法

BBigSun 评论198阅读模式

代码随想录10:贪心算法

什么是贪心算法

贪心的本质是选择每一阶段的局部最优,从而达到全局最优。文章源自十年又十年-https://www.bbigsun.com/417.html

贪心的解题步骤

  • 将问题分解为若干子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干,但是,每个孩子最多只能给一块饼干。文章源自十年又十年-https://www.bbigsun.com/417.html

对于每个孩子i,都有一个胃口值g[i],每个饼干j,都有一个大小s[j],当饼干大于孩子的胃口时,孩子才会满足文章源自十年又十年-https://www.bbigsun.com/417.html

输入:g = [1,2,3], s = [1,1]
输出:1
解释:有三个孩子,两个饼干,只能让一个孩子满足文章源自十年又十年-https://www.bbigsun.com/417.html

思路:大饼干优先满足大胃口的孩子,或者小饼干优先满足小胃口的孩子文章源自十年又十年-https://www.bbigsun.com/417.html

def solution(g, s):
    g.sort()
    s.sort()
    i = 0
    for j in range(len(s)):
        if s[j] >= g[i] and i < len(g):
            i += 1
    return i    # 看看最终能满足多少个孩子
文章源自十年又十年-https://www.bbigsun.com/417.html文章源自十年又十年-https://www.bbigsun.com/417.html

纸上得来终觉浅,绝知此事要躬行。

weinxin
17688689121
我的微信
微信扫一扫
BBigSun
  • 本文由 BBigSun 发表于 2023年 3月 31日 08:30:46
  • 转载请务必保留本文链接:https://www.bbigsun.com/417.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定