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

秋招算法备战第32天 | 122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

通过做差可以得到利润序列,然后只要利润需求的非负数求和就可以,因为这里没有手续费,某天买入之后买出可以等价为这几天连续买入卖出

class Solution:def maxProfit(self, prices: List[int]) -> int:profit = 0for i in range(1, len(prices)):profit += max(prices[i]-prices[i-1], 0)return profit

55. 跳跃游戏 - 力扣(LeetCode)

这是一个常见的贪心算法问题。我们从数组的第一个元素开始,保持跟踪我们能到达的最远的下标。然后,我们迭代数组中的每个元素,并更新我们能到达的最远下标。如果我们能到达的最远下标大于或等于数组的长度,我们就知道我们可以到达数组的最后一个元素。以下是Python语言实现此算法的代码:

def canJump(nums):max_jump = 0for i, num in enumerate(nums):if i > max_jump:return Falsemax_jump = max(max_jump, i + num)return True

这个函数的工作原理是这样的:

  • max_jump 记录了在迭代过程中可以跳到的最远的下标。
  • enumerate(nums)会遍历数组并且返回每个元素的索引i和值num。
  • 如果当前索引i超过了我们可以跳到的最远的下标,那么我们就返回False,因为我们不能到达当前索引。
  • 否则,我们更新 max_jump 的值,为当前的 max_jumpi + num 中较大的一个。这是因为,从索引i我们可以跳到的最远的下标是 i + num

然后,如果我们没有提前返回False,那么在遍历完数组后,我们就返回True,因为我们可以到达数组的最后一个元素。

45. 跳跃游戏 II - 力扣(LeetCode)

这个问题也是一个贪心算法问题,与跳跃游戏 I 的问题相似,但是我们现在需要找出到达最后一个下标的最小跳跃次数。

我们可以追踪当前位置的最大跳跃范围,并将其与最大跳跃范围内的所有位置的最大跳跃范围进行比较。我们可以保留最大跳跃范围的索引,然后当当前位置到达或超过当前的最大跳跃范围时,我们更新最大跳跃范围并将跳跃次数加1。

以下是Python语言实现此算法的代码:

def jump(nums):n, max_reach, steps, end = len(nums), 0, 0, 0for i in range(n - 1):max_reach = max(max_reach, i + nums[i])if i == end:end = max_reachsteps += 1return steps

这个函数的工作原理是这样的:

  • max_reach 记录了在迭代过程中可以跳到的最远的下标。
  • steps 记录了跳跃的次数。
  • end 记录了当前的最大跳跃范围。
  • 如果当前索引i等于当前的最大跳跃范围,那么我们更新 end 的值为 max_reach,并且 steps 加1,因为我们需要跳跃到新的位置。

总结

Summary

📈 通过贪心算法解决股票买卖和跳跃游戏问题。

Facts

  • 📈 买卖股票的最佳时机 II: 通过做差可以得到利润序列,然后只要利润非负数求和即可,没有手续费。
  • 🏃 跳跃游戏: 使用贪心算法,遍历数组并保持跟踪最远能到达的下标。
  • 🏃 跳跃游戏 II: 同样是贪心算法,找出到达最后一个下标的最小跳跃次数。保持最大跳跃范围并逐步更新。

相关文章:

秋招算法备战第32天 | 122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II

122. 买卖股票的最佳时机 II - 力扣(LeetCode) 通过做差可以得到利润序列,然后只要利润需求的非负数求和就可以,因为这里没有手续费,某天买入之后买出可以等价为这几天连续买入卖出 class Solution:def maxProfit(se…...

Python状态模式介绍、使用

一、Python状态模式介绍 Python状态模式(State Pattern)是一种行为型设计模式,它允许对象在不同的状态下表现不同的行为,从而避免在代码中使用多重条件语句。该模式将状态封装在独立的对象中,并根据当前状态选择不同的…...

Github-Copilot初体验-Pycharm插件的安装与测试

引言: 80%代码秒生成!AI神器Copilot大升级 最近copilot又在众多独角兽公司的合力下,取得了重大升级。GitHub Copilot发布还不到两年, 就已经为100多万的开发者,编写了46%的代码,并提高了55%的编码速度。 …...

Spring AOP API详解

上一章介绍了Spring对AOP的支持,包括AspectJ和基于schema的切面定义。在这一章中,我们将讨论低级别的Spring AOP API。对于普通的应用,我们推荐使用前一章中描述的带有AspectJ pointcuts 的Spring AOP。 6.1. Spring 中的 Pointcut API 这一…...

分治法 Divide and Conquer

1.分治法 分治法(Divide and Conquer)是一种常见的算法设计思想,它将一个大问题分解成若干个子问题,递归地解决每个子问题,最后将子问题的解合并起来得到整个问题的解。分治法通常包含三个步骤: 1. Divid…...

super(Module_ModuleList, self).__init__()的作用是什么?

class Module_ModuleList(nn.Module):def __init__(self):super(Module_ModuleList, self).__init__()self.linears nn.ModuleList([nn.Linear(10, 10)])在这段代码中,super(Module_ModuleList, self).__init__() 的作用是调用父类 nn.Module 的 __init__ 方法&…...

【并发专题】操作系统模型及三级缓存架构

目录 课程内容一、冯诺依曼计算机模型详解1.计算机五大核心组成部分2.CPU内部结构3.CPU缓存结构4.CPU读取存储器数据过程5.CPU为何要有高速缓存 学习总结 课程内容 一、冯诺依曼计算机模型详解 现代计算机模型是基于-冯诺依曼计算机模型 计算机在运行时,先从内存中…...

java基础复习(第二日)

java基础复习(二) 1.抽象的(abstract)方法是否可同时是静态的(static),是否可同时是本地方法(native),是否可同时被 synchronized修饰? 都不能。 抽象方法需要子类重写…...

Ansible自动化运维工具

Ansible自动化运维工具 一、ansible介绍二、ansible环境安装部署三、ansible命令行模块1、command模块2、shell模块3、cron模块4、user模块5、group模块6、copy模块7、file模块8、hostname模块9、ping模块10、yum模块11、service/systemd模块12、script模块13、mount模块14、ar…...

LeetCode-116-填充每个节点的下一个右侧节点指针

一:题目描述: 给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node {int val;Node *left;Node *right;Node *next; }填充它的每个 next 指针,让这个指…...

前端面试的性能优化部分(3)每篇10题

21.如何优化移动端网页的性能? 优化移动端网页的性能是提升用户体验、降低用户流失的关键。以下是一些优化移动端网页性能的常见方法: 压缩和合并资源: 压缩 CSS、JavaScript 和图片等静态资源,减少文件大小,同时合并…...

如何通过企业工商信息初步判断企业是否靠谱?

银行、投资机构等对企业进行融资、授信、合作时,需要如何评估企业的可靠性。企业工商信息作为企业的基础信息,是初步判断企业是否靠谱的重要依据之一,通过对企业工商信息的综合分析,我们可以了解企业的经营状况、财务实力、法律风…...

ChatGPT+知乎,20分钟超越专业大V的调教方法

AI技术正在迅速发展,渗透到我们的生活中,尤其在内容营销领域。 AI算法帮助我们生成文本、优化搜索引擎排名,提升用户体验等,这些创新正在塑造时代的前进方向,AI也将引领未来十年的变革。对于每个创业者、内容创作者和…...

git branch --show-current 和 git rev-parse --abbrev-ref HEAD 区别

git branch --show-current 和 git rev-parse --abbrev-ref HEAD 区别 git branch --show-current 和 git rev-parse --abbrev-ref HEAD 命令都可以用于获取当前所在的 Git 分支名称。 但是,它们之间有一些不同点: git branch --show-current 命令是 G…...

【TypeScript】接口类型 Interfaces 的使用理解

导语: 什么是 类型接口? 在面向对象语言中,接口(Interfaces)是一个很重要的概念,它是对行为的抽象,而具体如何行动需要由类(classes)去实现(implement&#x…...

2023-07-31 C语言根据错误号打印详细的错误信息perror(““) 或者strerror(errno)

一、C 语言可以使用perror("perror output"); 或 strerror(errno)打印详细的错误信息。 二、需要的头文件#include <errno.h>。 三、实例测试&#xff0c;这里我让open一个linux 底层杂项设备失败的情况&#xff0c;返回的是一个负数&#xff0c;强制返回-EN…...

JDK17和JDK8完美卸载方法及新版JDK安装教程

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

FPGA设计时序分析二、建立/恢复时间

目录 一、背景知识 1.1 理想时序模型 1.2 实际时序模型 1.2.1 时钟不确定性 1.2.2 触发器特性 二、时序分析 2.1 时序模型图 ​2.2 时序定性分析 一、背景知识 之前的章节提到&#xff0c;时钟对于FPGA的重要性不亚于心脏对于人的重要性&#xff0c;所有的逻辑运算都离开…...

oracle建立自动增长字段

oracle数据库与其他的数据库不太一样&#xff0c;比如在mysql里自动增长只要设定“auto_increment”即可。可是在oracle里就没有这种配置了。以oracle11g为例&#xff0c;建立自动增长的字段。操作如下&#xff1a; --创建表 create table USERINFO ( ID NUMBER , …...

【Git】远程仓库的创建、SSH协议克隆、拉取、推送

目录 一、创建远程仓库 二、HTTPS协议克隆仓库 三、SSH协议克隆仓库 四、向远程仓库推送 五、从远程仓库拉取 六、忽略特殊文件 七、配置命令别名 一、创建远程仓库 首先我们可以从GitHub或者Gitee中创建自己的个人仓库 工作台 - Gitee.comhttps://gitee.com/ 二、HTT…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...