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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode题解-贪心算法 - MaggicQ的博客，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1778字，纯文字阅读大概需要3分钟。

内容图文

本文目录

• 定义
• 常见题型
  • 买卖股票的最佳时机
  • 买卖股票的最佳时机 II
  • 跳跃游戏
  • 最大子序和
  • 判断子序列

定义

贪心算法（英语：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 大专栏 ?Leetcode题解-贪心算法 - MaggicQ的博客:
    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:])

---

---

内容总结

以上是互联网集市为您收集整理的Leetcode题解-贪心算法 - MaggicQ的博客全部内容，希望文章能够帮你解决Leetcode题解-贪心算法 - MaggicQ的博客所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---