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

贪心算法-数组跳跃游戏(mid)

目录

一、问题描述

二、解题思路

1.回溯法

2.贪心算法

三、代码实现

1.回溯法实现

2.贪心算法实现

四、刷题链接


一、问题描述

二、解题思路

1.回溯法

        使用递归的方式,找到所有可能的走步方式,并记录递归深度(也就是走步次数),当走完数组时更新最小步长并返回。

        这种方式的缺点就是耗时很长,还容易产生栈溢出的问题

2.贪心算法

        直接通过画图来说明一下过程,找局部最优解扩展到全局最优解:

这里注意:当 i >=maxReach时,说明不能到达数组末尾,返回-1

这里可以用下面的示例按照上面的执行过程模拟一下,理解一下到达不了数组末尾是一个什么过程。

三、代码实现

1.回溯法实现

import java.util.*;public class Solution {int minstep=-1;/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int minJumpStep (int[] nums) {// 首先对常见的几种场景进行判断if(nums.length==0||(nums.length>1&&nums[0]==0)){return -1;}else if(nums.length==1){return 0;}//使用回溯法findMinStep(nums,0,0);return minstep;}//回溯法对所有可能的情况进行判断public void findMinStep(int[] nums,int nowIndex,int steps){if(nowIndex>=nums.length-1){if(minstep==-1){minstep=steps;}else{minstep=Math.min(minstep,steps);}return;}if(nums[nowIndex]==0){return;}else{for(int i=1;i<=nums[nowIndex];i++){findMinStep(nums,nowIndex+i,steps+1);} }}
}

2.贪心算法实现

import java.util.*;public class Solution {int minstep=-1;/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int minJumpStep (int[] nums) {// 首先对常见的几种场景进行判断if(nums.length==0||(nums.length>1&&nums[0]==0)){return -1;}else if(nums.length==1){return 0;}//使用贪心算法//定义变量://nowstep 记录当前走了多少步//current 记录nowstep可以走到的最远距离//maxReach 记录走到current后到下一次更新step之前可以到达的最远距离//初始时,步数为1,走一步以后所在位置nums[0],最远可到达nums[0]int nowstep=1,current=nums[0],maxReach=nums[0];for(int i=1;i<nums.length;i++){maxReach=Math.max(maxReach,i+nums[i]);if(i>=maxReach){return -1;}if(current>=nums.length-1){break;}if(i==current){nowstep++;current=maxReach;}}return nowstep;}}

四、刷题链接

跳跃游戏(三)_牛客题霸_牛客网

相关文章:

贪心算法-数组跳跃游戏(mid)

目录 一、问题描述 二、解题思路 1.回溯法 2.贪心算法 三、代码实现 1.回溯法实现 2.贪心算法实现 四、刷题链接 一、问题描述 二、解题思路 1.回溯法 使用递归的方式&#xff0c;找到所有可能的走步方式&#xff0c;并记录递归深度&#xff08;也就是走步次数&#x…...

C++经典150题

经典150题 数组/字符串 文章目录 经典150题数组/字符串88. 合并两个有序数组27.移除元素26.删除有序数组中的重复项80.删除有序数组重点重复项II169.多数元素189.轮转数组121.买卖股票的最佳时机123.买卖股票的最佳时机 III55.跳跃游戏45.跳跃游戏II 88. 合并两个有序数组 给…...

超详解——Python 序列详解——基础篇

目录 1. 序列的概念 字符串&#xff08;String&#xff09; 列表&#xff08;List&#xff09; 元组&#xff08;Tuple&#xff09; 2. 标准类型操作符 连接操作符&#xff08;&#xff09; 重复操作符&#xff08;*&#xff09; 索引操作符&#xff08;[]&#xff09; …...

DVWA-DC-6

靶机IP:192.168.20.140 kaliIP:192.168.20.128 网络有问题的可以看下搭建Vulnhub靶机网络问题(获取不到IP) 信息收集 nmap扫描靶机端口及版本信息 dirsearch扫目录 发现是个wordpress建站 我们去访问前端界面 存在重定向&#xff0c;修改hosts文件&#xff0c;加入192.168…...

ubuntu早期版本以及18.04后的版本,通过rc.local配置开机自启

在ubuntu早期版本以及18.04后的版本&#xff0c;还是支持在rc.local中进行操作开机自启。 1、编辑rc.local文件 cat <<EOF >/etc/rc.local #!/bin/sh -e # rc.local # This script is executed at the end of each multiuser runlevel. # Make sure that the script…...

【环境搭建】1.阿里云ECS服务器 安装jdk8

在阿里云服务器上安装 JDK 8 可以通过以下步骤完成。假设你使用的是 CentOS 或者其他基于 Red Hat 的发行版或Alibaba Cloud Linux 3.2104 LTS 64位。 1.更新系统软件包 sudo yum update -y2.安装 OpenJDK 8 使用 yum 包管理器安装 OpenJDK 8 sudo yum install -y java-1.8…...

idea插件开发之定义侧边栏

写在前面 看下如何在侧边栏定义窗口&#xff0c;如下的效果&#xff1a; 1&#xff1a;正戏 先来定义UI&#xff0c;随便拖拽个组件&#xff0c;就看个效果&#xff1a; 接着定义一个工厂类来创建这个UI&#xff0c;需要实现接口com.intellij.openapi.wm.ToolWindowFactor…...

HarmonyOS未来五年的市场展望

一、引言 随着科技的不断进步和消费者对于智能化设备需求的日益增长&#xff0c;操作系统作为连接硬件与软件的核心平台&#xff0c;其重要性愈发凸显。HarmonyOS&#xff08;鸿蒙系统&#xff09;&#xff0c;作为华为自主研发的分布式操作系统&#xff0c;自诞生以来便备受瞩…...

R语言:什么是向量化操作(Vectorization)?

在R语言中&#xff0c;向量化操作是一个非常重要且强大的概念。它不仅提高了代码的简洁性和可读性&#xff0c;还大大提升了代码的执行效率。本文将详细介绍什么是向量化操作&#xff0c;并通过几个示例来展示其应用。 什么是向量化操作&#xff1f; 向量化操作是指在不使用显…...

Python 机器学习 基础 之 【实战案例】中药数据分析项目实战

Python 机器学习 基础 之 【实战案例】中药数据分析项目实战 目录 Python 机器学习 基础 之 【实战案例】中药数据分析项目实战 一、简单介绍 二、中药数据分析项目实战 三、数据处理与分析实战 1、数据读取 2、中药材数据集的数据处理与分析 2.1数据清洗 2.2、 提取别…...

python中报错“ModuleNotFoundError: No module named ‘docx2txt‘”

python中from langchain_community.document_loaders import Docx2txtLoader报错“ModuleNotFoundError: No module named ‘docx2txt’” 问题描述: python中from langchain_community.document_loaders import Docx2txtLoader报错“ModuleNotFoundError: No module named ‘…...

json.dumps参数

json.dumps&#xff08;&#xff09;是 Python 中json 模块的一个函数&#xff0c;用于将 Python 对象编码成 JSON格式的字符串。这个函数有几个常用的参数&#xff0c;下面是一些主要的参数及其描述&#xff1a; 1. **obj**&#xff1a; 必需。要转换的 Python 对象。 2. *…...

未来已来,划时代革命性产品——全息数字人管家系统,全网首发

尊敬的投资人、亲爱的网友们&#xff1a; 大家好&#xff0c;我是数字人管家项目总设计师&#xff0c;我叫William wang。在这个科技日新月异的时代&#xff0c;我们正站在一个前所未有的交汇点上&#xff0c;数字与现实的边界日益模糊&#xff0c;智能技术正以前所未有的方式…...

psql导入数据报错排查

问题&#xff1a;采用pg_dump导出表数据后&#xff0c;用psql导入表数据&#xff0c;导入时报错 无效的命令 \N定位该问题的方法 --进入psql \set ON_ERROR_STOP on --退出psqlpsql -U postgres -d test -v ON_ERROR_STOPon < /home/postgres/test.dmp参考文章&#xff1a…...

项目:双人五子棋对战-对战模块(6)

完整代码见: 邹锦辉个人所有代码: 测试仓库 - Gitee.com 当玩家进入到游戏房间后, 就要开始一局紧张而又刺激的五子棋对战了, 本文将就前端后端的落子与判断胜负的部分作详细讲解. 模块详细讲解 约定前后端交互的接口 首先是建立连接后, 服务器需要生成一些游戏的初始信息(可…...

LeakSearch:针对网络公开凭证的安全扫描与检测工具

关于LeakSearch 在红队演戏过程中&#xff0c;往往需要获取到针对目标域的访问权限。在这个过程中&#xff0c;很多红队人员会选择使用暴露在互联网上的代理服务器来实现目标域的访问&#xff0c;那么此时就需要在互联网上收集公开暴露的凭证信息。 对于蓝队来说&#xff0c;…...

ArcoDesgin a-model中自定义样式model-class无效

增加黄框代码解决 原因是&#xff0c;动态加载的组件默认渲染在body下面&#xff0c;与#app平级。样式设置无效 加上:render-to-body“false”&#xff0c;让组件不渲染到body下&#xff0c;渲染在app下面&#xff0c;样式设置生效...

持续总结中!2024年面试必问 20 道分布式、微服务面试题(十)

上一篇地址&#xff1a;持续总结中&#xff01;2024年面试必问 20 道分布式、微服务面试题&#xff08;九&#xff09;-CSDN博客 十九、请描述一种微服务部署策略。 微服务部署策略是确保微服务架构中各个独立服务能够高效、稳定地部署到生产环境中的方法。以下是一些常见的微…...

北航第四次数据结构与程序设计编程题复习

到期末了&#xff0c;所以再来复习一下以前的作业。 北航第四次数据结构与程序设计编程题 一、栈操作&#xff08;栈-基本题&#xff09;二、C程序括号匹配检查三、计算器&#xff08;表达式计算-后缀表达式实现&#xff0c;结果为浮点&#xff09;四、文本编辑操作模拟&#…...

golang调用外部程序包os/exec中的 Command和CommandContext 函数创建的Cmd对象的区别

在go语言中&#xff0c;我们可以通过os/exec包中的Command和CommandContext 函数创建对应的外部程序执行Cmd对象&#xff0c; 这2个函数创建的cmd命令执行对象是有区别的&#xff0c;CommandContext创建的对象可以携带上下文&#xff0c;这个主要用于我们通过cancel函数给对应的…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

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

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

测试markdown--肇兴

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

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...