问答

当前位置

Google面试题 | 分饼干

  • Ta: 刘助教

题目描述

假设你有一群孩子和一些饼干,每一块饼干j大小为s(j),同时每一个孩子i,被分到的饼干大小至少为g(i),即s(j)>=g(i)时,这个孩子才会满足,g(i)成为孩子i的满足度。你的目标是将饼干分配给孩子,使得到满足的孩子尽可能多。保证每个g(i)为正且不能将多块饼干分给一个孩子或将一块饼干分给多个孩子。

输出样例

样例1:

输入: [1,2,3], [1,1]
输出: 1
说明: 三个孩子的满足度分别为1,2,3,两块饼干的大小均为1。饼干的大小为1,只能满足第一个孩子,所以输出1。

样例2:

输入: [1,2], [1,2,3]
输出: 2
说明: 两个孩子的满足度分别为1,2,三块饼干的大小分别为1,2,3。这三块饼干的大小足以满足这两个孩子,所以输出2。

解题思路分析

  1. 分析
    直觉上,要使满足的孩子尽可能多,分配给每个孩子的饼干应该尽可能小。如果把大的饼干分配给满足度较小的孩子,显然会造成浪费。这样,我们可以按g(i)从小到大给孩子分配饼干,同时,为了不浪费饼干,对于要分配给某个孩子的饼干,也从剩下的饼干中找到最小的能满足这个孩子的饼干。按g(i)从小到大分配饼干的好处是,当把s(j)分配给g(i)之后,对于下一个孩子g(i+1),我们就不用考虑s(j)之前的饼干了,只需考虑s(j)之后的饼干(这里假设g(i),s(i)为从小到大排列)。因为,如果s(j)之前还有可以满足g(i+1)的饼干,那这块饼干也必然可以满足g(i),那s(j)就不是剩余饼干中可以满足g(i)的最小的饼干了。

  2. 实现
    将g与s都从小到大排列,再用两根指针i,j,如果g(i)<=s(j),则将s(j)分配给g(i),再看下一个孩子与下一块饼干,i与j均自增;否则,应依次增大j去寻找能满足g(i)的s(j)。这种方法叫做two pointer。设孩子数与饼干数的较大值为n,则排序的时间复杂度为O(nlog(n)),两根指针的时间的复杂度为O(n),总的时间复杂度为O(nlog(n))。

  3. 证明
    那么这样的贪心算法是正确的吗?是的。下面给出简单的分析。首先仍然假设g(i)已从小到大排序,所以g(0)为最小值。对于一个最优的方案(即能满足最多孩子的方案),假设这个方案里能满足的孩子中满足度最小的是g(i),而将s(j)分配给了g(i),那么有s(j)>=g(i)>=g(0),故我们可以把g(i)换成g(0)而得到另一个最优方案。把g(0)与s(j)从原问题中去掉,则得到了一个比原问题规模略小但形式相同的新问题。对于新问题的分析与原问题相同。这样,我们就可以把原最优方案中的孩子依次替换成g(0),g(1),……,g(ans-1),ans为最优方案满足的孩子个数。因此,我们总可以去先满足满足度最小的孩子来获得最优方案。

  4. 实现
    只要每次给出的饼干是能满足当前的孩子的最小的饼干,以什么样的顺序给孩子分配饼干其实是无所谓的(如果不存在能满足当前孩子的饼干,则跳过这个孩子),最终的答案都是一样的。具体分析比较繁琐,这里不再给出,感兴趣的读者可以试着从以下角度分析:对于一种孩子分配顺序,如果交换某对相邻两个孩子的顺序,会对最终结果造成怎样的影响。

  5. Follow up
    如果可以把多块饼干分给一个孩子,怎么做?

参考程序

面试官角度分析

此题的最优算法是贪心算法。如果能想到贪心算法并给出算法框架,就可以达到hire的程度。对于贪心算法的学习,可以参考的意见 如下 link:
还在浪费时间学贪心算法么?告诉你三个不需要学习贪心法的理由!

LintCode相关问题

Majority Number
Create Maximum Number
Jump Game-ii
Jump Game
Gas Station
Delete Digits
Linked List Cycle-ii
Linked List Cycle

九章官网参考代码链接:

Majority Number 参考代码
Create Maximum Number 参考代码
Jump Game-ii 参考代码
Jump Game 参考代码
Gas Station 参考代码
Delete Digits 参考代码
Linked List Cycle-ii 参考代码
Linked List Cycle 参考代码

0 个回复

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1