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

代码随想录第32天|● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

文章目录

  • 买卖股票
    • 思路一:贪心
      • 代码:
    • 思路:动态规划
      • 代码:
  • 跳跃游戏
    • 思路:贪心找最大范围
    • 代码:
  • 跳跃游戏②
    • 思路:
      • 代码:
    • 方法二:处理方法一的特殊情况

买卖股票

在这里插入图片描述

思路一:贪心

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

代码:

// 贪心思路
class Solution {public int maxProfit(int[] prices) {int result = 0;for (int i = 1; i < prices.length; i++) {//如果为正result += Math.max(prices[i] - prices[i - 1], 0);}return result;}
//或者
class Solution {public int maxProfit(int[] prices) {int res=0;for(int i=1;i<prices.length;i++){//如果递增if(prices[i]>prices[i-1]){res+=prices[i]-prices[i-1];}}return res;}
}

思路:动态规划

在这里插入图片描述

代码:

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

跳跃游戏

在这里插入图片描述

思路:贪心找最大范围

在这里插入图片描述
在这里插入图片描述

代码:

class Solution {public boolean canJump(int[] nums) {if (nums.length == 1) {return true;}//覆盖范围, 初始覆盖范围应该是0,因为下面的迭代是从下标0开始的int cover=0;//在覆盖范围内更新最大的覆盖范围for(int i=0;i<=cover;i++){cover=Math.max(cover,i+nums[i]);//cover:当前步数覆盖范围 i+nums[i]扩展范围if(cover>=nums.length-1)return true;}return false;}
}

跳跃游戏②

在这里插入图片描述

思路:

在这里插入图片描述
记录这一步的最大覆盖范围,在这个覆盖范围里,去找里面包含的(下一步能达到的最大覆盖范围)。按照最大覆盖范围去跳,次数就会最少。
每找到一次覆盖范围则相当于跳跃了一次
在这里插入图片描述
在这里插入图片描述

代码:

遇到终点则停止

class Solution {public int jump(int[] nums) {if (nums.size() == 1) return 0;//单一数组int curdis=0;  // 当前覆盖最远距离下标int nextdis=0; // 下一步覆盖最远距离下标int ans=0;  // 记录走的最大步数for (int i = 0; i < nums.length; i++) {nextdis=Math.max(nextdis,i+nums[i]);// 更新下一步覆盖最远距离下标if(i==curdis){ // 遇到当前覆盖最远距离下标ans++;curdis = nextdis;if(nextdis>=nums.length-1)break;}}return ans;}
}

方法二:处理方法一的特殊情况

// 版本二
class Solution {public int jump(int[] nums) {int result = 0;// 当前覆盖的最远距离下标int curdis = 0;// 下一步覆盖的最远距离下标int nextdis = 0;for (int i = 0; i < nums.length - 1; i++) {nextdis = Math.max(nextdis, i + nums[i]);// 可达位置的改变次数就是跳跃次数if (i == curdis) {curdis = nextdis;result++;}}return result;}
}

相关文章:

代码随想录第32天|● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

文章目录 买卖股票思路一&#xff1a;贪心代码&#xff1a; 思路&#xff1a;动态规划代码&#xff1a; 跳跃游戏思路&#xff1a;贪心找最大范围代码&#xff1a; 跳跃游戏②思路&#xff1a;代码&#xff1a; 方法二&#xff1a;处理方法一的特殊情况 买卖股票 思路一&#x…...

线性代数的本质 2 线性组合、张成的空间、基

基于3Blue1Brown视频的笔记 一种新的看待方式 对于一个向量&#xff0c;比如说&#xff0c;如何看待其中的3和-2&#xff1f; 一开始&#xff0c;我们往往将其看作长度&#xff08;从向量的首走到尾部&#xff0c;分别在x和y上走的长度&#xff09;。 在有了数乘后&#xff0…...

- 工程实践 - 《QPS百万级的有状态服务实践》01 - 存储选型实践

本文属于专栏《构建工业级QPS百万级服务》 《QPS百万级的无状态服务实践》已经完成。截止目前为止&#xff0c;支持需求“给系统传入两个日期&#xff0c;计算间隔有多少天”的QPS百万级服务架构已经完成。如图1&#xff1a; 图1 可是这个架构不能满足需求“给系统传入两个日期…...

SECS/GEM的HSMS通讯?金南瓜方案

High Speed SECS Message Service (HSMS) 是一种基于 TCP/IP 的协议&#xff0c;它使得 SECS 消息通信更加快速。这通常用作设备间通信的接口。 HSMS 状态逻辑变化&#xff08;序列&#xff09;&#xff1a; 1.Not Connected&#xff1a;准备初始化 TCP/IP 连接&#xff0c;但尚…...

wayland(xdg_wm_base) + egl + opengles——dma_buf 作为纹理数据源(五)

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、EGL dma_buf import 相关的数据结构和函数1. EGLImageKHR2. eglCreateImageKHR()3. glEGLImageTargetTexture2DOES()二、egl 中 import dma_buf 作为纹理的代码实例1. egl_wayland_dmabuf_…...

【VTKExamples::PolyData】第二十八期 LinearExtrusion

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ:870202403 前言 本文分享VTK样例LinearExtrusion,并解析接口vtkLinearExtrusionFilter,希望对各位小伙伴有所帮助! 感谢各位小伙伴的点赞+关注,小易会继续努力分享,一起进步! 你的点赞就是我的动力(^U^)ノ~YO 目录…...

Linux操作系统基础(五):Linux的目录结构

文章目录 Linux的目录结构 一、Linux目录与Windows目录区别 二、常见目录介绍&#xff08;记住重点&#xff09; Linux的目录结构 一、Linux目录与Windows目录区别 Linux的目录结构是一个树型结构 Windows 系统 可以拥有多个盘符, 如 C盘、D盘、E盘 Linux 没有盘符 这个概…...

SolidWorks如何在一个零件的基础上绘制另一个零件

经过测试&#xff0c;新建零件&#xff0c;然后插入零件a&#xff0c;在a的基础上绘制b,这种做法无法断开a与b的联系。虽然可以通过切除命令&#xff0c;切除b&#xff0c;但不是正途。 在装配体中可以实现&#xff1a; &#xff08;1&#xff09;建立装配体 &#xff08;2&…...

gin(结)

gin day1 今天的目标就是学懂&#xff0c;看懂每一步代码。 gin框架 gin框架就是go语言的web框架。框架你也可以理解成一个库。里面有一堆封装好的工具&#xff0c;帮你实现各种各样的功能&#xff0c;这样使得你可以关注业务本身&#xff0c;而在写代码上少费力。 快速入门&…...

JavaScript 设计模式之桥接模式

桥接模式 通过桥接模式&#xff0c;我们可以将业务逻辑与元素的事件解耦&#xff0c;也可以更灵活的创建一些对象 倘若我们有如下代码 const dom document.getElementById(#test)// 鼠标移入移出事件 // 鼠标移入时改变背景色和字体颜色 dom.onmouseenter function() { th…...

B3651 [语言月赛202208] 数组调整

题目描述 给出一个长度为 n 的数组&#xff0c;第 i 个数为ai​。 为了调整这个数组&#xff0c;需要将第 k 个数改变为 −ak​。 请你求出调整后的数组中所有数的和。 输入格式 输入共两行。 输入的第一行为两个整数 n,k。 输入的第二行为 n 个整数&#xff0c;第 i 个…...

MessageQueue --- RabbitMQ

MessageQueue --- RabbitMQ RabbitMQ IntroRabbitMQ 核心概念RabbitMQ 分发类型Dead letter (死信)保证消息的可靠传递 RabbitMQ Intro 2007年发布&#xff0c;是一个在AMQP&#xff08;高级消息队列协议&#xff09;基础上完成的&#xff0c;可复用的企业消息系统&#xff0c;…...

WordPress作者页面链接的用户名自动变成16位字符串串插件Smart User Slug Hider

WordPress默认的作者页面URL链接地址格式为“你的域名/author/admin”&#xff0c;其中admin就是你的用户名&#xff0c;这样的话就会暴露我们的用户名。 为了解决这个问题&#xff0c;前面boke112百科跟大家分享了『如何将WordPress作者存档链接中的用户名改为昵称或ID』一文…...

Nvidia 携手 RTX 推出的本地运行 AI 聊天机器人

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

年假作业day2

1.打印字母图形 #include<stdio.h> #include<string.h> int main(int argc, const char *argv[]) { int i,j; char k; for(i1;i<7;i) { for(j1;j<i;j) { printf("%c",_); } for(j0,…...

HTML-多媒体嵌入-MDN文档学习笔记

HTML-多媒体与嵌入 查看更多学习笔记&#xff1a;GitHub&#xff1a;LoveEmiliaForever MDN中文官网 HTML-中的图片 将图片放入网页 可以使用<img/>来将图片嵌入网页&#xff0c;它是一个空元素&#xff0c;最少只需src属性即可工作 <img src"图片链接"…...

openJudge | 距离排序 C语言

总时间限制: 1000ms 内存限制: 65536kB 描述 给出三维空间中的n个点&#xff08;不超过10个&#xff09;,求出n个点两两之间的距离,并按距离由大到小依次输出两个点的坐标及它们之间的距离。 输入 输入包括两行&#xff0c;第一行包含一个整数n表示点的个数&#xff0c;第二…...

【教程】MySQL数据库学习笔记(三)——数据定义语言DDL(持续更新)

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【MySQL数据库学习】系列文章 第一章 《认识与环境搭建》 第二章 《数据类型》 第三章 《数据定义语言DDL》 文章目录 【MyS…...

[leetcode]买卖股票的最佳时机 (动态规划)

121. 买卖股票的最佳时机 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从…...

隐函数的求导【高数笔记】

1. 什么是隐函数&#xff1f; 2. 隐函数的做题步骤&#xff1f; 3. 隐函数中的复合函数求解法&#xff0c;与求导中复合函数求解法有什么不同&#xff1f; 4. 隐函数求导的过程中需要注意什么&#xff1f;...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

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

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

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...