简介
学习链接：贪心算法（第 10 ~ 12 天）
贪心算法（Greedy Algorithm）：一种在每次决策时，总是采取在当前状态下的最好选择，从而希望导致结果是最好或最优的算法。
贪心问题的两个特征：
- 贪心选择：问题的全局最优解可以通过一系列的局部最优解来得到
- 最优子结构：问题的最优解包含其子问题的最优解
解题三步走：
- 转换问题：将原问题转换为贪心选择问题，先做出选择，再解决剩下的一个子问题
- 贪心选择策略：制定贪心策略，选取当前状态下最优解，得到局部最优解
- 最优子结构：根据贪心策略，将贪心选择局部最优解与子问题最优解合并得到全局最优解
练习题
455. 分发饼干
思路
- 贪心策略：我们将小孩和饼干都按照从小到大的顺序排序，然后枚举每一块饼干，如果符合就给，不符合就下一块
- 代码实现。
代码
class Solution(object):def findContentChildren(self, g, s):""":type g: List[int]:type s: List[int]:rtype: int"""g, s = sorted(g), sorted(s)ans = 0i, j = 0, 0while i < len(g) and j < len(s):cookie = s[j]child = g[i]if cookie >= child:ans += 1j += 1i += 1else: j += 1return ans
2410. 运动员和训练师的最大匹配数
思路
- 和上一题一模一样
代码
class Solution(object):def matchPlayersAndTrainers(self, players, trainers):""":type players: List[int]:type trainers: List[int]:rtype: int"""players = sorted(players)trainers = sorted(trainers)ans = 0i, j = 0, 0while i < len(players) and j < len(trainers):player, trainer = players[i], trainers[j]if player <= trainer:ans += 1i += 1j += 1else:j += 1return ans
435. 无重叠区间
思路
- 贪心策略：我们将所有的区间按照右端点排序，这样可以确定最先结束的区间，从而能够给后续区间留下足够多的空间，使得区间数最多，记录一个当前右端点的位置
left和重叠区间数cnt - 遍历所有区间，每次比较区间的左端点和当前右端点
left，如果重叠，则记录一次，并更新left - 最后所有区间数减去重叠区间数即为答案。
代码
class Solution(object):def eraseOverlapIntervals(self, intervals):""":type intervals: List[List[int]]:rtype: int"""intervals.sort(key=lambda x: x[1])left = intervals[0][1]cnt = 1for i in range(1, len(intervals)):interval = intervals[i]if interval[0] >= left:cnt += 1left = interval[1]return len(intervals) - cnt
452. 用最少数量的箭引爆气球
思路
- 和上题考点相同，直接统计重叠区间数即可。
代码
class Solution(object):def findMinArrowShots(self, points):""":type points: List[List[int]]:rtype: int"""points.sort(key=lambda x: x[1])n = len(points)left = points[0][1]cnt = 1for i in range(1, n):if points[i][0] > left:cnt += 1left = points[i][1]return cnt
