06贪心:跳跃游戏
06贪心:跳跃游戏
55. 跳跃游戏
刚看到本题一开始可能想:当前位置元素如果是 3,我究竟是跳一步呢,还是两步呢,还是三步呢,究竟跳几步才是最优呢?
其实跳几步无所谓,关键在于可跳的覆盖范围!
不一定非要明确一次究竟跳几步,每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围。
这个范围内,别管是怎么跳的,反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点!
每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。
贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
局部最优推出全局最优,找不出反例,试试贪心!
i 每次移动只能在 cover 的范围内移动,每移动一个元素,cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。
而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。
如果 cover 大于等于了终点下标,直接 return true 就可以了。
class Solution {public boolean canJump(int[] nums) {int cover = 0;//只关注能跳跃的最大范围,如果最大范围能包含到结尾,就可以跳到for(int i = 0; i <= cover; i++) {//用<=,因为我能跳到最大的范围cover = Math.max(cover, i + nums[i]);if(cover >= nums.length - 1) return true;}return false;}
}
总结
这道题目关键点在于:不用拘泥于每次究竟跳几步,而是看覆盖范围,覆盖范围内一定是可以跳过来的,不用管是怎么跳的。
可以看出思路想出来了,代码还是非常简单的。
感觉,贪心系列题目和题目之间貌似没有什么联系?
是真的就是没什么联系,因为贪心无套路!没有个整体的贪心框架解决一系列问题,只能是接触各种类型的题目锻炼自己的贪心思维!
相关文章:
06贪心:跳跃游戏
06贪心:跳跃游戏 55. 跳跃游戏 刚看到本题一开始可能想:当前位置元素如果是 3,我究竟是跳一步呢,还是两步呢,还是三步呢,究竟跳几步才是最优呢? 其实跳几步无所谓,关键在于可跳的…...
鄙视测试,理解测试,成为测试
首先,其实题主的问题还是很实诚的,我刚开始做测试的时候其实也是这个心态,想转开发,也学习了很多的语言,个人觉得这是职业危机感的表现,挺好的,也相信题主不管去做开发和测试都会去不断的学习和…...
MySQL数据库基础知识要点总结
目录 前言 一.数据库构成 1.1 表 1.2 关系 1.3 索引 1.4 查询语言 1.5 数据库管理系统 二.数据类型 2.1 整数 2.2 浮点 2.3 日期与时间 2.4 字符串 三.约束条件 3.1 主键约束 3.2 唯一约束 3.3 外键约束 3.4 非空约束 3.5 默认值约束 总结 前言 数据库是…...
基础运维(一)YUM仓库
一 自定义YUM仓库 1 Yum仓库特点 作为yum源需要准备的内容 大量的rpm 软件安装包文件针对这些软件包的 repodata/ 仓库档案 repodata/ 仓库档案数据 filelists.xml.gz // 软件包的文件安装清单primary.xml.gz // 软件包的基本/主要信息other.xml.gz // 软件包…...
递归算法讲解,深度理解递归
首先最重要的就是要说明递归思想的作用,在后面学习的高级数据接口,树和图中,都需要用到递归,即深度优先搜索,如果递归掌握的不好,后面的数据结构将举步为艰。 加油 首先看下如何下面两个方法有什么区别&a…...
网络通信(套接字通信)(C/C++)
1.网络编程必知概念 1.广域网和局域网 广域网:又称外网、公网。是连接不同地区局域网或城域网进行计算机通信的远程公共网络。 局域网:在一定的通信范围内,有很个多计算机组成的私有网络就叫局域网。(这些计算机相互之间是可以通信的,但是不能直接访问外网(可以通过网线…...
anaconda navigator启动时一直卡在 loading applications 页面
anaconda navigator启动时一直卡在 loading applications 页面 方法1 在安装目录找到D:\anaconda\Lib\site-packages\anaconda_navigator\api 然后打开conda_api.py, 在1358行找到data yaml.load(f),将其改为data yaml.safeload(f) 猜测为保证代码…...
力扣刷题-链表-删除链表的倒数第N个节点
19.删除链表的倒数第N个节点 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5] 示例 2:输入:head [1], n 1 输出&…...
Blender DreamUV插件使用简明教程
DreamUV 是一个可让你在Blender的 3D 视口中操纵 UV的工具集合。 该工具集设计用于可重复使用的纹理,例如平铺纹理、装饰表和纹理图集。 其目的是让你无需退出 3D 视图即可对几何体进行纹理处理,从而节省时间并提高灵活性。 1、安装DreamUV 首先下载为…...
AI在线工具分享
1、ChatGPT ChatGPT是一种由OpenAI训练的大型语言模型。它的原理是基于Transformer架构,通过预训练大量文本数据来学习如何生成人类可读的文本,然后通过接受输入并生成输出来实现对话。 ChatGPT的用途非常广泛,可以用于自然语言处理…...
Matlab批量处理测试数据的方法:以VCO的调谐测试曲线处理为例
我们都知道得到的VCO调谐曲线是一根一根扫出来的,如果要手动对数据进行处理很麻烦。 (当然最好是搭建一个自动化测试平台,一边测试一边把数据抓取了,这个以后可以搞一下再更新) 目前还是手动测量的情况下,…...
VScode断点调试vue
VScode断点调试vue 1、修改launch.js文件(没有这个文件就新建)。 {// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more information, visit: https://go.microsoft.com/fwlin…...
20吨屠宰鸡鸭鹅一体化污水处理设备加工厂家
20吨屠宰鸡鸭鹅一体化污水处理设备加工厂家 溶气气浮机主要构造说明 气浮系统气浮系统集进水、絮凝、分离、集水、出水于一体,与传统气浮设备类似,设有一个稳流室、溶气释放室,使处理性能更稳定,效果更优越。 稳定室:通…...
android被杀以后fragments缓存重建问题和测试方法
这个问题,其实不是太好复现。因为在android的缓存Fragment机制是写在androidx的库中。 主要的原因是android Framework机制: framework at yourpackage.onSaveInstanceState(XXXActivity.kt:118) at android.app.Activity.performSaveInstanceState(A…...
Visual Studio 2017 安装
C自学精简实践教程 目录(必读) 这篇文章会保证你第一次安装VS2017就成功运行Hello World! 下载Visual Studio Installer Gitee 下载 VS2017/vs2017_Community.exe CalmReason/VisualStudio - 码云 - 开源中国 (gitee.com) 百度云下载 链接:https://pan.baidu…...
day5|242.有效的字母异位词、349. 两个数组的交集
242.有效的字母异位词 题目链接:https://leetcode.cn/problems/valid-anagram/ 文章链接:https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html 视频链接:https://www.bilibili.…...
【Python基础】常用模块学习:sys|os|pytest
📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...
【煤矿虚拟仿真体验】VR采煤机技能培训有效提高训练效果
在我们的社会中,能源是至关重要的。它是推动我们日常生活和工作的主要动力。然而,我们在获取这种能源的过程中,也带来了许多环境问题。煤矿开采是其中的一个重要部分,因此我们需要寻找更环保、更安全的方式来进行煤矿开采。VR&…...
渲染路径RenderingPath
文章目录 前言一、什么是渲染路径二、渲染路径有哪些1、前向渲染路径2、延迟渲染路径3、顶点照明渲染路径(已过时)4、旧的渲染路径(已过时) 前言 渲染路径RenderingPath 一、什么是渲染路径 为进行光照计算而设计的渲染方式 二、渲染路径有哪些 1、前向…...
【Java】泛型 之 extends通配符
我们前面已经讲到了泛型的继承关系:Pair<Integer>不是Pair<Number>的子类。 假设我们定义了Pair<T>: public class Pair<T> { ... }然后,我们又针对Pair<Number>类型写了一个静态方法,它接收的参…...
Thanos.sh安全使用手册:避免数据灾难的10个终极技巧
Thanos.sh安全使用手册:避免数据灾难的10个终极技巧 【免费下载链接】Thanos.sh if you are Thanos(root), this command could delete half your files randomly 项目地址: https://gitcode.com/gh_mirrors/th/Thanos.sh Thanos.sh是一款以"随机删除一…...
基于SpringBoot + Vue的校园流浪动物救助平台
文章目录前言一、详细操作演示视频二、具体实现截图三、技术栈1.前端-Vue.js2.后端-SpringBoot3.数据库-MySQL4.系统架构-B/S四、系统测试1.系统测试概述2.系统功能测试3.系统测试结论五、项目代码参考六、数据库代码参考七、项目论文示例结语前言 💛博主介绍&#…...
NCM格式突破全攻略:从解密到跨平台播放的自由解锁方案
NCM格式突破全攻略:从解密到跨平台播放的自由解锁方案 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 音乐作为数字生活的重要组成部分,却常常受到格式限制的困扰。网易云音乐的NCM加密格式就是其中典型代表&…...
Vue2项目实战:集成西瓜播放器xgplayer实现企业级视频播放组件
1. 为什么选择xgplayer做企业级视频播放方案 在在线教育平台这类对视频播放要求较高的场景中,播放器的选择直接影响用户体验和开发效率。我经历过多个项目的实战验证,西瓜播放器xgplayer确实是个不错的选择。它不像某些开源播放器那样需要折腾各种兼容性…...
从理论到实践:拆解FOC滑模观测器中的三个关键增益(Gsmopos, Fsmopos, Hsmopos)
从理论到实践:拆解FOC滑模观测器中的三个关键增益(Gsmopos, Fsmopos, Hsmopos) 在永磁同步电机(PMSM)的磁场定向控制(FOC)系统中,滑模观测器(SMO)因其强鲁棒性…...
CLAP音频分类环境部署:Python3.8+PyTorch+Gradio一键配置指南
CLAP音频分类环境部署:Python3.8PyTorchGradio一键配置指南 想不想让电脑“听懂”声音?比如,上传一段音频,它就能告诉你这是狗叫、猫叫还是汽车鸣笛。这听起来像是科幻电影里的场景,但现在,借助一个叫CLAP…...
Android项目中的Gradle文件详解:从基础配置到高级技巧
Android项目中的Gradle文件详解:从基础配置到高级技巧 在Android开发的世界里,Gradle文件就像是一个项目的"大脑",它控制着构建过程的方方面面。对于有一定经验的Android开发者来说,深入理解Gradle文件的配置不仅能够提…...
千问3.5-2B集成IDEA开发环境:Java大模型应用快速构建指南
千问3.5-2B集成IDEA开发环境:Java大模型应用快速构建指南 1. 为什么要在IDEA中集成大模型? 作为Java开发者,我们经常需要在项目中处理各种文本处理任务。传统方式要么需要调用外部API(有网络延迟和费用问题)…...
MiniCPM-V-2_6 Ubuntu 20.04一键部署教程:从安装到运行
MiniCPM-V-2_6 Ubuntu 20.04一键部署教程:从安装到运行 想试试那个能看懂图片还能跟你聊天的多模态大模型MiniCPM-V-2_6吗?很多朋友在第一步——部署上就被卡住了,不是环境依赖搞不定,就是权限问题报错,折腾半天模型还…...
Java 26 FFM API进阶:零JNI调用TensorRT/OpenVINO,AI端到端延迟砍半
文章目录一、JNI,AI时代的"文言文写作"二、FFM API:Java调用原生代码的"现代白话文"1. Arena:比try-with-resources还狠的内存管理2. Linker:C函数的"Java身份证"3. jextract:头文件自动…...
