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 index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

这题是之前那道 Jump Game 的延伸，那题是问能不能到达最后一个数字，而此题只让求到达最后一个位置的最少跳跃数，貌似是默认一定能到达最后位置的? 此题的核心方法是利用贪婪算法 Greedy 的思想来解，想想为什么呢？ 为了较快的跳到末尾，想知道每一步能跳的范围，这里贪婪并不是要在能跳的范围中选跳力最远的那个位置，因为这样选下来不一定是最优解，这么一说感觉又有点不像贪婪算法了。其实这里贪的是一个能到达的最远范围，遍历当前跳跃能到的所有位置，然后根据该位置上的跳力来预测下一步能跳到的最远距离，贪出一个最远的范围，一旦当这个范围到达末尾时，当前所用的步数一定是最小步数。需要两个变量 cur 和 pre 分别来保存当前的能到达的最远位置和之前能到达的最远位置，只要 cur 未达到最后一个位置则循环继续，pre 先赋值为 cur 的值，表示上一次循环后能到达的最远位置，如果当前位置i小于等于 pre，说明还是在上一跳能到达的范围内，根据当前位置加跳力来更新 cur，更新 cur 的方法是比较当前的 cur 和 i + A[i] 之中的较大值，如果题目中未说明是否能到达末尾，还可以判断此时 pre 和 cur 是否相等，如果相等说明 cur 没有更新，即无法到达末尾位置，返回 -1，代码如下：

解法一：

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, n = nums.size(), i = 0, cur = 0;
        while (cur < n - 1) {
            ++res;
            int pre = cur;
            for (; i <= pre; ++i) {
                cur = max(cur, i + nums[i]);
            }
            if (pre == cur) return -1; // May not need this
        }
        return res;
    }
};

还有一种写法，跟上面那解法略有不同，但是本质的思想还是一样的，关于此解法的详细分析可参见网友 实验室小纸贴校外版的博客，这里 cur 是当前能到达的最远位置，last 是上一步能到达的最远位置，遍历数组，首先用 i + nums[i] 更新 cur，这个在上面解法中讲过了，然后判断如果当前位置到达了 last，即上一步能到达的最远位置，说明需要再跳一次了，将 last 赋值为 cur，并且步数 res 自增1，这里小优化一下，判断如果 cur 到达末尾了，直接 break 掉即可，代码如下：

解法二：

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

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

赞 (0)

相关推荐

  • LeetCode 单调栈内容小结

    LeetCode 单调栈内容小结

    LeetCode Monotone Stack Summary 单调栈小结 所谓的单调栈 Monotone Stack,就是栈内元素都是单调递增或者单调递减的,有时候需要严格的单调递增或递减,根据题目的具体情况来看吧.关于单调栈,这个帖子讲的不错,而且举了个排队的例子来类比.那么,博主也举个生动的例子来说明吧:比如有一天,某家店在发 free food,很多人在排队,于是你也赶过去凑热闹.但是由于来晚了,队伍已经很长了,想着不然就插个队啥的.但发现排在队伍最前面的都是一些有纹身的大佬,惹不起,只

  • 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(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(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(7.翻转整数)

    [LeetCode] 7. Reverse Integer 翻转整数 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment whi

  • 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(验证数字)

    [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(8.字符串转为整数)

    [LeetCode] 8. String to Integer (atoi) 字符串转为整数 Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this ch

  • 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(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

  • python实战之利用pygame实现贪吃蛇游戏（二）

    python实战之利用pygame实现贪吃蛇游戏（二）

    一.前言 在上一篇博客中,我们实现了基本的界面搭建,这次实现一下逻辑部分. 二.创建蛇 首先,先分析一下蛇的移动,不然我们一定会吃亏的(别问,问就是自己写了一堆无效代码). 蛇的移动其实并没有想象中那样复杂,每一个模块都需要有一个方向,按照方向进行移动. 其实实际上就是一个出队的感觉,即每一个元素都取代上一个元素的位置,然后再按照贪吃蛇当前的方向,移动一下头节点即可. snake.py: """"

  • C++实现LeetCode(90.子集合之二)

    [LeetCode] 90. Subsets II 子集合之二 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example

  • C++实现LeetCode(40.组合之和之二)

    [LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u

  • C++实现LeetCode(59.螺旋矩阵之二)

    [LeetCode] 59. Spiral Matrix II 螺旋矩阵之二 Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆

  • C++实现LeetCode(126.词语阶梯之二)

    [LeetCode] 126. Word Ladder II 词语阶梯之二 Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed

  • C++实现LeetCode(140.拆分词句之二)

    [LeetCode] 140.Word Break II 拆分词句之二 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Not

随机推荐