此博客为《代码随想录》二叉树章节的学习笔记，主要内容为算法>贪心算法基础的相关题目解析。
文章目录
- 455.分发饼干
- 1005.K次取反后最大化的数组和
- 860.柠檬水找零
455.分发饼干
题目链接
python">class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()i = 0for x in s:if i < len(g) and g[i] <= x:i += 1return i
- 饼干和胃口数组都从小到大排序，最小的饼干应该给当前满足的胃口最小的孩子，如果不给则会浪费分发机会，无法取得最优解
- 指针
i标识当前满足到第i个孩子；完整遍历饼干列表，按照孩子胃口从小到达依次尝试去满足，最后直接返回i即为已经满足的孩子数量
1005.K次取反后最大化的数组和
题目链接
python">class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort()min_num, res = +inf, 0for num in nums:min_num = min(min_num, abs(num))if num < 0 and k > 0:res -= numk -= 1else:res += numif k and k % 2 != 0:return res - 2 * min_numelse:return res
- 首先把负数从小到大仅可能反转为正数，如果反转所有负数后
k > 0，则后序反转只针对最小的元素 - 在遍历过程中反转负数同时记录最小元素，如果遍历结束后
k > 0且k为奇数，则把最小的元素反转，反之则直接返回答案
860.柠檬水找零
题目链接
python">class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five = ten = 0for b in bills:if b == 5:five += 1elif b == 10:five -= 1ten += 1else:if ten:ten -= 1five -= 1else:five -= 3if five < 0:return Falsereturn True
- 分类讨论，贪心准则为优先使用十元找零，之后再使用五元
