打卡一个力扣题目

这篇具有很好参考价值的文章主要介绍了打卡一个力扣题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、问题

二、解题办法一

三、解题方法二

四、对比分析


关于 ARTS 的释义 —— 每周完成一个 ARTS:
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人,延续好奇、探索、实践、分享的精神。

一、问题

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

二、解题办法一

def max_profit(prices):
    if not prices:
        return 0

    min_price = prices[0]
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)

    return max_profit

这段代码实现了一个函数 `max_profit`,用于计算在给定的股票价格数组中,选择某一天买入并在未来某一个不同的日子卖出所能获取的最大利润。

首先判断输入的价格数组是否为空,如果为空则直接返回 0。

然后定义两个变量 `min_price` 和 `max_profit`,分别表示当前遍历到的价格中的最低价格和最大利润。初始时将它们都设置为数组的第一个元素。

接下来使用循环遍历整个价格数组,对于每个遍历到的价格,先更新 `min_price` 为当前遍历到的价格和之前记录的最低价格中的较小值,这样可以保证后续计算利润时使用的是更小的价格。

然后计算当前遍历到的价格与 `min_price` 之间的差值,即当前可以选择的利润。将这个利润与之前记录的最大利润比较,取较大值作为新的 `max_profit`。

最后返回 `max_profit` 作为结果。

需要注意的是,这段代码的时间复杂度为 O(n),其中 n 是输入的价格数组的长度。

提示:可简单介绍学习打卡过程中遇到的困难和对应的解决方法~

三、解题方法二

以下是另一种解题思路,使用动态规划的方法实现。

def max_profit(prices):
    if not prices:
        return 0

    n = len(prices)
    dp = [[0] * 2 for _ in range(n)]

    dp[0][0] = -prices[0]
    dp[0][1] = 0

    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

    return dp[n-1][1]

这段代码中,我们定义了一个二维数组 `dp`,其中 `dp[i][j]` 表示在第 i 天买入并在第 j 天卖出所能获取的最大利润。由于题目要求选择某一天买入并在未来某一个不同的日子卖出,因此我们在计算 `dp[i][j]` 时需要同时考虑两种情况,即在第 i 天买入或在第 i-1 天买入。这样就得到了一个二维的动态规划状态转移方程。

首先初始化 `dp[0][0]` 为 `-prices[0]`,表示如果不进行任何操作,则第一天亏损了价格;初始化 `dp[0][1]` 为 0,表示如果在第一天买入,则第一天没有获得利润。

然后从第 1 天开始遍历到第 n-1 天,对于每个遍历到的天数 i,分别计算在第 i 天买入和在第 i-1 天买入所能获取的最大利润,并取其中的较大值作为当前状态的最优解。具体来说,如果在第 i 天买入,则 `dp[i][0]` 可以取到 `dp[i-1][1] - prices[i]`;如果在第 i-1 天买入,则 `dp[i][1]` 可以取到 `dp[i-1][0] + prices[i]`。最后返回 `dp[n-1][1]` 作为结果。

四、对比分析

这两种方法的时间复杂度都是 O(n),其中 n 是输入的价格数组的长度。因此它们的时间复杂度是相同的,都可以在较短的时间内解决问题。

但是从代码实现的角度来看,这两种方法有一些不同之处。第一种方法使用了循环遍历整个价格数组,并在遍历过程中不断更新最小价格和最大利润。这种方法比较直观,易于理解,但是当价格数组很大时,可能会导致内存占用过高。

第二种方法使用了动态规划的思想,将问题分解为若干个子问题,并通过状态转移方程求解出每个子问题的最优解。这种方法可以有效地减少重复计算,避免了空间复杂度过高的问题。同时,由于动态规划的状态转移方程较为简单,因此代码实现也相对简洁。

综上所述,两种方法各有优缺点,可以根据具体的情况选择适合的方法来解决问题。文章来源地址https://www.toymoban.com/news/detail-615937.html

到了这里,关于打卡一个力扣题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 打卡力扣题目九

    #左耳听风 ARST 打卡活动重启# 目录  一、问题  二、解题方法一  三、解题方法二 四、两种方法的区别 关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share

    2024年02月14日
    浏览(38)
  • 打卡力扣题目十一

    #左耳听风 ARST 打卡活动重启# 目录  一、问题 二、解题方法一  三、解题方法二  四、区别  关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有

    2024年02月14日
    浏览(31)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(48)
  • 力扣数组类题目--41缺失的第一个正数

    41 缺失的第一个正数 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案 。 示例 1: 输入:nums = [1,2,0] 输出:3 示例 2: 输入:nums = [3,4,-1,1] 输出:2 示例 3: 输入:nums = [7,8,9,11,12

    2024年02月11日
    浏览(38)
  • 算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树

    Leetcode 738.单调递增的数字 题目链接:738.单调递增的数字  大佬视频讲解:单调递增的数字视频讲解  个人思路 这个题目就是从例子中找规律,例如 332,从后往前遍历,32不是单调递增将2变为9,3减1,变成了329,遍历到2,32不是递增,将2变为9,3减1,变成299,符合题目条件,打印

    2024年04月16日
    浏览(46)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

    Leetcode 70. 爬楼梯(进阶版) 题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,

    2024年04月14日
    浏览(65)
  • 力扣(LeetCode)算法_C++—— 快乐数

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果 n 是

    2024年02月09日
    浏览(40)
  • 算法学习——LeetCode力扣回溯篇2

    40. 组合总和 II - 力扣(LeetCode) 描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 示例 示例 1: 输入: candidates = [10,1,2,7

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

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

    2024年04月13日
    浏览(77)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包