贪心算法学习 1
局部最优--全局最优
题目：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
这个题目很简单 就是我有这个 g是胃口 s是饼干 我先把最大的饼干拿出来 给胃口最大的看行不行 然后都减去 再重复 直到饼干没有了 或者是胃口没有了
不管是谁没了 我只需要知道有多少个小孩被满足了就行 如果饼干满足了这个小孩 小孩饼干都减一 满足小孩数+1 如果现在这个小孩找不到饼干去满足 那么直接删除这个小孩就行 不要破坏都是从最后一个往前走的这个顺序
代码如下：
class Solution(object):def findContentChildren(self, g, s):m=len(g)n=len(s)g=sorted(g)s=sorted(s)#首先将两个数组进行排序count=0while m>0 and n>0:if s[-1]>=g[-1]:del (g[-1])del (s[-1])#如果可以的话m-=1n-=1count+=1else:#那么就证明这个最后的那个孩子没办法被满足 直接删掉就行del g[-1]m-=1return count solution=Solution() result=solution.findContentChildren([1,2,3], [1,1]) print(result)solution=Solution() result=solution.findContentChildren([1,2,3],[6,2])
这个题目比较简单 但是我写的其实不好
然后我去看排名比较靠前的代码 我觉得非常好 就是也是从孩子入手 从后往前 如果这个饼干可以满足 那么count+1 饼干减1 如果没有满足 那么孩子继续往前找 满足的人数和饼干的位置都是不发生改变的 很巧妙的 太妙了 我要多久才能有这么妙的思想
我来写一下这个代码
class Solution(object):
def findContentChildren(self, g, s):
m=len(g)
n=len(s)
g=sorted(g)
s=sorted(s)#首先将两个数组进行排序
index=n-1
count=0
for i in range(m-1,-1,-1):
if index >= 0 and s[index]>=g[i]:
count+=1
index-=1
return count
solution=Solution()
result=solution.findContentChildren([1,2,3], [1,1])
print(result)
solution=Solution()
result=solution.findContentChildren([1,2,3],[6,2])
然后我发现还不是最好的 那我看看最好的是啥样的
class Solution(object):def findContentChildren(self, g, s):""":type g: List[int]:type s: List[int]:rtype: int"""g.sort()s.sort()i, j = 0, 0ng, ns = len(g), len(s)# 尽可能满足更多的孩子while i < ng and j < ns:if s[j] >= g[i]:i += 1j += 1else:j += 1return i
其实都差不多 大家看看就行 就是这个都差不多 主要就是按照小孩的来 满意饼干动 次数加 而小孩是会一直往前移动的
如果大家喜欢的话欢迎给我点赞