代码训练LeetCode(15)买卖股票

这篇具有很好参考价值的文章主要介绍了代码训练LeetCode(15)买卖股票。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

代码训练(15)LeetCode之买卖股票

Author: Once Day Date: 2024年4月22日

漫漫长路,才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

  • 122. 买卖股票的最佳时机 II - 力扣(LeetCode)
  • 力扣 (LeetCode) 全球极客挚爱的技术成长平台
1. 原题

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候最多只能持有 一股 股票。你也可以先购买,然后在同一天出售。

返回你能获得的最大利润 。

例如对于prices = [7,1,5,3,6,4],最大利润为7,即:

  • 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
  • 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
  • 总利润为 4 + 3 = 7 。
2. 分析

这道题需要找出在给定股票价格数组 prices 中能获得的最大利润,其中 prices[i] 代表第 i 天的股票价格。规则是在任何一天,可以决定是否购买或者出售股票,但最多只能持有一股股票,并且允许在同一天买入和卖出。题目要求返回可能的最大利润。

关键在于理解在哪些天买入和在哪些天卖出可以获得最大利润。由于可以在同一天买入和卖出,那么只要今天的价格比昨天高,就可以认为昨天买入,今天卖出是有利可图的。

具体策略是:

  • 遍历价格数组,从第二天开始比较。
  • 每当发现今天的价格比昨天的高,就计算这一天的利润(今天的价格减去昨天的价格),并累加到总利润中。

这种策略的好处在于不需要维护任何复杂的状态,只需要在价格上升的时候“买卖”即可。

分析步骤

  1. 初始化一个变量 maxProfit 来存储总利润,初值设为0。
  2. 从第二天开始遍历价格数组。
  3. 对于每一天,如果价格比前一天高,就将差价加到 maxProfit 上。
  4. 最后返回 maxProfit

性能优化关键点

  • 执行速度:这个算法的时间复杂度是 O(n),因为只需要遍历一次价格数组,这是非常高效的。
  • 内存使用:空间复杂度为 O(1),因为我们只使用了常数额外空间。
3. 代码实现
int maxProfit(int* prices, int pricesSize) {
    int32_t i, state, money, buy_price, last_price;

    state = 1; /* 买入 */
    money = 0;
    last_price = buy_price = prices[0];
    for (i = 1; i < pricesSize; i++) {
        if (prices[i] < last_price) {
            /* 降价卖出 */
            if (state) {
                money += last_price - buy_price;
                state = 0;
            }
        } else if (prices[i] > last_price) {
            /* 升价买入 */
            if (!state) {
                buy_price = last_price;
                state = 1;
            }
        }
        last_price = prices[i];
    }

    /* 最后直接卖掉 */
    if (state) {
        money += last_price - buy_price;
    }

    return money;
}

这段代码实现了一个简单的股票交易策略,目标是最大化利润。函数的输入是一个整数数组 prices,表示一段时间内股票的价格变化,数组的大小为 pricesSize

代码的主要逻辑如下:

  1. 初始化变量:state 表示当前的交易状态,1 表示持有股票(买入),0 表示不持有股票(卖出),money 表示当前的总利润,

    buy_price 表示最近一次买入的价格,last_price 表示上一次的股票价格。

  2. 遍历价格数组,从下标 1 开始:

    • 如果当前价格小于上一次的价格(降价):
      • 如果当前持有股票(state 为 1),则卖出股票,计算利润并更新 money,将 state 设为 0。
    • 如果当前价格大于上一次的价格(升价):
      • 如果当前不持有股票(state 为 0),则买入股票,将 buy_price 设为上一次的价格,将 state 设为 1。
    • 更新 last_price 为当前价格。
  3. 遍历结束后,如果仍持有股票(state 为 1),则以最后一个价格卖出,计算利润并更新 money

  4. 返回总利润 money

这个策略的核心思想是:在价格下降时卖出,在价格上升时买入,以期获得最大利润

运行结果如下所示(仅供参考):

代码训练LeetCode(15)买卖股票,#  十年代码训练,leetcode,算法

4. 总结

这个问题考察了对数组遍历和简单逻辑判断的应用,以及如何从实际问题中抽象出有效的解决方案。通过这种问题,可以加强对简单贪心算法的理解和应用。文章来源地址https://www.toymoban.com/news/detail-859460.html

到了这里,关于代码训练LeetCode(15)买卖股票的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode买卖股票之一:基本套路(122)

    这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos 在LeetCode上,有数道和买卖股票有关的题目,覆盖了简单、中等、困难,要求都是选择低价时间买入、高价时间卖出,以求达到利润最大化 这类题型的特点就是:典型的动态规划题型,掌握套路后,

    2024年02月09日
    浏览(43)
  • 【LeetCode】121.买卖股票的最佳时机

    给定一个数组  prices  ,它的第  i  个元素  prices[i]  表示一支给定股票第  i  天的价格。 你只能选择  某一天  买入这只股票,并选择在  未来的某一个不同的日子  卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如

    2024年02月15日
    浏览(38)
  • leetcode121. 买卖股票的最佳时机

    题目: 给定一个数组  prices  ,它的第  i  个元素  prices[i]  表示一支给定股票第  i  天的价格。 你只能选择  某一天  买入这只股票,并选择在  未来的某一个不同的日子  卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大

    2024年02月10日
    浏览(50)
  • [思维]LeetCode:121.买卖股票的最佳时机

      题目链接:121. 买卖股票的最佳时机 - 力扣(Leetcode)   分析:这里的数据大小为1e5,所以使用暴力会TLE. 思路:我们发现, 需要找到最大利润,其目标就是找到当前第i位后的最大值。换位思考,就是找到当前第i位前的最小值。

    2023年04月09日
    浏览(57)
  • 力扣(Leetcode) 121. 买卖股票的最佳时机

    给定一个数组  prices  ,它的第  i  个元素  prices[i]  表示一支给定股票第  i  天的价格。 你只能选择  某一天  买入这只股票,并选择在  未来的某一个不同的日子  卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如

    2024年01月25日
    浏览(42)
  • 【LeetCode股票买卖系列:309. 最佳买卖股票时机含冷冻期 | 暴力递归=>记忆化搜索=>动态规划】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月02日
    浏览(43)
  • LeetCode-题目整理【3】:买卖股票的最佳时机

    买卖股票的最佳时机 都是求最大利润,但是在没有限制,如121和122,动态规划稍微复杂一些,建议不用,到最后两道难题,题目有限制,使用动态规划通过求解子问题的最优解来逐步求解原问题的最优解。 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i]

    2024年01月23日
    浏览(59)
  • LeetCode:121.买卖股票的最佳时机——动态规划

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 关于动态规划:LeetCode:322. 零钱兑换——动态规划从案例入门 题目描述 :给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只

    2023年04月17日
    浏览(37)
  • leetcode-188-买卖股票的最佳时机 IV

    https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

    2024年02月10日
    浏览(39)
  • leetcode 188. 买卖股票的最佳时机 IV

            这道题是 买卖股票的最佳时机III  的升级版,即买卖次数限制为k次,做法和上一篇如法炮制,直接看代码:

    2024年02月12日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包