美文网首页
LeetCode 455. Assign Cookies

LeetCode 455. Assign Cookies

作者: njim3 | 来源:发表于2019-02-23 17:49 被阅读1次

题目

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: 1
Explanation: 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: 2
Explanation: 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.

解析

题目中要求更多的分配cookies,即“贪心”。实现的思路比较简单,根据题目中的逻辑进行实现即可,即从左至右遍历s,如果比g大,即满足该child。

实现(C语言)

int comp(const void* a, const void* b) {
    return *(int*)a > *(int*)b;
}

int findContentChildren(int* g, int gSize, int* s, int sSize) {
    qsort(g, gSize, sizeof(int), comp);
    qsort(s, sSize, sizeof(int), comp);
    
    int count = 0, j = 0;
    
    for (int i = 0; i < sSize; ++i) {
        if (s[i] >= g[j]) {
            ++count;
            ++j;
            
            if (j >= gSize)
                break;
        }
    }
    
    return count;
}

实现中使用到了qsort库函数,即将数组进行从大到小排序,先从大到小进行满足,可以更多的满足child,这个是显然的。

相关文章

网友评论

      本文标题:LeetCode 455. Assign Cookies

      本文链接:https://www.haomeiwen.com/subject/robpyqtx.html