当前位置: 首页 > 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函数给对应的…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

电脑桌面太单调,用Python写一个桌面小宠物应用。

下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡&#xff0c;可以响应鼠标点击&#xff0c;并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...