当前位置：首页 > article >正文

Leetcode算法基础篇-贪心算法

article 2024/11/15 9:00:40

简介

学习链接：贪心算法（第 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 = 0
        i, j = 0, 0
        while i < len(g) and j < len(s):
            cookie = s[j]
            child = g[i]
            if cookie >= child:
                ans += 1
                j += 1
                i += 1
            else: 
                j += 1


        return 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 = 0
        i, j = 0, 0
        while i < len(players) and j < len(trainers):
            player, trainer = players[i], trainers[j]
            if player <= trainer:
                ans += 1
                i += 1
                j += 1
            else:
                j += 1
        return 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 = 1
        for i in range(1, len(intervals)):
            interval = intervals[i]
            if interval[0] >= left:
                cnt += 1
                left = 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 = 1
        for i in range(1, n):
            if points[i][0] > left:
                cnt += 1
                left = points[i][1]
        
        return cnt