饼干分发贪心算法的双重循环
时间: 2023-11-29 16:46:26 浏览: 37
以下是饼干分发贪心算法的双重循环的Python实现:
```python
def findContentChildren(g, s):
g.sort()
s.sort()
child = 0
cookie = 0
while child < len(g) and cookie < len(s):
if g[child] <= s[cookie]:
child += 1
cookie += 1
return child
```
该算法的思路是,先将孩子和饼干的胃口和大小进行排序,然后使用两个指针child和cookie分别指向孩子和饼干的第一个元素。如果当前孩子的胃口小于等于当前饼干的大小,则将child指针向后移动一位,否则将cookie指针向后移动一位。最终返回能够被满足的孩子数量。
相关问题
贪心算法分发饼干Java
以下是使用贪心算法分发饼干的Java代码:
```java
import java.util.Arrays;
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int j = g.length - 1;
for(int i = s.length - 1;i >= 0;i--){
while(j >= 0 && s[i] < g[j]){
j--;
}
if(j >= 0){
count++;
j--;
}
if(j < 0){
break;
}
}
return count;
}
}
```
该算法的核心思想是:每次将最小的饼干分配给胃口最小的孩子,这样可以使得更多的孩子得到满足。具体步骤如下:
1.将孩子和饼干按照大小排序,从大到小遍历饼干。
2.如果当前饼干可以满足当前孩子的胃口,就将该饼干分配给该孩子,并将计数器加1。
3.如果当前饼干不能满足当前孩子的胃口,就将该饼干留给下一个孩子。
4.重复步骤2和3,直到所有孩子都得到了满足或者所有饼干都被遍历完。
c++饼干贪心算法具体代码
下面是一个饼干贪心算法的具体代码实现,使用了Python语言:
def findContentChildren(g, s):
g.sort()
s.sort()
i = 0
for j in range(len(s)):
if i == len(g):
break
if s[j] >= g[i]:
i += 1
return i
g = [1,2,3]
s = [1,1]
print(findContentChildren(g, s)) # 输出1
g = [1,2]
s = [1,2,3]
print(findContentChildren(g, s)) # 输出2
g = [1,2,3]
s = [3]
print(findContentChildren(g, s)) # 输出1
在代码中,findContentChildren函数接收两个参数,一个是孩子的胃口列表g,另一个是饼干的大小列表s。函数首先对两个列表进行排序,然后使用i来记录已经满足的孩子数量,从第一个饼干开始遍历,如果饼干的大小大于等于当前孩子的胃口,则将i加1。如果饼干遍历完了,或者已经满足了所有孩子,就退出循环,返回已经满足的孩子数量i。最后,通过几个测试用例来验证代码的正确性。