Google 面试题 | 分饼干

输入:  [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。

2. 实现

将g与s都从小到大排列，再用两根指针i,j，如果g(i)

那么这样的贪心算法是正确的吗？是的。下面给出简单的分析。首先仍然假设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: 

还在浪费时间学贪心算法么？告诉你三个不需要学习贪心法的理由！

http://www.lintcode.com/en/problem/majority-number/

http://www.lintcode.com/en/problem/create-maximum-number/
http://www.lintcode.com/en/problem/jump-game-ii/
http://www.lintcode.com/en/problem/jump-game/
http://www.lintcode.com/en/problem/gas-station/
http://www.lintcode.com/en/problem/delete-digits/
http://www.lintcode.com/en/problem/linked-list-cycle-ii/
http://www.lintcode.com/en/problem/linked-list-cycle/

九章官网参考代码链接：

http://www.jiuzhang.com/solutions/majority-number/
http://www.jiuzhang.com/solutions/create-maximum-number/
http://www.jiuzhang.com/solutions/jump-game-ii/
http://www.jiuzhang.com/solutions/jump-game/
http://www.jiuzhang.com/solutions/gas-station/
http://www.jiuzhang.com/solutions/delete-digits/
http://www.jiuzhang.com/solutions/linked-list-cycle-ii/
http://www.jiuzhang.com/solutions/linked-list-cycle-i/

• 回复“简历”，查看简历撰写指南，获取“简历模板”

• 回复“冷冻期”，查看北美各大IT企业冷冻期信息和注意事项

• 回复“Career”, 查看Caireer Fair 攻略 check list

• 回复“薪资”，查看北美各大IT企业New Grades Engineer 薪资水平；

• 回复“项目”，查看7-14天可以搞定的小项目推荐

• 回复“评分”，查看系统设计评分指南

• 回复“behavior”，查看behavior interview指南

• 回复“晋升”，查看Engineer晋升机制