MENU

LeetCode455. Assign Cookies(贪心)

2019 年 04 月 11 日 • 阅读: 1011 • LeetCode阅读设置

LeetCode455. Assign Cookies(贪心)

  • Easy
  • Accepted:60,685
  • Submissions:125,878

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.

链接

https://leetcode.com/problems/assign-cookies

题意

假设你现在要给你的孩子们分一些饼干,每个孩子最多分一个。每个孩子都有一个贪婪指数gi,每块饼干有一个尺寸si,当si大于等于gi时,就可以把饼干分给孩子,孩子就会变得开心,问如何分配饼干让最多的孩子开心,输出最多孩子开心的数量。

题解

此时,一个表情包在我脑海中浮现,“懂不懂,这道题用贪心”。

我们要使得尽可能多的孩子开心,就是尽可能分配更多的饼干。考虑一个贪心策略:每次尽可能的先分配最大尺寸的饼干给贪婪指数最大的孩子,这样我们就可以获得一个最优解。

为了更好处理,我们可以对孩子的贪婪指数和饼干的尺寸从大到小排序,然后使用一个while循环。

因为要排序,所以时间复杂度为$O(nlogn)$,一个比较“暴力”的写法是两重循环。

代码

  • Runtime: 44 ms, faster than 74.03% of C++ online submissions for Assign Cookies.
  • Memory Usage: 10.4 MB, less than 76.00% of C++ online submissions for Assign Cookies.
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int n = g.size(), m = s.size();
        sort(g.begin(), g.end(), greater <>()); // 从大到小排序
        sort(s.begin(), s.end(), greater <>());
        int ans = 0;
        int i = 0, j = 0;
        while (i < n && j < m)
        {
            if (s[j] >= g[i])
            {
                ++i, ++j;
                ++ans;
            }
            else
                ++i;
        }
        return ans;
    }
};
  • Runtime: 876 ms, faster than 5.04% of C++ online submissions for Assign Cookies.
  • Memory Usage: 10.1 MB, less than 100.00% of C++ online submissions for Assign Cookies.
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int n = g.size(), m = s.size();
        vector<bool>vis(m + 1, false);
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int ans = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = m - 1; j >= 0; --j)
            {
                if (!vis[j] && s[j] >= g[i])
                {
                    ++ans;
                    vis[j] = true;
                    break;
                }
            }
        }
        return ans;
    }
};

The end.
2019年4月11日 星期四