贪心算法|45.跳跃游戏II

力扣题目链接

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标(相当于加油了)
                if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点,不用做ans++操作了,直接结束
            }
        }
        return ans;
    }
};

这题难了一点,它求的是步数

思路

本题相对于55.跳跃游戏 (opens new window)还是难了不少。

但思路是相似的,还是要看最大覆盖范围。

本题要计算最少步数,那么就要想清楚什么时候步数才一定要加一呢?

贪心的思路,局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一。整体最优:一步尽可能多走,从而达到最少步数。

思路虽然是这样,但在写代码的时候还不能真的能跳多远就跳多远,那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候,要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数!

这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖

如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点。

如图:

45.跳跃游戏II

图中覆盖范围的意义在于,只要红色的区域,最多两步一定可以到!(不用管具体怎么跳,反正一定可以跳到)

#方法一

从图中可以看出来,就是移动下标达到了当前覆盖的最远距离下标时,步数就要加一,来增加覆盖距离。最后的步数就是最少步数。

这里还是有个特殊情况需要考虑,当移动下标达到了当前覆盖的最远距离下标时

  • 如果当前覆盖最远距离下标不是是集合终点,步数就加一,还需要继续走。
  • 如果当前覆盖最远距离下标就是是集合终点,步数不用加一,因为不能再往后走了。

自己的思路

本题的关键是求步数ans

 if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标(相当于加油了)
                if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点,不用做ans++操作了,直接结束
            }

这一步不太好理解

 不过代码还是好记的。

这题需要明天再复习一下,自己独立敲出!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

qt-C++笔记之QLabel加载图片

qt-C笔记之QLabel加载图片 —— 2024-04-06 夜 code review! 文章目录 qt-C笔记之QLabel加载图片0.文件结构1.方法一&#xff1a;把图片放在项目路径下&#xff0c;在 .pro 文件中使用 DISTFILES添加图片文件1.1.运行1.2.qt_test.pro1.3.main.cpp 2.方法二&#xff1a;不在 .pr…

深入浅出 -- 系统架构之分布式集群的分类

一、单点故障问题 集群&#xff0c;相信诸位对这个概念并不陌生&#xff0c;集群已成为现时代中&#xff0c;保证服务高可用不可或缺的一种手段。 回想起初集中式部署的单体应用&#xff0c;因为只有一个节点&#xff0c;因此当该节点出现任意类型的故障&#xff08;网络、硬件…

go | 上传文件分析 | http协议分析 | 使用openssl 实现 https 协议 server.key、server.pem

是这样的&#xff0c;现在分析抓包数据 test.go package mainimport ("fmt""log""github.com/gin-gonic/gin" )func main() {r : gin.Default()// Upload single filer.MaxMultipartMemory 8 << 20r.POST("/upload", func(c *g…

【单片机】心率传感器,串口发送,MAX30102心率传感器模块

数值还是稳定的&#xff0c;但太贵了&#xff0c;stm32单片机的话&#xff0c;直接用这篇博客&#xff08;https://qq742971636.blog.csdn.net/article/details/137359381&#xff09;的代码&#xff0c;一样稳定。 解析这个模块的数据 char rev_max30102_bufferdata[30]; cha…

Flutter学习12 - SharedPreferences

1、shared_preferences 插件 类似于 Android 中的 SharedPreferences&#xff0c;键值对的形式进行本地存储 1.1、引入插件 在 pubspec.yaml 中引入 dependencies:shared_preferences: ^2.1.0在需要用到的文件中引入 import package:shared_preferences/shared_preference…

安全的通信协议HTTPS被攻击改采用什么防护方案

随着互联网的发展&#xff0c;保护用户在网上交换的敏感信息的安全性变得至关重要。HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;作为一种安全的通信协议&#xff0c;通过加密数据传输&#xff0c;保护用户的隐私和数据安全。然而&#xff0c;尽管HTTPS提…

Ubuntu部署LangChain-Chatchat

个人博客&#xff1a;https://blog.lukeewin.top 更多内容欢迎访问我的博客。 一、环境 OS: Ubuntu 20.04 PyTorch: 2.0.0 Python: 3.8 CUDA: 11.8 GPU: RTX 4090 24GB CPU: 12 vCPU Intel(R) Xeon(R) Platinum 8352V CPU 2.10GHz RAM: 90GB 硬盘: 180GB LLM: Chatglm3-6b E…

ubuntu20.04.6安装sshd服务,并连接到远程服务器

文章目录 sshd 是 OpenSSH 服务器的守护进程OpenSSH下载在 Ubuntu 上&#xff0c;可以按照以下步骤来管理 sshd 服务 防火墙开启22端口使用Mobaxterm链接服务器 sshd 是 OpenSSH 服务器的守护进程 它负责提供远程登录和安全的 shell 服务。通过启动 sshd 服务&#xff0c;可以…

小米汽车su7全色系展示源码

源码简介 小米汽车全色系展示源码&#xff0c;小米汽车su7全色系展示源码 安装教程 纯HTML&#xff0c;直接将压缩包上传网站目录解压即可 首页截图 源码下载 小米汽车su7全色系展示源码-小8源码屋源码简介 小米汽车全色系展示源码&#xff0c;小米汽车su7全色系展示源码 …

015——步进电机模块驱动开发(基于I.MX6uLL、MX-1502和28BYJ-48)

目录 一、电机驱动模块介绍 1.1 特性 1.2 应用范围 1.3 概述 1.4 电气属性 1.5 经典应用线路 二、电机介绍&#xff08;本节内容来自韦东山老师课程资料&#xff09; 三、 代码编写思路 四、 驱动程序 五、应用程序 一、电机驱动模块介绍 1.1 特性  低待机电流 (…

lua学习笔记6(经典问题输出99乘法表)

print("************for循环的99乘法表*************") for i 1, 9 dolocal line "" -- 创建一个局部变量来累积每行的输出--local 是一个关键字&#xff0c;用于声明一个局部变量。for j 1, i doline line .. j .. "*" .. i .. ""…

基于YOLOv8的铁路工人安全作业检测系统

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文摘要&#xff1a;基于YOLOv8的铁路工人安全作业检测系统&#xff0c;属于小目标检测范畴&#xff0c;并阐述了整个数据制作和训练可视化过程&#xff0c; 博主简介 AI小怪兽&#xff0c;YOLO骨灰级玩家&#xff0c;1&#xff0…

考研高数(平面图形的面积,旋转体的体积)

1.平面图形的面积 纠正&#xff1a;参数方程求面积 2.旋转体的体积&#xff08;做题时&#xff0c;若以x为自变量不好计算&#xff0c;可以求反函数&#xff0c;y为自变量进行计算&#xff09;

深入浅出 -- 系统架构之分布式多形态的存储型集群

一、多形态的存储型集群 在上阶段&#xff0c;我们简单聊了下集群的基本知识&#xff0c;以及快速过了一下逻辑处理型集群的内容&#xff0c;下面重点来看看存储型集群&#xff0c;毕竟这块才是重头戏&#xff0c;集群的形态在其中有着多种多样的变化。 逻辑处理型的应用&…

Docker容器与虚拟化技术:OpenEuler 部署 Prometheus 与 Grafana

目录 一、实验 1.环境 2.OpenEuler 部署 Prometheus 3.OpenEuler 部署 Grafana 4.使用cpolar内网穿透 二、问题 1.拉取镜像失败 2.如何导入Grafana监控模板&#xff08;ES&#xff09; 一、实验 1.环境 &#xff08;1&#xff09;主机 表1 主机 系统架构版本IP备注…

【简单讲解下epoll】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

ELK报错,索引变成只读状态。

问题描述 今天发现当天的索引在ES中并没有创建&#xff0c;logstash中不停的报错&#xff1a; [2021-05-24T05:47:51,904][INFO ][logstash.outputs.elasticsearch] retrying failed action with response code: 403 ({“type”>“cluster_block_exception”, “reason”&g…

c++算法学习笔记 (20) 哈希表

1.模拟散列表 // 拉链法 #include <bits/stdc.h> using namespace std; const int N 100003; int h[N]; int e[N], ne[N], idx; // 存链void insert(int x) {int k (x % N N) % N; // 让负数的余数变成正数(若直接加N,则可能溢出)e[idx] x;ne[idx] h[k];h[k] idx;…

29岁东张女神凭索爆身材演活情妇角色。

正在热播的《逆天奇案2》&#xff0c;云集陈展鹏、林夏薇、冯盈盈、黄智贤、蒋祖曼、多位老戏骨&#xff0c;亦有不少新力军。日前一集展开新单元「龙头棍风暴」&#xff0c;饰演林景程情妇的王嘉慧&#xff08;Cathy&#xff09;&#xff0c;与平日「东张女神」形象反差极大。…

记录重装ubuntu系统

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言无法进入ubuntu图形化界面进入ubuntu的tty模式开始解决误打误撞进入X-Window界面&#xff0c;拷贝ubuntu系统文件重装ubuntu系统 前言 提示&#xff1a;这里可…