当前位置: 首页 > news >正文

算法题:分发饼干

这个题目是贪心算法的基础练习题,解决思路是排序+双指针+谈心法,先将两个数组分别排序,优先满足最小胃口的孩子。(本题完整题目附在了最后面)

代码如下:

class Solution(object):def findContentChildren(self, g, s):if not s: return 0g.sort()s.sort()pos_g, pos_s, n_satisfy = 0, 0, 0while pos_g < len(g) and pos_s < len(s):if g[pos_g] <= s[pos_s]:n_satisfy += 1pos_g += 1pos_s += 1else:pos_s += 1return n_satisfyif __name__ == '__main__':sol = Solution()print(sol.findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]))

完整题目:

455. 分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

 

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示:

  • 1 <= g.length <= 3 * 10^4
  • 0 <= s.length <= 3 * 10^4
  • 1 <= g[i], s[j] <= 2^31 - 1
http://www.lryc.cn/news/183913.html

相关文章:

  • WebSocket编程golang
  • PHP之redis 和 memache面试题
  • java socket实现代理Android App
  • Nacos与Eureka的区别
  • 浅谈Rob Pike的五条编程规范
  • LeetCode 377.组合总和IV 可解决一步爬m个台阶到n阶楼顶问题( 完全背包 + 排列数)
  • C中volatile总结
  • asp.net班级管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio
  • 【Pytorch笔记】6.Transforms
  • nodejs+vue临沂特色产品销售平台elementui
  • 机器学习必修课 - 使用管道 Pipeline
  • WEB各类常用测试工具
  • Naive UI 文档地址
  • 在CentOS7系统中安装MySQL5.7
  • R语言通过接口获取网上数据平台的免费数据
  • 【Docker内容大集合】Docker从认识到实践再到底层原理大汇总
  • 算法题:摆动序列
  • 复习 --- QT服务器客户端
  • Godot 官方2D游戏笔记(1):导入动画资源和添加节点
  • leetcode 热题 100
  • Ae 效果:CC Lens
  • 【Redis】基础数据结构-quicklist
  • QT 实现服务器客户端搭建
  • Javascript - 轮播图
  • MATLAB中syms函数使用
  • 竞赛选题 深度学习 opencv python 实现中国交通标志识别_1
  • Qt 关于mouseTracking鼠标追踪和tabletTracking平板追踪的几点官方说明
  • 基于springboot的论坛网站
  • 分库分表理论总结
  • RK3568平台开发系列讲解(外设篇)AP3216C 三合一环境传感器驱动