LeetCode 455. Assign Cookies

本文主要是介绍LeetCode 455. Assign Cookies，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

455. Assign Cookies

一、问题描述

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

二、输入输出

Example 1:

Input: [1,2,3], [1,1]Output: 1Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]Output: 2Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

三、解题思路

不得不说，贪心算法比DP好理解多了。刷DP快刷成s b了^(*￣(oo)￣)^

贪心算法

先把g 和 s全部从小到大来排序。然后依次遍历g里面的元素，对于下标i 需要的饼干至少是g[i] 那么再从s中去找，如果有size >= g[i]的计数器就加一。i++ 然后继续遍历注意是继续遍历s 因为s和g都是有序的，所以遍历s的时候是在上一次的基础上继续遍历的，如果s到了末尾那么直接break，说明现在没有满足条件的饼干。否则的话，count++ j++ j++是因为饼干只能给一个人，给过之后就没有了。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int count = 0, j = 0;for (int i = 0, n = g.size(); i < n; ++i) {int need = g[i];for (; j < s.size() && s[j] < need; ++j) ;if(j == s.size()) break;count++;j++;}return count;}
};