首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

分发饼干——贪心算法

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。...对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。...题解:如何将饼干喂孩子才能保证尽可能满足更多的孩子呢?...因为一块饼干(不能掰开)只能喂给一个小孩,饼干尺寸太小满足不了孩子的胃口,饼干尺寸过大又会造成浪费饼干 所以我们首先想到:应该先拿尺寸较小的饼干去喂胃口也相对较小的孩子,我们自然想到先将两数组按由小到大排序...,然后按个去试 如果当前尺寸饼干不能满足小孩,则拿出下一块稍大尺寸的饼干再喂给这个孩子,如果还是不能满足,依次拿cookies++,如果能满足,则能被满足孩子个数加1,直到后续无孩子或无饼干,也即遍历到孩子数组和饼干数组的末尾

36030
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    分发饼干(贪心)

    题目 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。...对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。...虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。...示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。...思路 现将孩子胃口数组和饼干尺寸排序,然后遍历孩子胃口,如果孩子胃口大于当前饼干尺寸饼干尺寸指针后移直到当前孩子胃口小于等于当前饼干尺寸 class Solution { public: int

    20420

    分发饼干

    分发饼干) https://leetcode-cn.com/problems/assign-cookies/ 题目描述 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。...但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 gi,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 sj 。...如果 sj >= gi,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。...虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。...示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。

    36600

    分发饼干

    1 题目描述 分发饼干 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。...对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。...假设在对前i 至 1个孩子分配饼干之后,可以满足第i个孩子的胃口的最小的饼干是第j块饼干,即sj是剩下的饼干中满足gi≤sj的最小值,最优解是将第j块饼干分配给第i个孩子。...如果j饼干分配给第i个孩子,当gi+1≤sj时,可以将第j块饼干分配给第i+1个孩子,分配的结果不会让更多的孩子被满足;当gi+1 > 8j时,第j块饼干无法分配给任何孩子,因此剩下的可用的饼干少了一块...当两个数组之—遍历结束时,说明所有的孩子都被分配到了饼干,或者所有的饼干都已经被分配或被尝试分配(可能有些饼干无法分配给任何孩子),此时被分配到饼干的孩子数量即为可以满足的最多数量。

    20840

    分发饼干(贪心)

    题目 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。...对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。...一个小朋友最多只能拥有一块饼干。 示例 1: 输入: [1,2,3], [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。...虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。...示例 2: 输入: [1,2], [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.

    30410

    C:图案打印

    { printf(" ");//这里留两个空格 } } printf("\n");//换行 } } return 0; } 图案展示...3、X形图案 3.1代码展示: #include int main() { int size = 0; // 初始化 scanf("%d", &size);//输入值...'*' } else { printf(" "); // 否则打印空格 } } printf("\n"); // 换行 } return 0; }  图案展示...: 3.2 代码解析: 1.先定义一个变量size来表示图案的大小; 2.使用两个嵌套的for循环,外层控制行数,内层控制列数; 3.你可以将图案看作在一张表格上,对于每个位置( i , j ),通过条件判断...4 使用控制语句 如 if-else 语句来区分不同的行或列的输出模式。 5 以行列的思想为基础 学会逐行逐列构造图形。 结语:  图形化编程题目对于帮助我们熟悉循环和控制结构的使用非常有帮助。

    9110

    455.分发饼干【分配问题】

    455.分发饼干【分配问题】 题目 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。...对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。...为了尽量使得剩下的饼干可以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。...令 cookie = 1来选中第一块饼干,也就是 尺寸 最小的饼干。...③ 此时 child = 2,cookie = 2 ,选中第二个孩子,第二块饼干。第二块饼干不满足第二个孩子,所以 ++cookie,饼干选择第三块饼干,孩子仍是第二个孩子。

    24210

    ​LeetCode刷题实战455:分发饼干

    假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。...对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。...虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。...示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。...解题 给定一个关于饼干的数组和一个关于胃口的数组,要求尽可能满足多的孩子,那么需要先对连个数组进行排序,尽可能让小饼干满足小胃口的,而不是那一块大饼干满足小胃口的,以此进行遍历计数 class Solution

    21020
    领券