This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
1. Title Description
Distribution of biscuits
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.
Example 1
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.
Example 2
Input: g = [1,2], s = [1,2,3] output: 2 explanation: you have two children and three cookies, each with an appetite value of 1,2. The number and size of cookies you have is enough to satisfy all children. So you should print 2.
Second, train of thought analysis
- Familiar with the author should understand before sharing a number of dynamic programming algorithm, if this problem is solved by dynamic programming, there is a pain point – two-dimensional
- What do I mean by two dimensions? The robot addressing that we did in dynamic programming was also two-dimensional. Why is that possible with dynamic programming?
- First of all, let’s review the walking diagram of the robot. Our current state (I, J) is related to the above two states and this relationship can be described by the equation
- But putting the same layout into a cookie is a little tricky. First of all, our current state (I,j) does not necessarily come from resources (I -1,j) or (I,j-1).
- Let’s think of it this way: when child G is fixed, s cookies may be distributed among m children (m
- So dynamic programming is a little bit of a stretch in dividing cookies. So greedy algorithms are good for this. The essence of greedy algorithm is local optimization to solve the problem
- Greedy algorithm is different from dynamic programming in that the former realizes problem solving through forward propulsion. In dynamic programming, the current state is determined by the previous state. The greedy algorithm doesn’t care about the previous state. Only consider your current state. The bottom line is that greedy algorithms only guarantee that their current problem can be solved without someone else
Greedy analysis
- Now that we have a greedy algorithm, we have to determine the greedy strategy in the same way that we have to determine the transition equation. First, we need to rank the kids and the cookies in order of appetite.
- Because we need to know how many children can be satisfied, we have expanded to include children as subjects.
- G [I] is the minimum number of cookies we need to find in S that are greater than the current child’s appetite. Why do we need a minimum?
- In the figure above, we assign the smallest cookie that satisfies the condition to the current child, and then the next cookie that satisfies the condition can be assigned to the next child
- But if we don’t distribute the smallest cookie that meets the criteria, the worst that can happen is that the first cookie doesn’t meet the next kid
AC code
).
- Based on the above analysis we can present the following code. So what I’m going to do is I’m going to assign the minimum satisfaction of the cookie to the current kid so that I can satisfy as many kids as possible
- There are some boundary cases in there that we need to evaluate, because it’s a child loop that doesn’t cause an array to go out of bounds. However, cookie arrays can be out of bounds, and the following if determination is to prevent the array from being out of bounds
public int findContentChildren(int[] g, int[] s) {
if (s.length == 0) {
return 0;
}
Arrays.sort(g);
Arrays.sort(s);
int sIndex = 0;
int total = 0;
for (int i = 0; i < g.length; i++) {
if (sIndex >= s.length) {
return total;
}
while (g[i] > s[sIndex]) {
sIndex++;
if (sIndex >= s.length) {
return total;
}
}
sIndex++;
total++;
}
return total;
}
Copy the code- The result was not very satisfactory
Upgrade 1
- The execution speed and memory consumption are not ideal. In fact, we can avoid overstepping the bounds of the above array and thus reduce the amount of execution memory that we think should be improved.
- Let’s see, for g(I) it has the following relation to s(j) of the biscuit
i>=j. So let’s look at the code after we optimize
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int total = 0;
for (int i = 0; i < g.length; i++) {
for (int j = i; j < s.length; j++) {
if (s[j] >= g[i]) {
// In order to be compared next time by other children, this is set to -1, so that no child will be assigned to it
s[j] = -1;
total++;
break; }}}return total;
}
Copy the code
Upgrade 2
- My guess is that the code execution speed in Upgrade 1 is not optimized because
s[j]=-1This piece. I’m going to set it to -1 but I’m still going to do one alignment in the loop but it’s not going to pass. This results in the same number of comparisons so the execution speed remains the same - So we can define an index of cookies. So that we don’t have to have the cookies that we’re comparing at different levels to be counted more than once.
public int findContentChildren(int[] g, int[] s) {
if (s.length == 0) {
return 0;
}
Arrays.sort(g);
Arrays.sort(s);
int total = 0;
int startPos = 0;
for (int i = 0; i < g.length; i++) {
for (int j = startPos; j < s.length; j++) {
if (s[j] >= g[i]) {
total++;
startPos=j+1;
break; }}}return total;
}
Copy the code
Four,
- Greedy algorithms solve problems locally. His scenes have no postponement. That is, there is no need to consider the state before and after. Be single-minded and just do it yourself.
Like, follow you the most beautiful