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

【LeetCode Hot100 贪心算法】 买卖股票的最佳时机、跳跃游戏、划分字母区间

贪心算法

    • 买卖股票的最佳时机
    • 买卖股票的最佳时机II
    • 跳跃游戏
    • 跳跃游戏II
    • 划分字母区间

买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

思路
如果第 i i i 天卖出股票,则最大利润为(该天的股价-前面天数中最小的股价),然后与已知的最大利润比较,如果大于则更新当前最大利润的值。

代码

class Solution {public int maxProfit(int[] prices) {int cost = Integer.MAX_VALUE, profit = 0;for (int i = 0; i < prices.length; i++) {cost = Math.min(cost, prices[i]);profit = Math.max(profit, prices[i] - cost);}return profit;}
}

买卖股票的最佳时机II

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
输入: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 。

思路
分解成每天都买卖,但是只在最后的结果中加入正的,局部最优->全局最优。

代码
注意 i 从 1 开始

class Solution {public int maxProfit(int[] prices) {int profit = 0;for (int i = 1; i< prices.length; i++) {profit += Math.max(prices[i] - prices[i-1], 0);}return profit;}
}

跳跃游戏

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

思路
确定从第一个位置开始,能够跳跃到的范围有多少,如果这个范围能够覆盖到数组的最后一个位置,那么就可以范围true。

代码

class Solution {public boolean canJump(int[] nums) {int cover = 0; // 覆盖范围// 遍历的范围是cover内for (int i = 0; i <= cover; i++) {// 遍历到一个位置,就从上一个cover和该位置能够到达的最远位置取最大值cover = Math.max(cover, i + nums[i]);if (cover >= nums.length - 1) {// 如果能够覆盖到数组的最后一个位置return true;}}return false;}
}

跳跃游戏II

在上一题的基础上,要求返回最少跳跃次数。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

思路
在这里插入图片描述
代码

class Solution {public int jump(int[] nums) {int curRight = 0;   // 已经造桥的右端点int nextRight = 0;  // 下一步造桥最远的端点int ans = 0;  // 答案// for 循环中 i < nums.length - 1// 因为开始的时候边界时第0个位置,ans已经加过一次1了,最后末尾的时候不用计算步数了for (int i = 0; i < nums.length - 1; i++) {nextRight = Math.max(nextRight, i + nums[i]);if (i == curRight) {   // 到达已建造的桥的右端点curRight = nextRight;  // 建造桥ans++;}}return ans;}
}

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:s = “ababcbacadefegdehijhklij”
输出:[9,7,8]
解释:
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的,因为划分的片段数较少。
示例 2:
输入:s = “eccbbbbdec”
输出:[10]

思路
先用一个hash数组把字符串中每一个字母出现的最远位置下标存储在hash数组中。
遍历字符串,更新当前要划分的区间的最远距离(当前最远距离与该位置字母的最远位置下标取最大值)
然后判断此时的最远位置是否是当前位置,如果是说明已经找到了一个划分的区间。
结合代码随项目的思路来解题

代码

class Solution {public List<Integer> partitionLabels(String s) {int[] hash = new int[26];for (int i = 0; i < s.length(); i++) {// 求某个字母的最远位置;使用hash来记录;// s.charAt(i) - 'a'是字母的索引,i是这个字母目前的最远位置hash[s.charAt(i) - 'a'] = i;}int left = 0, right = 0;List<Integer> ans = new ArrayList<>();for (int i = 0; i < s.length(); i++) {// 现有的右边界和当前位置字母的最远出现位置求maxright = Math.max(right, hash[s.charAt(i) - 'a']);// i == right 说明找到了一个分割点if (i == right) {ans.add(right - left + 1);left = right + 1; }  }return ans;}
}

相关文章:

【LeetCode Hot100 贪心算法】 买卖股票的最佳时机、跳跃游戏、划分字母区间

贪心算法 买卖股票的最佳时机买卖股票的最佳时机II跳跃游戏跳跃游戏II划分字母区间 买卖股票的最佳时机 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的…...

互联网架构变迁:从 TCP/IP “呼叫” 到 NDN “内容分发” 的逐浪之旅

本文将给出关于互联网架构演进的一个不同视角。回顾一下互联网的核心理论基础产生的背景&#xff1a; 左边是典型的集中控制通信网络&#xff0c;很容易被摧毁&#xff0c;而右边的网络则没有单点问题&#xff0c;换句话说它很难被全部摧毁&#xff0c;与此同时&#xff0c;分…...

git相关操作笔记

git相关操作笔记 1. git init git init 是一个 Git 命令&#xff0c;用于初始化一个新的 Git 仓库。执行该命令后&#xff0c;Git 会在当前目录创建一个 .git 子目录&#xff0c;这是 Git 用来存储所有版本控制信息的地方。 使用方法如下&#xff1a; &#xff08;1&#xff…...

jenkins 使用 ssh-agent向windows进行部署

背景&#xff1a; jenkins在linux的docker环境内&#xff0c;应用服务部署在windows。需要使用jenkins实现自动化部署。 实现方式&#xff1a; jenkins上构建pipeline任务&#xff0c;脚本如下&#xff1a; 遇到问题&#xff1a; 1、问题&#xff1a;jenkins 调用部署bat脚…...

MySQL入门学习笔记

第一章 数据库系统概述 数据库的4个基本概念 数据、数据库、数据库管理系统、数据库系统是与数据库技术密切相关的4个基本概念 数据 数据是数据库中存储的基本对象&#xff0c;描述事物的符号记录称为数据&#xff0c;数据的表现形式还不能完全表达其内容&#xff0c;需要…...

机器学习全流程解析:数据导入到服务上线全阶段介绍

目录 1. 数据导入 2. 数据预处理 3. 超参数搜索与优化 4. 模型训练 5. 模型评估 6. 模型压缩与优化 7. 模型注册与版本管理 8. 服务上线与部署 总结 1. 数据导入 数据源&#xff1a;数据库、文件系统、API等。数据格式&#xff1a;CSV、JSON、SQL 数据库表、Parquet …...

C#从“Hello World!“开始

是时候一览C#的庐山真面目了。现在&#xff0c;让我们从"Hello World"开始吧&#xff0c;出发&#xff01; 1. 一个简单的C#程序 先来看一段最简单的示例代码&#xff0c;如代码清单2-1所示。 代码清单2-1 HelloWorldClass.cs using System;namespace Programmi…...

LVS 支持 UDP 协议代理

在现代网络架构中,负载均衡技术是保证高可用性和高性能的关键组成部分。Linux Virtual Server(LVS)作为一个高效、稳定的负载均衡解决方案,广泛应用于处理 TCP 流量的场景。然而,随着实时通信、视频流和在线游戏等应用的不断发展,UDP 协议的支持成为了 LVS 负载均衡的重要…...

【C++经典例题】求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a; 期待您的关注 题目描述&#xff1a; 原题链接&#xff1a; 求123...n_牛客题霸_牛客网 (nowcoder.com) 解题思路&#xff1a; …...

Rabbitmq 具体怎么做到削峰的,是丢弃部分消费吗,有的实际场景是不允许丢弃

在高并发场景中&#xff0c;RabbitMQ 可以通过几种策略来实现 削峰&#xff08;缓解瞬时负载激增&#xff09;&#xff0c;而这些策略并不一定需要丢弃消息。在一些业务场景下&#xff0c;丢弃消息显然是不允许的&#xff0c;因此在这种情况下&#xff0c;可以使用以下方法来确…...

Linux渗透实战之Nullbyte靶场提权

0x1 前言 一、浅谈 哈喽师傅们&#xff0c;这次又到了给师傅们分享文章的时候了&#xff0c;这篇文章呢主要是给师傅们以vulnhub中的Nullbyte靶场来给师傅们演示下通过Hydra表单暴力破解等操作拿到账户密码&#xff0c;然后中间以四种sql注入的方式给大家非常详细的操作了sql…...

(STM32笔记)十二、DMA的基础知识与用法 第三部分

我用的是正点的STM32F103来进行学习&#xff0c;板子和教程是野火的指南者。 之后的这个系列笔记开头未标明的话&#xff0c;用的也是这个板子和教程。 DMA的基础知识与用法 三、DMA程序验证1、DMA 存储器到存储器模式实验&#xff08;1&#xff09;DMA结构体解释&#xff08;2…...

品牌账号矩阵如何打造?来抄作业

在讲究全域营销的当下&#xff0c;目前企业都在各自搭建品牌矩阵号&#xff0c;以提升自己在不同渠道上的影响力。虽然不同平台之间有诸多细节值得深究&#xff0c;但也不妨碍我们先了解如何搭建品牌矩阵。接下来&#xff0c;就让我们一同来了解下该如何搭建。 一、一个主账号 …...

基于vue的商城小程序的毕业设计与实现(源码及报告)

环境搭建 ☞☞☞ ​​​Vue入手篇(一)&#xff0c;防踩雷(全网最详细教程)_vue force-CSDN博客 目录 一、功能介绍 二、登录注册功能 三、首页 四、项目截图 五、源码获取 一、功能介绍 用户信息展示&#xff1a;页面顶部设有用户头像和昵称展示区&#xff0c;方便用户识别…...

NineData云原生智能数据管理平台新功能发布|2024年12月版

本月发布 7 项更新&#xff0c;其中重点发布 2 项、功能优化 5 项。 重点发布 数据库 Devops - Oracle 非表对象支持可视化创建与管理 Oracle 非表对象&#xff0c;包括视图&#xff08;View&#xff09;、包&#xff08;Package&#xff09;、存储过程&#xff08;Procedur…...

【Vue.js 组件化】高效组件管理与自动化实践指南

文章目录 摘要引言组件命名规范与组织结构命名规范目录组织 依赖管理工具自动化组件文档生成构建自动引入和文档生成的组件化体系代码结构自动引入组件配置使用 Storybook 展示组件文档自动生成 代码详解QA 环节总结参考资料 摘要 在现代前端开发中&#xff0c;组件化管理是 V…...

Clojure语言的并发编程

Clojure语言的并发编程 引言 在现代软件开发中&#xff0c;并发编程成为了处理多个任务、提高应用效率和响应速度的重要手段。尤其是在多核处理器逐渐成为主流的今天&#xff0c;如何高效利用这些计算资源是每个开发者面临的挑战。Clojure作为一种函数式编程语言&#xff0c;…...

RabbitMQ-SpringAMQP使用介绍

RabbitMQ 1. Spring AMQP1.1 引入依赖1.2 消息发送1.3 消息接收1.4 WorkQueue模型1.4.1 实例代码1.4.2 能者多劳1.4.3 总结 1.5交换机1.6 Fanout交换机&#xff08;广播&#xff09;1.7 Direct交换机&#xff08;订阅&#xff09;1.8 Topic交换机&#xff08;通配符订阅&#x…...

ASP.NET Core 中服务生命周期详解:Scoped、Transient 和 Singleton 的业务场景分析

前言 在 ASP.NET Core 中&#xff0c;服务的生命周期直接影响应用的性能和行为。通过依赖注入容器 (Dependency Injection, DI)&#xff0c;我们可以为服务定义其生命周期&#xff1a;Scoped、Transient 和 Singleton。本文将详细阐述这些生命周期的区别及其在实际业务中的应用…...

c语言----------小知识

1 system函数的使用 #include <stdlib.h> int system(const char *command); 功能&#xff1a;在已经运行的程序中执行另外一个外部程序 参数&#xff1a;外部可执行程序名字 返回值&#xff1a; 成功&#xff1a;0 失败&#xff1a;任意数字示例代码&#xff1a; #inc…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...