LeetCode from inefficient to efficient, click

I. Title Description:

Topic request

Let’s say you’re a great parent and you want to give your kids some cookies. However, no more than one cookie can be given to each child. For each child I, there is an appetite value g[I], which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie J has a size S [J]. If s[j] >= g[I], we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number.

The sample

Input: g = [1,2,3], s = [1,1] Output: 1 Explanation: You have three children and two cookies. Even though you have two little cookies, since they're both size 1, you can only satisfy a child with an appetite of 1. So you should print 1.Copy the code

Ii. Analysis of Ideas:

In order to satisfy the appetite of the smallest child first, it is necessary to sort both arrays. When a biscuit cannot satisfy the appetite of the smallest child, the biscuit is invalid.

Iii. AC Code:

It’s easy to write the following violence simulation code along the lines above:

// 44 ms 17.1 MB
int findContentChildren_v1(vector<int> &g, vector<int> &s)
{
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    auto gi = g.begin(a);auto si = s.begin(a);int sum = 0;
    while(gi ! = g.end() && si ! = s.end())
    {
        cout << *gi << "" << *si << endl;
        if (*gi > *si)
        {
            // If the child's appetite is not satisfied, the cookie moves to the next one
            si++;
        }
        else
        {
            // Can satisfy the child's appetite, children, cookies move back, match number + 1gi++; si++; sum++; }}return sum;
}
Copy the code

However, there is room for optimization in the above code, which can reuse some variables and result in the following optimization

// 32 ms 17.1 MB
int findContentChildren(vector<int> &g, vector<int> &s)
{
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    auto gi = g.begin(a);auto si = s.begin(a);auto ge = g.end(a);auto se = s.end(a);int sum = 0;
    while(gi ! = ge && si ! = se) {if (*gi <= *si)
        {
            gi++;
            sum++;
        }
        si++;
    }
    return sum;
}

Copy the code

Iv. Summary:

Simple greedy algorithms can also improve efficiency by saving variables, optimizing the process, and paying attention to the reuse of parameters

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign