leetcode 贪心算法 455题 分发饼干

题目大意

给定两个数组，g[i] 为孩子饥饿程度。s[j]为饼干的大小，要求当饼干的大小 大于 孩子的饥饿度，求能满足最多数量的孩子。

解题思路

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的 并且 大小最小的饼干给这个孩子。

实现代码

具体的实现，我们需要将能满足饥饿孩子的 并且 大小最小的饼干给孩子，所以可以对饥饿度和饼干大小依次进行排序

c++ 实现

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // g[i] 能让孩子们满足胃口的饼干的最小尺寸
        // s[j] 代表每块饼干的尺寸
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int child = 0, cookies = 0;
        while(child < g.size() && cookies < s.size()){
            if(s[cookies] >= g[child])  ++child;
            ++cookies;
        }
        return child;
    }
};

python 实现

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 对两个序列进行排序
        g.sort()
        s.sort()
        pChild = 0
        pCookie = 0
        while pChild < len(g) and pCookie < len(s):
            if g[pChild] <= s[pCookie]: 
                pChild += 1
            pCookie +=1
       	return pChild

java 实现

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0, j = 0;
        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
            }
            j++;
        }
        return i;
    }
}

总结

1. 我完成的第一个贪心思想的算法，并且利用了c++, python，java 三种语言，来尽可能多的熟悉语言
2. 贪心算法：题目要求我们尽可能多的让孩子吃到饼干，所以说我们给每个孩子分配饼干的时候都尽可能的把最优解分配给孩子
3. 分配的最优解是：饼干大于孩子胃口，且把最小的大于孩子胃口的饼干分配给孩子
4. 贪心算法就是要求每一步解都是最优的