Leetcode题解-贪心算法 - MaggicQ的博客

本文目录

定义
常见题型

定义

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

常见题型

买卖股票的最佳时机

买卖股票的最佳时机-题目描述

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res, in_price = 0, float('inf')
        for price in prices:
            in_price = min(in_price, price)
            res = max(res, price-in_price)
        return res

买卖股票的最佳时机 II

买卖股票的最佳时机 II-题目描述

（可以参与多次交易）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(len(prices)-1):
            res += max(0, prices[i+1]-prices[i])
        return res

跳跃游戏

跳跃游戏-题目描述

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_ind = 0
        for i, n in enumerate(nums):
            if i > max_ind:  # 超出当前所能到达的最远索引
                return False
            # max_ind每一步都会更新
            # 表示当前所能到达的最远的索引
            max_ind = max(max_ind, i+n)

        # 成功完成遍历，说明从第一个位置出发能到达最后一个位置
        return True

最大子序和

最大子序和-题目描述

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

判断子序列

判断子序列-题目描述

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s:
            return True
        pos = t.find(s[0])
        if pos == -1:
            return False
        else:
            return self.isSubsequence(s[1:], t[pos+1:])

定义