摘要：贪心算法每一步必须满足一下条件可行的即它必须满足问题的约束。四题目分析贪心算法，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，也就是说，只关心当前最优解，按照贪心策略，不关心以后，我们只关心当前利益。
一、写在前面
为什么要在LeetCode刷题？大家都知道不管是校招还是社招算法题是必考题，而这一部分恰巧是大多数人的短板，所以刷题首先是为了提高自身的编程能力，能够在算法面试中脱颖而出，拿到满意的offer。自己是打算考研的，计算机考研数据结构也是必考题，所以刷题的第二个原因就是为了巩固自己的数据结构知识。
应该如何刷题呢？这两个月自己是顺序刷题的，但是总结的时候发现知识点太零散，前二十题有栈，链表，数组等等，自己总结的时候没有形成一个完整的体系，也没有清晰的分类，这不是自己想要的，所以自己后期刷题将采用专题的方式，比如数组，链表，二叉树等等。
那么第一个专题就是贪心算法。前20题链接【LeetCode】汇总贴（NO.1-20）
自己建了一个LeetCode刷题群，交流自己的刷题心得，现在还没有到达预定的人数，感兴趣的小伙伴可以参加哦，个人微信：wxb950917。
为面试而生，期待你的加入。
二、什么是贪心算法
贪心算法在LeetCode共有41个题目，以中等难度居多。那么什么是贪心算法呢？
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法每一步必须满足一下条件：
1、可行的：即它必须满足问题的约束。
2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。
学习贪心算法的时候可以结合动态规划一起来学习，两者还是很相似的。
三、今日题目
买卖股票的最佳时机 II（122）
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
四、题目分析
贪心算法，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，也就是说，只关心当前最优解，按照贪心策略，不关心以后，我们只关心当前利益。第0天买入，花费prices[0]，第一天卖出，得到prices[1]，那么我们的收获就是profit = prices[1] - prices[0],那么有两种情况
（1）当profit > 0 时，赶紧买入卖出，能赚一笔是一笔。
（2）当profit <= 0 时，再买入卖出的话，那就是傻了，亏钱。
以此方式类推下去，即得最大利润。
五、代码实现
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
profit = 0
temp=0
for i in range(1,len(prices)):
temp=prices[i] - prices[i-1]
if temp>0:
profit+=temp
return profit
【推荐阅读】
【Python爬虫】初识爬虫（1）
用Python来一场人工造雪
机器学习实战--住房月租金预测（1）
Python之禅
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/45039.html
摘要：动态规划问题一定会具备最优子结构，才能通过子问题的最值得到原问题的最值。另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的状态转移方程才能正确地穷举。 大厂算法面试之leetcode精讲3.动态规划视频教程（高效学习）:点击学习目录：1.开篇介...
摘要：题目描述给定一个数组，它的第个元素是一支给定股票第天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。随后，在第天股票价格的时候买入，在第天股票价格的时候卖出这笔交易所能获得利润。 题目描述 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票...
摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...
摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。 一 目录 不折腾的前端，和咸鱼有什么区别...
摘要：本文只是简单理解算法，并不会深入的讨论。大部分来自数组部分。如果数组中每个元素都不相同，则返回。示例输入输出加给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。尽量减少操作次数。 算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰...
阅读 1008·2021-10-11 10:59
阅读 1833·2021-09-29 09:44
阅读 767·2021-09-01 10:32
阅读 1312·2019-08-30 14:21
阅读 1740·2019-08-29 15:39
阅读 2817·2019-08-29 13:45
阅读 3435·2019-08-29 13:27
阅读 1889·2019-08-29 12:27
