前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【LeetCode】贪心算法--买卖股票的最佳时机 II(122)

【LeetCode】贪心算法--买卖股票的最佳时机 II(122)

作者头像
PM小王
发布2019-07-01 11:46:05
7730
发布2019-07-01 11:46:05
举报
文章被收录于专栏:程序员小王

一、写在前面

为什么要在LeetCode刷题?大家都知道不管是校招还是社招算法题是必考题,而这一部分恰巧是大多数人的短板,所以刷题首先是为了提高自身的编程能力,能够在算法面试中脱颖而出,拿到满意的offer。自己是打算考研的,计算机考研数据结构也是必考题,所以刷题的第二个原因就是为了巩固自己的数据结构知识。

应该如何刷题呢?这两个月自己是顺序刷题的,但是总结的时候发现知识点太零散,前二十题有栈,链表,数组等等,自己总结的时候没有形成一个完整的体系,也没有清晰的分类,这不是自己想要的,所以自己后期刷题将采用专题的方式,比如数组,链表,二叉树等等。

那么第一个专题就是贪心算法。前20题链接【LeetCode】汇总贴(NO.1-20)

自己建了一个LeetCode刷题群,交流自己的刷题心得,现在还没有到达预定的人数,感兴趣的小伙伴可以参加哦。

为面试而生,期待你的加入。

二、什么是贪心算法

贪心算法在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 时,再买入卖出的话,那就是傻了,亏钱。

以此方式类推下去,即得最大利润。

五、代码实现

代码语言:javascript
复制
 1class Solution:
 2    def maxProfit(self, prices):
 3        """
 4        :type prices: List[int]
 5        :rtype: int
 6        """
 7        profit = 0
 8        temp=0
 9        for i in range(1,len(prices)):
10            temp=prices[i] - prices[i-1]
11            if temp>0:
12                profit+=temp
13        return profit

【推荐阅读】

【Python爬虫】初识爬虫(1)

用Python来一场人工造雪

机器学习实战--住房月租金预测(1)

Python之禅

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-12-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员小王 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 二、什么是贪心算法
  • 三、今日题目
  • 四、题目分析
  • 五、代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档