贪心算法采用贪心的策略,保证每步都是局部最优,最终达到全局最优
分配问题 455.Assign Cookies (Easy)
题目描述 有一群孩子和一堆饼干,每个孩子都有一个饥饿度,每个饼干都有一个大小,每个孩子只能吃最多一个饼干,且只有饼干的大小大于孩子的饥饿度时,这个孩子才能吃饱。求解最多有多少孩子可以吃饱。
输入输出样例 输入两个数组,分别代表孩子们的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。
1 2 Input: [1, 2], [1, 2, 3] Output: 2
c++:
1 2 3 4 5 6 7 8 9 10 int findContentChildren (vector<int >& children, vector<int >& cookies) { sort (children.begin (), children.end ()); sort (cookies.begin (), cookies.end ()); int child = 0 , cookie = 0 ; while (child < children.size () && cookie < cookies.size ()) { if (children[child] <= cookies[cookie]) ++child; ++cookie; } return child; }
java:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int findContentChildren (int [] g, int [] s) { int max = 0 ; Arrays.sort(g); Arrays.sort(s); for (int i = 0 , j = 0 ; i < s.length & j < g.length; i++) { if (g[j] <= s[i]) { max++; j++; } } return max; } }