贪心算法-数组跳跃游戏(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;}}

四、刷题链接

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/346767.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【AI法官】人工智能判官在线判案?

概述 AI法官是一款为用户提供专业法律分析和判决建议的智能体应用。用户只需简要描述案情&#xff0c;AI法官便会利用其强大的法律知识和逻辑推理能力&#xff0c;快速且准确地梳理出判决结果。该应用的目标是为用户提供高效、准确、合法的判决建议。 角色任务 任务描述 作为…

小程序 UI 风格魅力非凡

小程序 UI 风格魅力非凡

Oracle的优化器

sql优化第一步&#xff1a;搞懂Oracle中的SQL的执行过程 从图中我们可以看出SQL语句在Oracle中经历了以下的几个步骤&#xff1a; 语法检查&#xff1a;检查SQL拼写是否正确&#xff0c;如果不正确&#xff0c;Oracle会报语法错误。 语义检查&#xff1a;检查SQL中的访问对象…

海南聚广众达电子商务咨询有限公司打造一站式电商服务

在数字经济的浪潮中&#xff0c;电商行业蓬勃发展&#xff0c;各种平台和服务商如雨后春笋般涌现。其中&#xff0c;海南聚广众达电子商务咨询有限公司凭借其专业的团队和丰富的经验&#xff0c;在抖音电商服务领域独树一帜&#xff0c;成为业界的佼佼者。 海南聚广众达电子商…

判断对称树

leetcode - 101 - 对称二叉树 给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#xff1a;false提示&a…

注册小程序

每个小程序都需要在 app.js 中调用 App 方法注册小程序实例&#xff0c;绑定生命周期回调函数、错误监听和页面不存在监听函数等。 详细的参数含义和使用请参考 App 参考文档 。 整个小程序只有一个 App 实例&#xff0c;是全部页面共享的。开发者可以通过 getApp 方法获取到全…

【递归、搜索与回溯】穷举vs暴搜vs深搜vs回溯vs剪枝

穷举vs暴搜vs深搜vs回溯vs剪枝 1.全排列2.子集 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 管他什么深搜、回溯还是剪枝&#xff0c;画出决…

【Java】解决Java报错:NoClassDefFoundError

文章目录 引言1. 错误详解2. 常见的出错场景2.1 类路径配置错误2.2 依赖库缺失2.3 类文件被删除或损坏2.4 类加载器问题 3. 解决方案3.1 检查类路径配置3.2 检查依赖库3.3 检查类文件3.4 调试类加载器问题 4. 预防措施4.1 使用构建工具管理依赖4.2 定期进行构建和测试4.3 使用I…

【Unity+AI01】在Unity中调用DeepSeek大模型!实现AI对话功能!

要在Unity中调用DeepSeek的API并实现用户输入文本后返回对话的功能&#xff0c;你需要遵循以下步骤&#xff1a; 获取API密钥&#xff1a; 首先&#xff0c;你需要从DeepSeek获取API密钥。这通常涉及到注册账户&#xff0c;并可能需要订阅相应的服务。 集成HTTP请求库&#xf…

【APP移动端自动化测试】第一节.环境配置和adb调试工具

文章目录 前言一、Java环境搭建二、AndroidSDK环境搭建三、Android模拟器安装四、adb调试工具基本介绍 4.1 adb构成和基本原理 4.2 adb获取包名&#xff0c;界面名 4.3 adb文件传输 4.4 adb获取app启动时间 4.5 adb获取手机日志 4.6 adb其他有关…

python的resample()函数

介绍 在Python中,resample()函数是一个常用的工具,用于对时间序列数据进行重新采样。这个函数可以将时间序列数据从一个频率转换为另一个频率,比如将每天的数据转换为每月的数据。在本教程中,我将向你展示如何使用resample()函数,并解释每个步骤的具体含义。 整体流程 首先…

独具魅力的 App UI 风格才能称之为优秀

独具特色的App UI 长什么样&#xff01;看这里

Java案例:找素数

文章目录 题目问题反思代码改进 题目 找素数 判断101-200之间有多少个素数&#xff0c;并输出所有素数 只需要除到 n/2 即可。 算数平方根。&#xff08;j*j<i&#xff09;实际上可以更高效地只除到Math.sqrt(n)&#xff08;或者说Math.sqrt(n) 1为了处理整数除法&#xf…

Master-Worker 架构的灰度发布难题

作者&#xff1a;石超 一、前言 Master-Worker 架构是成熟的分布式系统设计模式&#xff0c;具有集中控制、资源利用率高、容错简单等优点。我们数据中心内的几乎所有分布式系统都采用了这样的架构。 &#xfeff; 我们曾经发生过级联故障&#xff0c;造成了整个集群范围的服…

文件IOoooo

1.1 文件路径 文件路径分为两种&#xff1a; 1、绝对路径&#xff1a;以C:、D:等盘符开头的&#xff0c;就是我们所说的绝对路径&#xff0c;根据它可以直接找到文件的具体位置。 2、相对路径&#xff1a;需要先指定一个目录作为基准目录&#xff0c;从基准目录出发&#xf…

SpringSecurity入门(四)

18、权限管理/授权 18.1、针对url配置 配置SecurityConfig package com.wanqi.config;import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.security.config.annotation.web.bu…

(免费领源码)基于 node.js#vue#mysql的网上游戏商城35112-计算机毕业设计项目选题推荐

摘 要 本论文主要论述了如何使用node.js语言开发一个基于vue的网上游戏商城&#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;本系统采用的数据库是Mysql&#xff0c;使用node.js的koa技术技术构建的一个管理系统&#xff0c;实现了本系统的全部功能。在…

云计算-期末复习题-选择/判断/填空/简答(1)

目录 填空题/简答题 单选题 多选题 判断题 云计算期末复习部分练习题&#xff0c;下一章会补全。祝大家好好复习&#xff0c;顺利通过课程。 填空题/简答题 >保障云基本安全的对策包括&#xff08;&#xff09;、&#xff08;&#xff09;和&#xff08;&#xff09; &…

Linux:桌面系统中的文件后缀和类型

相关阅读 Linuxhttps://blog.csdn.net/weixin_45791458/category_12234591.html?spm1001.2014.3001.5482 Linux中的文件后缀与Windows系统有些不同&#xff0c;因为其似乎没有很重要&#xff0c;一个文件是否可执行对后缀没有要求。但是&#xff0c;后缀依然可以用于表示文件…

机器学习笔记:label smoothing

在传统的分类任务中&#xff0c;我们通常使用硬标签&#xff08;hard labels&#xff09; 即如果一个样本属于某个类别&#xff0c;其对应的标签就是一个全0的向量&#xff0c;除了表示这个类别的位置为1。例如&#xff0c;在一个3类分类任务中&#xff0c;某个样本的标签可能是…