C++实现LeetCode(55.跳跃游戏)

[LeetCode] 55. Jump Game 跳跃游戏

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

这道题说的是有一个非负整数的数组，每个数字表示在当前位置的最大跳力（这里的跳力指的是在当前位置为基础上能到达的最远位置），求判断能不能到达最后一个位置，开始博主以为是必须刚好到达最后一个位置，超过了不算，其实是理解题意有误，因为每个位置上的数字表示的是最大的跳力而不是像玩大富翁一样摇骰子摇出几一定要走几。这里可以用动态规划 Dynamic Programming 来解，维护一个一维数组 dp，其中 dp[i] 表示达到i位置时剩余的跳力，若到达某个位置时跳力为负了，说明无法到达该位置。接下来难点就是推导状态转移方程啦，想想啊，到达当前位置的剩余跳力跟什么有关呢，其实是跟上一个位置的剩余跳力（dp 值）和上一个位置新的跳力（nums 数组中的值）有关，这里新的跳力就是原数组中每个位置的数字，因为其代表了以当前位置为起点能到达的最远位置。所以当前位置的剩余跳力（dp 值）和当前位置新的跳力中的较大那个数决定了当前能到的最远距离，而下一个位置的剩余跳力（dp 值）就等于当前的这个较大值减去1，因为需要花一个跳力到达下一个位置，所以就有状态转移方程了：dp[i] = max(dp[i - 1], nums[i - 1]) - 1，如果当某一个时刻 dp 数组的值为负了，说明无法抵达当前位置，则直接返回 false，最后循环结束后直接返回 true  即可，参见代码如下：

解法一：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
            if (dp[i] < 0) return false;
        }
        return true;
    }
};

其实这题最好的解法不是 DP，而是贪婪算法 Greedy Algorithm，因为这里并不是很关心每一个位置上的剩余步数，而只希望知道能否到达末尾，也就是说我们只对最远能到达的位置感兴趣，所以维护一个变量 reach，表示最远能到达的位置，初始化为0。遍历数组中每一个数字，如果当前坐标大于 reach 或者 reach 已经抵达最后一个位置则跳出循环，否则就更新 reach 的值为其和 i + nums[i] 中的较大值，其中 i + nums[i] 表示当前位置能到达的最大位置，参见代码如下：

解法二：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size(), reach = 0;
        for (int i = 0; i < n; ++i) {
            if (i > reach || reach >= n - 1) break;
            reach = max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }
};

到此这篇关于C++实现LeetCode(55.跳跃游戏)的文章就介绍到这了,更多相关C++实现跳跃游戏内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(45.跳跃游戏之二)

    [LeetCode] 45. Jump Game II 跳跃游戏之二 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last i

  • C++实现LeetCode(769.可排序的最大块数)

    [LeetCode] 769.Max Chunks To Make Sorted 可排序的最大块数 Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them,

  • C++实现LeetCode(42.收集雨水)

    C++实现LeetCode(42.收集雨水)

    [LeetCode] 42. Trapping Rain Water 收集雨水 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,

  • C++实现LeetCode(11.装最多水的容器)

    C++实现LeetCode(11.装最多水的容器)

    [LeetCode] 11. Container With Most Water 装最多水的容器 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two

  • C++实现LeetCode(验证数字)

    [LeetCode] Valid Number 验证数字 Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true "

  • C++实现LeetCode(44.外卡匹配)

    [LeetCode] 44. Wildcard Matching 外卡匹配 Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequenc

  • C++实现LeetCode(84.直方图中最大的矩形)

    C++实现LeetCode(84.直方图中最大的矩形)

    [LeetCode] 84. Largest Rectangle in Histogram 直方图中最大的矩形 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of e

  • C++实现LeetCode(10.正则表达式匹配)

    [LeetCode] 10. Regular Expression Matching 正则表达式匹配 Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. T

  • C++实现LeetCode(768.可排序的最大块数之二)

    [LeetCode] 768.Max Chunks To Make Sorted II 可排序的最大块数之二 This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements cou

  • C++实现LeetCode(55.跳跃游戏)

    [LeetCode] 55. Jump Game 跳跃游戏 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach th

  • Java跳跃游戏实例真题解决思路详解

    Java跳跃游戏实例真题解决思路详解

    目录 变式题—跳跃游戏 I 一.题目描述 二.思路 三.代码 变式题—跳跃游戏 II 一.题目描述 二.思路 三.代码 变式题—跳跃游戏 I 一.题目描述 给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 .数组中的每个元素代表你在该位置可以跳跃的最大长度.判断你是否能够到达最后一个下标. 来源:https://leetcode.cn/problems/jump-game/ 示例: 二.思路 本题可以使用贪心法解决,对每个能到达的位置(可覆盖到的位置),计算其每次能覆盖的最大长度,

  • C++实现LeetCode(174.地牢游戏)

    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the t

  • Vue实现Chrome小恐龙游戏的示例代码

    Vue实现Chrome小恐龙游戏的示例代码

    目录 前言 复刻画面 动画效果 路面动画 障碍物动画 恐龙动画 响应事件 碰撞检测 部署 总结 前言 几年前,Google 给 Chrome 浏览器加了一个有趣的彩蛋:如果你在未联网的情况下访问网页,会看到 “Unable to connect to the Internet” 或 “No internet” 的提示,旁边是一只像素恐龙. 许多人可能觉得这只恐龙只是一个可爱的小图标,在断网的时候陪伴用户.但是后来有人按下空格键,小恐龙开始奔跑! 这只可爱的小恐龙是设计师 Sebastien Ga

  • C++ 算法精讲之贪心算法

    C++ 算法精讲之贪心算法

    目录 选择排序 平衡字符串 买股票的最佳时机 跳跃游戏 钱币找零 多机调度问题 活动选择 无重叠区间 选择排序 我们熟知的选择排序,其采用的就是贪心策略. 它所采用的贪心策略即为每次从未排序的数据中选取最小值,并把最小值放在未排序数据的起始位置,直到未排序的数据为0,则结束排序. void swap(int* arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void selectSort(int* a

  • C#实现微信跳一跳小游戏的自动跳跃助手开发实战

    C#实现微信跳一跳小游戏的自动跳跃助手开发实战

    一.前言: 前段时间微信更新了新版本后,带来的一款H5小游戏"跳一跳"在各朋友圈里又火了起来,类似以前的"打飞机"游戏,这游戏玩法简单,但加上了积分排名功能后,却成了"装逼"的地方,于是很多人花钱花时间的刷积分抢排名.后来越来越多的聪明的"程序哥们"弄出了不同方式不同花样的跳一跳助手(外挂?),有用JS实现的.有JAVA实现的.有Python实现的,有直接物理模式的.有机械化的.有量尺子的等等,简直是百花齐放啊-- 赶一下潮流

  • Python 实现平台类游戏添加跳跃功能

    在本期使用 Python Pygame 模块编写视频游戏中,学会如何使用跳跃来对抗重力. 在本系列的前一篇文章 中,你已经模拟了重力.但现在,你需要赋予你的角色跳跃的能力来对抗重力. 跳跃是对重力作用的暂时延缓.在这一小段时间里,你是向上跳,而不是被重力拉着向下落.但你一旦到达了跳跃的最高点,重力就会重新发挥作用,将你拉回地面. 在代码中,这种变化被表示为变量.首先,你需要为玩家精灵建立一个变量,使得 Python 能够跟踪该精灵是否正在跳跃中.一旦玩家精灵开始跳跃,他就会再次受到重力的作用,并

  • C++实现LeetCode(312.打气球游戏)

    [LeetCode] 312. Burst Balloons 打气球游戏 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon iyou will get nums[left] * nums[i]

  • 教你利用pygame模块制作跳跃小球小游戏

    教你利用pygame模块制作跳跃小球小游戏

    前言 pygame是用来开发游戏的一套基于SDL的模板,它可以是python创建完全界面化的游戏和多媒体程序,而且它基本上可以在任何系统上运行.本文将详细介绍你利用pygame模块制作跳跃小球小游戏的相关内容,下面来一起看看吧 实现方法 首先创建一个游戏窗口,然后再窗口内创建一个小球.以一定的速度移动小球,当小球碰到游戏窗口的边缘时,小球弹回,继续移动.可以按照如下步骤实现该功能. (1)首先来创建一个游戏窗口,宽和高设置为640×480.代码如下: import sys #导入sys模块 im

随机推荐