455 - 分发饼干(assign-cookies)

Create by jsliang on 2019-07-30 11:12:02
Recently revised in 2019-07-30 11:49:34

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 知识点
七 解题思路
八 进一步思考

二 前言

返回目录

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

注意:

你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。

示例 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.

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码
var findContentChildren = function(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);

  let result  = 0;

  let i = 0;
  let j = 0;

  while (i < g.length && j < s.length) {
    if (g[i] <= s[j]) {
      // 可以满足胃口,喂食
      result += 1;
      i += 1;
      j += 1;
    } else {
      // 不满足胃口,查看下一块小饼干
      j += 1;
    }
  }

  return result;
};

四 执行测试

返回目录

  1. s[1,2,3]
  2. g[1,1]
  3. return
1

五 LeetCode Submit

返回目录

✔ Accepted
  ✔ 21/21 cases passed (148 ms)
  ✔ Your runtime beats 71.6 % of javascript submissions
  ✔ Your memory usage beats 21.05 % of javascript submissions (37.9 MB)

六 知识点

返回目录

  1. sort():排序,保持返回数组的数字为顺序排列。sort() 详细介绍

七 解题思路

返回目录

首先,理解题意:

  1. 一个饼干对应一个小朋友
  2. 饼干不能拆分成更多小饼干
  3. 找到最好的解决方案

然后,我们思考下:

  1. sg 进行排序,这样方便我们挪动指针位置,探测到饼干去向。
  2. 初始化两个指针 ij,分别指向 sg
  3. 对比 s[i]g[j]

如果 s[i] < g[j],说明这块饼干能满足小朋友的胃口,那么我们就将 ij 往前移动 1,并且小朋友的数量 result 加一。

如果 s[i] > g[j],说明这块饼干不能满足小朋友的胃口,并且这块饼干废了,我们将 j 往前移动 1 即可。

var findContentChildren = function(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);

  let result  = 0;

  let i = 0;
  let j = 0;

  while (i < g.length && j < s.length) {
    if (g[i] <= s[j]) {
      // 可以满足胃口,喂食
      result += 1;
      i += 1;
      j += 1;
    } else {
      // 不满足胃口,查看下一块小饼干
      j += 1;
    }
  }

  return result;
};

提交尝试下:

✔ Accepted
  ✔ 21/21 cases passed (148 ms)
  ✔ Your runtime beats 71.6 % of javascript submissions
  ✔ Your memory usage beats 21.05 % of javascript submissions (37.9 MB)

这样,我们就通过贪心算法完成了这道题的破解~

八 进一步思考

返回目录

简单难度的分发饼干就此结束了。

那么问题来了:

  1. 如果饼干能拆分成小饼干。
  2. 如果可以多块饼干满足一个小朋友的胃口。

是不是会有不一样的求解。


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-30 11:49:35

results matching ""

    No results matching ""