当前位置: 首页 > news >正文

打卡一个力扣题目

目录

一、问题

二、解题办法一

三、解题方法二

四、对比分析


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

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

一、问题

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

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

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

二、解题办法一

def max_profit(prices):if not prices:return 0min_price = prices[0]max_profit = 0for price in prices:min_price = min(min_price, price)profit = price - min_pricemax_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 0n = len(prices)dp = [[0] * 2 for _ in range(n)]dp[0][0] = -prices[0]dp[0][1] = 0for 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 是输入的价格数组的长度。因此它们的时间复杂度是相同的,都可以在较短的时间内解决问题。

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

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

综上所述,两种方法各有优缺点,可以根据具体的情况选择适合的方法来解决问题。

相关文章:

打卡一个力扣题目

目录 一、问题 二、解题办法一 三、解题方法二 四、对比分析 关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有观点…...

【SSM—SpringMVC】 问题集锦(持续更新)

目录 1.Tomcat启动,部署工件失败 1.Tomcat启动,部署工件失败 解决:使用SpringMVC,添加Web支持,要将项目结构进行添加WEB-INF下添加lib目录,将依赖添进去...

2022年全国职业院校技能大赛(高职组)“软件测试”赛项接口测试任务书

任务七 接口测试 执行接口测试 本部分按照要求,执行接口测试;使用接口测试工具PostMan,编写脚本、配置参数、执行接口测试并且截图,截图需粘贴在接口测试总结报告中。 接口测试具体要求如下: 题目1:资产…...

Docker 如何助您成为数据科学家

一、说明 在过去的 5 年里,我听到了很多关于 docker 容器的嗡嗡声。似乎我所有的软件工程朋友都在使用它们来开发应用程序。我想弄清楚这项技术如何使我更有效率,但我发现网上的教程要么太详细:阐明我作为数据科学家永远不会使用的功能&#…...

机器学习01 -Hello World(对鸢尾花(Iris Flower)进行训练及测试)

什么是机器学习? 机器学习是一种人工智能(AI)的子领域,它探索和开发计算机系统,使其能够从数据中学习和改进,并在没有明确编程指令的情况下做出决策或完成任务。 传统的程序需要程序员明确编写指令来告诉…...

android studio JNI开发

一、JNI的作用: 1.使Java与本地其他类型语言(C、C)交互; 2.在Java代码调用C、C等语言的代码 或者 C、C调用Java代码。 由于JAVA具有跨平台的特点,所以JAVA与本地代码的交互能力弱,采用JNI特性可以增强JA…...

CSS 高频按钮样式

矩形与圆角按钮 正常而言&#xff0c;我们遇到的按钮就这两种 -- 矩形和圆角&#xff1a; 它们非常的简单&#xff0c;宽高和圆角和背景色。 <div classbtn rect>rect</div><div classbtn circle>circle</div>.btn {margin: 8px auto;flex-shrink: 0;…...

系列二、RocketMQ简介

一、概述 RocketMQ是一款阿里巴巴开源的消息中间件。2016年11月28日&#xff0c;阿里巴巴向Apache软件基金会捐赠RabbitMQ&#xff0c;成为Apache孵化项目。2017年9月25日&#xff0c;Apache宣布RocketMQ孵化成为Apache顶级项目&#xff08;TLP&#xff09;&#xff0c;成为国内…...

论文笔记--Skip-Thought Vectors

论文笔记--Skip-Thought Vectors 1. 文章简介2. 文章概括3 文章重点技术3.1 Skip Thought Vectors3.2 词表拓展 4. 文章亮点5. 原文传送门6. References 1. 文章简介 标题&#xff1a;Skip-Thought Vectors作者&#xff1a;Ryan Kiros, Yukun Zhu, Ruslan Salakhutdinov, Rich…...

1400*B. Karen and Coffee

Examples input 3 2 4 91 94 92 97 97 99 92 94 93 97 95 96 90 100 output 3 3 0 4 input 2 1 1 1 1 200000 200000 90 100 output 0 解析&#xff1a; 题意为&#xff0c;给你多个区间&#xff08;会有重叠&#xff09;&#xff0c;每个区间的每个值都会为这个值累加…...

【业务功能篇54】Springboot项目常用工具类:HTTP状态码/客户端request

状态码常量类 /*** 返回状态码**/ public class HttpStatus {/*** 操作成功*/public static final int SUCCESS 200;/*** 对象创建成功*/public static final int CREATED 201;/*** 请求已经被接受*/public static final int ACCEPTED 202;/*** 操作已经执行成功&#xff0…...

Fine Logic

登录—专业IT笔试面试备考平台_牛客网 题目大意&#xff1a;有n个数分别为1~n&#xff0c;有m个数值对(u,v)表示u要排在v左边&#xff0c;问至少要多少个排列才能满足所有数值对至少一次 2<n<1e6;1<m<1e6 思路&#xff1a;如果数值对中要求u在v左边&#xff0c;…...

Neo4j图数据基本操作

Neo4j 文章目录 Neo4jCQL结点和关系增删改查匹配语句 根据标签匹配节点根据标签和属性匹配节点删除导入数据目前的问题菜谱解决的问题 命令行窗口 neo4j.bat console 导入rdf格式的文件 :GET /rdf/ping CALL n10s.graphconfig.init(); //初始化 call n10s.rdf.import.fetch(&q…...

前端JavaScript面试100问(中)

31、http 的理解 ? HTTP 协议是超文本传输协议&#xff0c;是客户端浏览器或其他程序“请求”与 Web 服务器响应之间的应用层通信协议。HTTPS主要是由HTTPSSL构建的可进行加密传输、身份认证的一种安全通信通道。32、http 和 https 的区别 ? 1、https协议需要到ca申请证书&…...

Docker 安全及日志管理与https部署

容器的安全性问题的根源在于容器和宿主机共享内核。如果容器里的应用导致Linux内核崩溃&#xff0c;那么整个系统可能都会崩溃。与虚拟机是不同的&#xff0c;虚拟机并没有与主机共享内核&#xff0c;虚拟机崩溃一般不会导致宿主机崩溃。 Docker 容器与虚拟机的区别 虚拟机通…...

2.3 HLSL常用函数

一、函数介绍 函数图像参考网站&#xff1a;Graphtoy 1.基本数学运算 函数 含义 示例图 min(a,b) 返回a、b中较小的数值 mul(a,b) 两数相乘用于矩阵计算 max(a,b) 返回a、b中较大的数值 abs(a) 返回a的绝对值 round(x) 返回与x最近的整数 sqrt(x) 返回x的…...

互联网的发展

概述 互联网是现代社会中举足轻重的一个领域&#xff0c;它的发展对于人类的生活和工作方式产生了深远的影响。互联网的发展经历了几个阶段&#xff0c;从初创阶段到如今的高度普及和深入应用&#xff0c;本文将详细介绍互联网的发展状况。 第一阶段&#xff1a;互联网的起源…...

STM32 CAN通讯实验程序

目录 STM32 CAN通讯实验 CAN硬件原理图 CAN外设原理图 TJA1050T硬件描述 实验线路图 回环实验 CAN头文件配置 CAN_GPIO_Config初始化 CAN初始化结构体 CAN筛选器结构体 接收中断优先级配置 接收中断函数 main文件 实验现象 补充 STM32 CAN通讯实验 CAN硬件原理图…...

Python代码片段之Django静态文件URL的配置

首先要说明这段python代码并不完整&#xff0c;而且我也没有做过测试&#xff0c;只是我在工作时参考了其中的一些个方法。这是我在找python相关源码资料里看到的一段代码&#xff0c;是Django静态文件URL配置代码片段2&#xff0c;代码中有些方法还是挺技巧的&#xff0c;做其…...

基于飞桨paddle的极简方案构建手写数字识别模型测试代码

基于飞桨paddle的极简方案构建手写数字识别模型测试代码 原始测试图片为255X252的图片 因为是极简方案采用的是线性回归模型&#xff0c;所以预测结果数字不一致 本次预测的数字是 [[3]] 测试结果&#xff1a; PS E:\project\python> & D:/Python39/python.exe e:/pro…...

从攻到防:实战演练基于Wireshark与Snort的DoS攻击检测

1. 拒绝服务攻击初探&#xff1a;原理与危害剖析 想象一下周末去热门餐厅吃饭的场景。当所有座位都被占满&#xff0c;门口还不断涌入大量"假顾客"时&#xff0c;真正的食客就会被挡在门外——这就是拒绝服务攻击&#xff08;DoS&#xff09;的生动写照。作为网络安…...

从游戏机到影音中心:用wiliwili解锁Switch的隐藏娱乐潜能

从游戏机到影音中心&#xff1a;用wiliwili解锁Switch的隐藏娱乐潜能 【免费下载链接】wiliwili 专为手柄控制设计的第三方跨平台B站客户端&#xff0c;目前可以运行在PC全平台、PSVita、PS4 和 Nintendo Switch上 项目地址: https://gitcode.com/GitHub_Trending/wi/wiliwil…...

XposedRimetHelper:突破地理限制的系统级定位解决方案

XposedRimetHelper&#xff1a;突破地理限制的系统级定位解决方案 【免费下载链接】XposedRimetHelper Xposed 钉钉辅助模块&#xff0c;暂时实现模拟位置。 项目地址: https://gitcode.com/gh_mirrors/xp/XposedRimetHelper 一、移动办公的地理枷锁&#xff1a;企业考勤…...

2026年实测10款降AI工具:毕业论文降AIGC哪款最靠谱?

2026年毕业季临近&#xff0c;降低论文AI生成痕迹、通过学校AIGC检测已经成为所有毕业生的必过关卡。但当前降AI工具市场鱼龙混杂&#xff1a;不少用户花了高价处理&#xff0c;AI率却纹丝不动&#xff1b;还有的工具改完的论文语句生硬、逻辑混乱&#xff0c;反而过不了答辩。…...

2026年,山东专业联想服务器解决方案,涵盖SR858 V3等众多型号!

在当今数字化飞速发展的时代&#xff0c;服务器作为企业数据处理和存储的核心设备&#xff0c;其性能和可靠性至关重要。联想服务器凭借其卓越的性能、丰富的功能和广泛的应用场景&#xff0c;成为众多企业的首选。今天&#xff0c;我们就来详细了解一下联想SR858 V3服务器。联…...

零基础友好:快马AI为你定制专属visual studio code图文安装与上手教程

作为一名从零开始学习编程的新手&#xff0c;我深刻体会到安装开发环境是很多人遇到的第一个"拦路虎"。最近在InsCode(快马)平台上发现了一个特别适合新手的Visual Studio Code安装教程项目&#xff0c;它完全解决了我的困惑。下面分享我的学习笔记&#xff0c;希望能…...

RWKV7-1.5B-G1A助力运维:利用Xshell脚本自动化模型部署与监控

RWKV7-1.5B-G1A助力运维&#xff1a;利用Xshell脚本自动化模型部署与监控 1. 引言 "又到周五下午4点&#xff0c;运维团队收到紧急需求——需要在10台服务器上部署最新的RWKV7-1.5B-G1A模型服务。"这样的场景对运维工程师来说再熟悉不过。传统的手动部署方式不仅耗…...

LVGL V8项目实战:手把手教你用CLion配置CMake,集成Gui Guider生成的UI文件(含避坑指南)

LVGL V8项目实战&#xff1a;CLion与CMake深度集成Gui Guider UI文件的完整指南 当你在嵌入式GUI开发中频繁往返于设计工具与代码编辑器之间时&#xff0c;是否经历过这样的困境&#xff1a;在Gui Guider中精心设计的界面&#xff0c;移植到LVGL项目后却遭遇编译错误、资源路径…...

避坑指南:用高德DistrictSearch获取精准行政边界时遇到的5个典型问题(含最新GeoJson处理技巧)

高德DistrictSearch深度避坑&#xff1a;5个实战难题与GeoJson优化方案 当你在深夜调试地图边界数据时&#xff0c;突然发现某个街道的轮廓出现了诡异的锯齿状变形——这不是恐怖片情节&#xff0c;而是使用高德DistrictSearch时可能遇到的真实场景。作为经历过数十个地图项目…...

RouterOS网桥VLAN实战:从零构建安全隔离的二层虚拟网络

1. VLAN基础与RouterOS网桥概述 刚接触网络管理的朋友可能经常听到"VLAN"这个词&#xff0c;但总觉得它神秘莫测。其实VLAN就像给一栋办公楼划分不同部门&#xff1a;财务部、研发部、市场部各自有独立的办公区域&#xff0c;既保证了隐私安全&#xff0c;又避免了相…...