当前位置： 首页 > 编程日记 > 正文

贪心：jump 游戏（获取最少跳跃的次数以及跳跃路径）

编程日记 2024-04-21 02:30:00

一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个 位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回最少跳跃的次数以及跳跃过程的路径（以数组下标标识）

例如:
nums = [2, 3, 1, 1, 4] ，可以从nums[0] = 2 跳跃至 nums[4] = 4; 最少跳跃次数为2，跳跃路径为[0,1,4]

该跳跃过程和判断最终节点是否可达类似，不过需要注意一点：为了保证获取到的跳跃次数是最少的，需要在每一次的跳跃范围中尽可能得跳跃更多的节点，且在第一次跳跃结束后获取到后续所有节点的跳跃范围之后再进行下一次跳跃。

贪心规律：
在无法到达更远的地方时，在这之前应该跳到一个可以到达更 远位置的位置!

在这里插入图片描述
类似如上，在index[i]的节点上无法跳跃到更远的节点了，此时应该选择index[i-2]，使得其能够跳跃更远的节点。

同时如果想要获取跳跃的路径，即可将跳跃过程中发生的节点更替的时的下标记录下来，在跳跃的过程中加入到路径数组即可。

实现过程如下:

/*获取最少的跳跃次数*/
int get_judge_finish(vector<int> &stage) {if (stage.size() < 2) {return 0;}int current_max_pos = stage[0]; //当前能够跳跃到的最远的节点int pre_max_pos = stage[0];    //各个位置能够跳跃到的最远的节点int least_jum = 1;for (int i = 0;i < stage.size(); ++i) {if(i > current_max_pos) { //当遍历完当前节点当范围时进行跳跃，跳跃点选择各个位置能够跳跃当最远的点least_jum ++;current_max_pos = pre_max_pos;}if (pre_max_pos < stage[i] + i){ //获取各个位置能够跳跃到的最远的点pre_max_pos = stage[i] + i;}}return least_jum;
}/*获取最少的跳跃路径*/
vector<int> get_jump_path(vector<int> &stage) {if (stage.size() < 2) {return stage;}int current_max_pos = stage[0];int pre_max_pos = stage[0];int pre_max_index = 0; //记录各个位置能够跳的最远的节点下标vector<int> jump_path; //记录跳跃路径jump_path.push_back(0); //开头节点起跳for (int i = 0;i < stage.size(); ++i) {if(i > current_max_pos) {current_max_pos = pre_max_pos;/*当开始跳时，记录的各个位置能够跳的最远的下标*/jump_path.push_back(pre_max_index); }   if (pre_max_pos < stage[i] + i){pre_max_pos = stage[i] + i;pre_max_index = i;}}jump_path.push_back(stage.size()-1);return jump_path;
}

测试代码如下:

#include <iostream>
#include <vector>using namespace std;
/*判断是否能够完成跳跃*/
bool judge_finish(vector<int> &stage) {vector<int> index;for (int i = 0; i < stage.size(); ++i) {index.push_back(i + stage[i]);}int max_index = stage[0];int jump = 0;while(jump < index.size() && jump <= max_index) {if (max_index < index[jump]) {max_index = index[jump];}jump ++;}if (jump == index.size()) {return true;}return false;
}
/*获取最少的跳跃次数*/
int get_judge_finish(vector<int> &stage) {if (stage.size() < 2) {return 0;}int current_max_pos = stage[0];int pre_max_pos = stage[0];int least_jum = 1;for (int i = 0;i < stage.size(); ++i) {if(i > current_max_pos) {least_jum ++;current_max_pos = pre_max_pos;}if (pre_max_pos < stage[i] + i){pre_max_pos = stage[i] + i;}}return least_jum;
}
/*获取跳跃路径*/
vector<int> get_jump_path(vector<int> &stage) {if (stage.size() < 2) {return stage;}int current_max_pos = stage[0];int pre_max_pos = stage[0];int pre_max_index = 0;vector<int> jump_path;jump_path.push_back(0);for (int i = 0;i < stage.size(); ++i) {if(i > current_max_pos) {current_max_pos = pre_max_pos;jump_path.push_back(pre_max_index);}   if (pre_max_pos < stage[i] + i){pre_max_pos = stage[i] + i;pre_max_index = i;}}jump_path.push_back(stage.size()-1);return jump_path;
}int main() {vector<int> s;int tmp;cout << "input arr " <<endl;for (int i =0;i < 5; ++i) {cin >> tmp;s.push_back(tmp);}cout << "the least times to jump is " << get_judge_finish(s) << endl;cout << "the true or false that judge the result is " << judge_finish(s) << endl;cout << "jump path is " << endl;vector<int> path = get_jump_path(s);for (int i = 0;i < path.size(); ++i) {cout << path[i] << " ";}return 0;
}

输出如下:

input arr 
3 2 2 0 5
the least times to jump is 2
the true or false that judge the result is 1
jump path is 
0 2 4input arr 
2 3 1 1 4
the least times to jump is 2
the true or false that judge the result is 1
jump path is 
0 1 4

https://www.dkcj.cn/info/4991.html

相关文章：

ADO.NET事务

在发布System.Transaction命名空间之前&#xff0c;可以直接用ADO.NET创建事务&#xff0c;也可以通过组件、特性和COM运行库&#xff08;位于System.EnterpriseServices命名空间中&#xff09;进行事务处理。本文如题所示&#xff0c;介绍在这些传统事务处理方式中较为简单的“…

编程日记2024/04/21 02:00:00

oracle表中怎么去重复,oracle去掉表重复数据

今天在做项目过程中&#xff0c;碰到数据库表存在重复记录&#xff0c;显示的时候需要去掉重复的数据。想了老半天&#xff0c;最终用rank() over (partition by 分组字段 order by 排序字段 顺序)解决了此问题。一、首先介绍下rank() over (partition by 分组字段 order by 排…

编程日记2024/04/21 01:30:00

JavaIO操作(1)字节流和字符流-1

3.2、字节流和字符流&#xff08;核心&#xff09; 使用File类执行的所有操作都是针对于文件本身&#xff0c;但是却没有针对于文件的内容&#xff0c;而要进行文件内容操作就需要通过Java之中提供的两组类完成&#xff1a; 字节操作流&#xff08;是在JDK 1.0的时候定义的&am…

编程日记2024/04/21 01:00:00

7min到40s：SpringBoot 启动优化实践

然后重点排查这些阶段的代码。先看下。

编程日记2024/04/21 00:30:05

SpringBoot系列教程之Bean之指定初始化顺序的若干姿势

之前介绍了@Order注解的常见错误理解，它并不能指定 bean 的加载顺序，那么问题来了，如果我需要指定 bean 的加载顺序，那应该怎么办呢？本文将介绍几种可行的方式来控制 bean 之间的加载顺序。

编程日记2024/04/21 00:30:05

在Java中使用WebSocket

WebSocket是一种协议，用于在Web应用程序和服务器之间建立实时、双向的通信连接。它通过一个单一的TCP连接提供了持久化连接，这使得Web应用程序可以更加实时地传递数据。WebSocket协议最初由W3C开发，并于2011年成为标准。

编程日记2024/04/21 00:30:05

3种方案，模拟两个线程抢票

在多线程编程中，资源竞争是一个常见的问题。资源竞争发生在多个线程试图同时访问或修改共享资源时，可能导致数据不一致或其他并发问题。在模拟两个线程抢票的场景中，我们需要考虑如何公平地分配票，并确保每个线程都有机会成功获取票。本篇文章将通过三种方式来模拟两个线程抢票的过程，以展示不同的并发控制策略。使用 Synchronized 来确保一次只有一个线程可以访问票资源。使用 ReentrantLock 来实现线程间的协调。使用 Semaphore 来限制同时访问票的线程数量。

编程日记2024/04/21 00:30:05

初级七 委托与事件

1.委托是一种类型&#xff0c;定义委托后想要实现他需要实例化&#xff0c;而事件其实就是委托的一个实例&#xff0c;加了event修饰&#xff1b; 委托实例化可以在 2.委托的作用&#xff1a;可以作为函数的参数传递&#xff1b; 无委托无异步&#xff1b; 委托主要是用来解耦 …

编程日记2024/04/21 00:30:00

r-route 命令 显示/配置ip路由表

文章目录前言语法格式命令使用输出含义使用实例前言 route命令用于显示和配置IP路由表&#xff0c;在不同节点间的网络通信&#xff0c;想要实现同一局域网之间的通信就需要交换机&#xff0c;不同局域网之间的通信就需要路由器。而路由器的存在是为了提供NAT转换&#xff0c;…

编程日记2024/04/21 00:00:00

suse oracle 12c安装,用半行代码实现在LINUX(SUSE/RH)下安装ORACLE 12C

最近新到单位的朋友总是抱怨在LINUX下安装ORACLE&#xff0c;实在是太麻烦了&#xff0c;而且这些步骤既不知是什么意思&#xff0c;也记不住&#xff1b;索性&#xff0c;我就分析了一下&#xff0c;经过实践&#xff0c;实现了只用半行代码(确切的说&#xff0c;只消4个字母)…

编程日记2024/04/20 23:30:00

shell--数组的定义/访问/赋值/遍历

1 #!/bin/bash2 # 数组3 4 # 数组的定义5 a(0 1 2 3)6 # 数组元素的访问7 echo "a[0]:${a[0]}"8 # 数组的长度9 echo "length:${#a[*]}" 10 # 所有元素 11 echo "all element:${a[*]}" 12 # 删除某个元素 13 unset a[1] 14 echo "after uns…

编程日记2024/04/20 23:00:00

四百元值不值——论小米2A与2S

作为一个米2用户&#xff0c;面对这手机市场极快的更新速度&#xff0c;有些跟不上速度。最近出了小米2A与2S&#xff0c;碰巧有人问值不值的问题&#xff0c;于是就小小的进行了一个研究&#xff0c;跟大家讨论一下。首先小米2A与2S在我看来就是2的翻版&#xff0c;现在小米的…

编程日记2024/04/20 22:30:00

python复习冒泡排序

冒泡排序&#xff1a; 思路&#xff1a; 先找到最大值放到最右边&#xff1a; #encodingutf-8 a[1,9,2,8,3,6,4] print "a before change:",a for i in range(len(a)-1): if a[i] > a[i1]: a[i],a[i1] a[i1],a[i] print "a after change:",a 结果&…

编程日记2024/04/20 22:00:00

linux 文件查找命令集:find,locate,wheres,which,type

文章目录前言find命令命令格式&#xff1a;常用选项&#xff1a;举例使用locate命令命令格式使用实例whereis命令使用过程:which命令type命令前言 在linux系统中一切皆文件&#xff0c;此时我们想要从海量的文件中快速定位中我们想要的文件来&#xff0c;需要指定的命令来操作…

编程日记2024/04/20 21:30:00

oracle生成xml方法,oracle存储过程生成xml==转

1.创建如下存储过程&#xff0c;注意将其中location >d:\work之中的目录改为你本机的某个目录.create or replace procedure getXML(newContext_qry varchar2,rowSettag varchar2,rowTag varchar2,filename varchar2) is-- Input query string-- Input rowsetTag , the root…

编程日记2024/04/20 21:00:00

打算看的书或正在看的书

打算看的书或正在看的书 《Data Structures and Algorithm Analysis in C》 正在看&#xff0c;这本书是在博客园上看到某个去google的大牛推荐的&#xff0c;的确&#xff0c;虽然数据结构&#xff0c;我已经很熟悉了&#xff0c;但是看这本书的时候&#xff0c;有一些细节我是…

编程日记2024/04/20 20:30:00

Tutorial——使用Maven开发Cloud Driver

2019独角兽企业重金招聘Python工程师标准>>> Before You Start 开发之前&#xff0c;应有以下准备 Apache MavenCloudify调用云API的安全凭证&#xff0c;使用SSH访问你的机器&#xff0c;如果需要访问您的云的存储。 例如&#xff0c;通过以下步骤获得OpenStack的安…

编程日记2024/04/20 20:00:00

[Machine Learning with Python] Data Visualization by Matplotlib Library

Before you can plot anything, you need to specify which backend Matplotlib should use. The simplest option is to use Jupyter’s magic command %matplotlib inline. This tells Jupyter to set up Matplotlib so it uses Jupyter’s own backend. Scatter Plot housin…

编程日记2024/04/20 19:30:00

贪心：Burst Balloons 最少次数完成射击气球

已知在一个平面上有一定数量的气球&#xff0c;平面可以看作一个坐标系&#xff0c;在平面的x轴的不同位 置安排弓箭手向y轴方向射箭&#xff0c;弓箭可以向y轴走无穷远;给定气球的宽度 xstart ≤ x ≤ xend&#xff0c;问至少需要多少弓箭手&#xff0c;将全部气球打爆? 例如…

编程日记2024/04/20 19:00:00

linux服务器加固的命令,Linux 服务器安全加固

一、summary随着互联网的发展&#xff0c;隐私以及安全被大家看的越来越重视&#xff0c;越来越多的重要交易正在通过网络完成&#xff0c;与此同时数据被损坏、截取和修改的风险也在增加。优秀的系统应当拥有完善的安全措施&#xff0c;应当足够坚固、能够抵抗来自Internet的侵…

编程日记2024/04/20 18:30:00

devexpress toolbar 填充整行宽度

设置 bar 的 optionsBar.UseWholeRow True 然后可设置Bar 中 Item的右对齐属性。转载于:https://www.cnblogs.com/perpetual/p/3756101.html

编程日记2024/04/20 18:00:00

【java】staitc

一、static变量 二、static方法 三、static代码块 四、static类&#xff1a;只能是内部类

编程日记2024/04/20 17:30:00

002.Docker安装部署

一 docker安装-CentOS系统1.1 docker自动安装脚本 1 rootdocker:~# wget -qO- https://get.docker.com/ | sh2 或——3 rootdocker:~# curl -sSL https://get.docker.com/ | sh 注意&#xff1a;若出现以下错误&#xff0c;可使用yum解决依赖——Delta RPMs disabled because /…

编程日记2024/04/20 17:00:00

贪心：expedition 最优加油方法

已知一条公路上&#xff0c;有一个起点与一个终点&#xff0c;这之间有n个加油站;已知从这n个加 油站到终点的距离d与各个加油站可以加油的量l&#xff0c;起点位置至终点的距离L与起 始时刻油箱中汽油量P;假设使用1个单位的汽油即走1个单位的距离&#xff0c;油箱没有 上限&am…

编程日记2024/04/20 16:30:00

UML for Java Programmers之dx实战

dx是一套简单的开发规则。它说白了就是迭代开发&#xff0c;在短周期内迭代处理”所有事情“&#xff0c;这里所指的”所有事情“包括需求、分析、设计、实现、测试和文档等等。 它的大概流程是这样&#xff1a;1. 初始探索 跟客户坐下来一起讨论系统到底是做什么的。在这个…

编程日记2024/04/20 16:00:00

linux进程池动态维护,可直接商用的跨平台c,c++动态线程池,任务池stpool库

stpool是一个轻便高效的动态跨平台的线程池/任务池库.常规线程池的缺点&#xff1a;1. 总是启动时候就开启固定数目的线程,而不管系统的繁忙状态(这是很浪费系统资源的).2. 当任务繁重的时候&#xff0c;即使线程池被设计成可继续添加更多线程来服务&#xff0c;由于实时服务状…

编程日记2024/04/20 15:30:00

hdu 1286( 欧拉函数 ）

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid1286 数学题真的是有点吃不消了。。。 View Code 1 #include<iostream>2 #include<cmath>3 using namespace std;4 //可以快速求出欧拉函数的值 ( P为N的质因子 )5 //若(N%P0 && (N/P)%P0…

编程日记2024/04/20 15:00:00

CF 1093 E. Intersection of Permutations

E. Intersection of Permutations 链接 题意&#xff1a; 给定两个序列&#xff0c;询问第一个排列的[l1,r1]和第二个排列[l2,r2]中有多少个共同的数&#xff0c;支持在第二个排列中交换两个数。 分析&#xff1a; 首先求出一个数组&#xff0c;c[i]&#xff0c;第二个排列的这…

编程日记2024/04/20 14:30:00

s-seq 生成序列化数字

前言 seq命令用于产生从某个数到另外一个数之间的所有整数。 命令格式 seq [OPTION]... LAST seq [OPTION]... FIRST LAST seq [OPTION]... FIRST INCREMENT LAST 支持将指定范围的数字打印出来&#xff0c;按照指定的递增规律 -f, --format格式 使用printf 样式的浮点格式…

编程日记2024/04/20 14:00:00

linux c++ 目录操作,C++文件及文件夹操作整理（代码示例）

一 文件1.1 使用C标准库中的IO库(fstream)读写文件#include #include using namespace std;int main(){char szData[200] "123456 test";fstream fFile;fFile.open("test.txt", ios::app | ios::out | ios::in);/****************将数据写入文件-begin***…

编程日记2024/04/20 13:30:00