problem
solution1:
But, you should give each child at most one cookie.
对小朋友的满意程度(也就是胃口)和当前cookies的大小分别进行排序,满足一个小朋友则加1;否则比较下一个cookie是否满足小朋友。记住前提是每个小朋友最多只能得到一个cookie.也就是贪婪算法。
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int res = ;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
for(int i=, j=; i<g.size() && j<s.size();)//err.
{
if(g[i]<=s[j]) { res++; j++; i++; }
else j++;
}
return res;
}
};
solution2:简化版本,即满足小朋友的个数即是所求解的,小朋友的坐标即是满足小朋友的个数。
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = ;
for(int j=; i<g.size() && j<s.size(); j++)//err.
{
if(g[i]<=s[j]) i++;
}
return i;
}
};
参考
1. Leetcode_455. Assign Cookies;
完