当前位置: 首页 > 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…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...