首页 > 贪心：Jump Game 跳跃游戏

贪心：Jump Game 跳跃游戏

一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个 位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回是true或者false判断是否能够跳跃到结尾

例如:

nums = [2, 3, 1, 1, 4] ，可以从nums[0] = 2 跳跃至 nums[4] = 4;

nums = [3, 2, 1, 0, 4] ，不可以从nums[0] = 3 跳跃至 nums[4] = 4

  1. 贪心规律：

    想要判断最终是否能够跳跃到终点，最快的办法即选择每次跳跃获取到的跳跃范围中最大的跳跃点；

    比如：nums = [2 3 1 1 4]

    第一次跳 为2，那么接下来可以跳一次，跳到nums[1] = 3;或者跳跃2次，nums[2] = 1

    如何选择第二次跳呢，根据贪心算法，我们想要更快得完成任务，优先选择能够跳的次数最多的点，即nums[1]，因为它能够在第二次跳3次，但是nums[2]只能跳1次

    所以，贪心规律即为 每次跳跃的落点，为接下来可跳跃范围中最大的值；站在巨人的肩膀上可以跳得更远。

  2. 迭代策略：

    1. 求从第i位置最远可跳至第index[i]位置: 根据从第i位置最远可跳nums[i]步: index[i] = nums[i] + i;
    2. 初始化:

      1)设置变量jump代表当前所处的位置，初始化为0;

      2)设置变量max_index代表从第0位置至第jump位置这个过程中，最远可到达的位置，

      初始化为index[0]。
    3. 利用jump扫描index数组，直到jump达到index数组尾部或jump超过max_index，扫描过程中， 更新max_index。
    4. 若最终jump 为数组长度，则返回true，否则返回false。

实现算法如下:

bool judge_finish(vector<int> &stage) { vector<int> index;/*构造最远跳至的 index列表*/for (int i = 0; i < stage.size(); ++i) { index.push_back(i + stage[i]);}int max_index = stage[0];int jump = 0;/*筛选条件为要求为jump达到数组尾且 jump不能超过index数组，否则当前道路为不可达*/while(jump < index.size() && jump <= max_index) { if (max_index < index[jump]) { max_index = index[jump];}jump ++;}/*当 jump达到数组尾，即此时已经能够走完*/if (jump == index.size()) { return true;}return false;
}

测试代码如下:

#include 
#include 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 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 true or false that judge the result is " << judge_finish(s) << endl;return 0;
}

输出如下:

input arr 
3 2 2 0 5
the true or false that judge the result is 1

更多相关：

  • VS+Eigen+CUDA compile error: C2244 and MSB3721

    编译环境Eigen3+CUDA9.2+VS2015 错误如下： 解决方式： 将Eigen中的JacobiSVD and BDCSVD里的Index用Eigen::Index替换 http://eigen.tuxfamily.org/dox-devel/TopicCUDA.html http://eigen.tuxfami...

  • ipython --pandas

    d定义: pandas是一个强大的Python数据分析的工具包。 pandas是基于NumPy构建的。 安装方法: pip install pandas import pandas as pd pandas的主要功能 具备对其功能的数据结构DataFrame、Series 集成时间序列功能 提供丰富的数学运算和操作 灵活处理缺失数据...

  • .NET使用OpenSSL生成的pem密钥文件[1024位]

      using System; using System.Text; using System.Security.Cryptography; using System.Web; using System.IO;namespace Thinhunan.Cnblogs.Com.RSAUtility {public class PemCo...

  • oracle 无效索引

    错误信息：ORA-01502: index 'VOX_ID' or partition of such index is in unusable state 原因：将表的表空间做了更改，导致索引失效。表移动表空间，需要重建索引。 解决方法：alter index vox_id rebuild   问题查找： SQL> select i...

  • 让小球跳起来

    // If on the ground and jump is pressed... if (Physics.Raycast(transform.position, -Vector3.up, k_GroundRayLength) && jump) { // ... add force in upwards. m_Rigidbody....

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

©2024 11GX.COM