做个一般的网站要多少钱,企业网页制作推广,网站服务器被黑怎么办,网站建设四川题目#xff1a;455. 分发饼干
难度#xff1a;简单
假设你是一位很棒的家长#xff0c;想要给你的孩子们一些小饼干。但是#xff0c;每个孩子最多只能给一块饼干。
对每个孩子 i#xff0c;都有一个胃口值 g[i]#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸455. 分发饼干
难度简单
假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是满足尽可能多的孩子并输出这个最大数值。
示例 1:
输入: g [1,2,3], s [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干3 个孩子的胃口值分别是1,2,3。
虽然你有两块小饼干由于他们的尺寸都是 1你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。示例 2:
输入: g [1,2], s [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。提示
1 g.length 3 * 1040 s.length 3 * 1041 g[i], s[j] 231 - 1
一、模式识别
1.贪心算法
局部最优解找到满足胃口最小大的孩子的最小大饼干
从局部到全局每满足一个孩子继续用剩余的饼干满足剩余的孩子
反例想不到。。。
2.双指针
根据题干条件想到双指针并不难其实我一开始是用双指针的思路做的
题目条件两个数组 逐个数字比大小s[j] g[i] - 解法双指针
官方解法中的解释是排序 双指针 贪心
为了尽可能满足最多数量的孩子从贪心的角度考虑应该按照孩子的胃口从小到大的顺序依次满足每个孩子且对于每个孩子应该选择可以满足这个孩子的胃口且尺寸最小的饼干。
还给出了证明但我觉得思路上理解起来并不难所以证明过程不用细看
二.代码实现
1.双指针 从小胃口孩子开始喂最简洁实现
步骤1.排序 2.双指针 3.循环数字比大小
写法有while循环写法和for循环写法推荐while循环写法可读性较强
可以理解为for循环写法衍生于while循环写法
while循环写法
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:if not s:return 0m, n len(g), len(s)g.sort()s.sort()i, j 0, 0while i n and j m:if s[i] g[j]:j 1i 1return j
for循环写法
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:if not s:return 0m, n len(g), len(s)s.sort()g.sort()j 0for i in range(n):if j m and s[i] g[j]:j 1return j
时间复杂度O(nlogn)空间复杂度O(1)
2.双指针 从大胃口孩子开始喂 步骤1.排序 2.双指针 3.循环数字比大小
不同于从小胃口孩子喂除了倒序访问的区别外
从大胃口孩子开始喂不能直接返回索引因此多了一个变量ans
和从小胃口一样写法有while循环写法和for循环写法推荐while循环写法可读性较强
可以理解为for循环写法衍生于while循环写法
while循环写法
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:if not s:return 0g.sort()s.sort()m, n len(g), len(s)i, j n - 1, m - 1ans 0while i 0 and j 0:if s[i] g[j]:i - 1ans 1j - 1return ans
for循环写法
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:if not s:return 0g.sort()s.sort()m, n len(g), len(s)i n - 1ans 0for j in range(m - 1, -1, -1):if i 0 and s[i] g[j]:i - 1ans 1return ans
时间复杂度O(nlogn)空间复杂度O(1)
3.可以用栈/队列代替双指针
实现的逻辑相同就是用栈/队列的抛出操作代替了移动指针操作但队列比指针操作耗时略大
从小胃口孩子开始喂栈
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:if not s:return 0ans 0g.sort()s.sort()while g and s:ch_g g.pop()if s[-1] ch_g:s.pop()ans 1return ans
从大胃口孩子开始喂队列
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:if not s:return 0ans 0g.sort()s.sort()gdeque deque(g)sdeque deque(s)while gdeque and sdeque:ch_s sdeque.popleft()if ch_s gdeque[0]:gdeque.popleft()ans 1return ans
时间复杂度O(nlogn)空间复杂度O(n)
三、为什么两种实现方式遍历的数组不同
模式识别目的是快速找到一个解法
但为了满足自己好奇心以及加快以后的模式识别我想探究一下这个问题
配对条件是饼干大小s[j] 胃口g[i]即饼干大于胃口
从小到大配对时需要遍历要求较大者饼干保证所有大饼干配对
即从小到大遍历要求较大者饼干防止小饼干无法配对导致错过大饼干
如果遍历胃口面临饼干组左端尺寸过小的饼干时无法继续找更大的饼干
从大到小配对时需要遍历要求较小者胃口保证所有小胃口配对
即从大到小遍历要求较小者胃口防止大胃口无法配对导致错过小胃口
如果遍历饼干面临胃口组右端胃口过大的孩子时无法继续找更小的胃口
