小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock

这篇具有很好参考价值的文章主要介绍了小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

121 Best Time to Buy and Sell Stock (买卖股票的最佳时机)

你好,2024年的第一个月,又是秋风萧瑟天气凉,草木摇落露为霜。.。。在这个特殊的时代,作为我们普通的一个打工人,我们用这道题,开启对这个不符合经济增长规律的股市反抗一把。

题目描述

有这样一个数组 prices ,其中 prices[i] 是给定股票在 ith天的价格。

我希望通过选择某一天购买一只股票并选择未来的另一天出售该股票来最大化的利润。

返回从本次交易中获得的最大利润。如果你无法获得任何利润,返回 0 。

小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock,leetcode,面试,leetcode,职场和发展
小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock,leetcode,面试,leetcode,职场和发展

这里我个人小白理解分析:

这道题我上来一看就感觉,股市要是能预测成这样,那大家不全都赚到钱了,有些扯。但谁叫面试官喜欢这道题呢,那我还是继续看题吧,毕竟,万一通过刷明白这道题,有钱请白月光吃麻辣烫了呢。
小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock,leetcode,面试,leetcode,职场和发展
这里我们那这个数组来进行理解 [7,1,5,3,6,4]

7 是我们看到的最便宜的开始价格,我们是无法在第一天出售,因此 maxProfit 为 0;

1 现在是我们见过的最便宜的价格。现在出售会我们肯定就亏了,所以我们无法更新 maxProfit;

5 比1贵,但如果我们现在出售,我们得到的最大利润为 4!最好保存起来供以后使用;

3 比1也贵,如果我们出售,我们只获得的利润为2,那么我们不需要在这里做改变;

6 是比1更贵,但如果我们在这里出售,我们会将 maxProfit 增加到 5,使其成为最佳回报利润。

4 比1也贵,如果我们出售,我们只获得的利润为3,比6的时候去卖获得的利润更少,那么我们在这里也不做改变;

解题过程

上来咱就是主打一个快,别让面试官久等了。另外,我还要去请白月光吃饭呢。

public static int maxProfit2(int[] prices){
        // 最大利润
        int maxProfit = 0;
        
        // 遍历所有可能的买入和卖出时机
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                // 计算利润
                int profit = prices[j] - prices[i];
                
                // 更新最大利润
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }

小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock,leetcode,面试,leetcode,职场和发展
小明:OK,完事儿,等着面试官来表扬自己吧。他肯定会说:小子,你是个好手!工位都给你准备好了,工资你说了算。

面试官:嗯,你这个要是nums2 给了十万个数是不是会影响性能?

小明OS:今年这个找工市场,人言洛阳花似锦,偏我来时不逢春。。。怎的,技能要求突然涨了,不是做出来就行?

好吧,逼我拿出压箱底的东西是吧。的确这个算法是偏慢。

话不多说,拿动态方程说话:

dp[i] = max(dp[i - 1], prices[i] - min(prices[0:i]))

其中,

  • dp[i] 表示在第 i 天卖出股票,最大利润
  • prices[i] 表示第 i 天的股票价格
  • min(prices[0:i]) 表示第 0 天到第 i 天中最小的股票价格

小白的理解过程:

动态方程的含义是:在第 i 天卖出股票,最大利润可以从以下两种情况中取最大值:

在第 i - 1 天卖出股票,最大利润
在第 i 天买入股票,然后在第 i 天卖出股票,利润为 prices[i] - min(prices[0:i])

public static int maxProfit(int[] prices) {
        // 最大利润
        int[] dp = new int[prices.length];

        // 初始化
        dp[0] = 0;

        // 计算 dp[i]
        for (int i = 1; i < prices.length; i++) {
            // 计算在第 i 天卖出股票,最大利润
            dp[i] = Math.max(dp[i - 1], prices[i] - min(prices[0:i]));
        }

        // 返回最大利润
        return dp[prices.length - 1];
    }

    private static int min(int[] prices) {
        int minPrice = prices[0];
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            }
        }

        return minPrice;
    }

终于,看到了面试官满意的点头,OK,进入下一面!

小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock,leetcode,面试,leetcode,职场和发展
编码道路漫漫,只要先看脚下的路,徐徐前进即可。文章来源地址https://www.toymoban.com/news/detail-815411.html

到了这里,关于小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C语言中链表经典面试题目

    🐶博主主页: @ᰔᩚ. 一怀明月ꦿ  ❤️‍🔥 专栏系列: 线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C++ 🔥 座右铭: “不要等到什么都没有了,才下定决心去做” 🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀   目录 环

    2024年02月02日
    浏览(81)
  • 算法修炼之路之双指针含多道leetcode 经典题目

    目录 前言  一:普通双指针 1.经典题目一  283移动0问题 分析 代码实现 2.经典题目二 1089复写0  分析 代码实现 二:解决成环类问题-快慢指针  经典例题一 202快乐数 分析  代码实现   三:左右相遇指针 经典例题一 11 盛最多水的容器 分析  代码实现    接下来的日子会顺

    2024年04月13日
    浏览(77)
  • 【pygame游戏开发】这几个经典游戏,小红书Python面试题目

    pygame.time.set_timer(change_hole_event, 800) mole = Mole(cfg.MOLE_IMAGEPATHS, hole_pos) hammer = Hammer(cfg.HAMMER_IMAGEPATHS, (500, 250)) clock = pygame.time.Clock() your_score = 0 flag = False init_time = pygame.time.get_ticks() while True: time_remain = round((61000 - (pygame.time.get_ticks() - init_time)) / 1000.) if time_remain == 40 and not flag: hole

    2024年04月25日
    浏览(52)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(45)
  • 【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   findContentChildren ( self ,  g :  List [ int ],  s

    2024年02月04日
    浏览(55)
  • 经典面试题:谈谈对死锁的理解

    死锁是指在并发系统中,两个或多个进程(或线程)因为彼此互相等待对方释放资源而无法继续执行的状态。 简单来说 ,当多个进程都在等待其他进程所持有的资源时,就可能发生死锁。 当一个线程一把锁,连续加锁两次的时候,如果锁是不可重入锁,就会死锁 补充:C+

    2024年02月12日
    浏览(36)
  • 【LeetCode-经典面试150题-day12】

    20.有效的括号 题意: 给定一个只包括  \\\'(\\\' , \\\')\\\' , \\\'{\\\' , \\\'}\\\' , \\\'[\\\' , \\\']\\\'  的字符串  s  ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 【输入样例】s=\\\"

    2024年02月11日
    浏览(42)
  • 【LeetCode-经典面试150题-day11】

    目录 128.最长连续序列  228.汇总区间  56.合并区间  57.插入区间  452.用最少数量的箭引爆气球   128.最长连续序列 题意: 给定一个未排序的整数数组  nums  ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为  O(n)   的算法

    2024年02月12日
    浏览(44)
  • LeetCode150道面试经典题-- 加一(简单)

    给你一个非负整数 x ,计算并返回  x  的 算术平方根 。 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。 注意: 不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1: 输入:x=4 输出:2   示例 2: 输入: x = 8 输出: 2 解释: 8 的

    2024年02月12日
    浏览(38)
  • 【LeetCode-面试经典150题-day14】

      目录 19.删除链表的倒数第N个结点  82.删除排序链表中的重复元素Ⅱ  61. 旋转链表  86.分隔链表  146.LRU缓存 19.删除链表的倒数第N个结点 题意: 给你一个链表,删除链表的倒数第  n   个结点,并且返回链表的头结点。 【输入样例】head = [1,2,3,4,5],n=2 【输出样例】[1,2,3,5

    2024年02月11日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包