`
cozilla
  • 浏览: 91906 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Jump Game / Jump Game II

 
阅读更多
Jump GameMar 25 '126923 / 16241

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.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

 

Jump Game IIMar 17 '126747 / 18561

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.

For example:
Given array A = [2,3,1,1,4]

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.)

 

class Solution {
public:
    bool canJump(int A[], int n) {
        int last = 0, t;
        for (int i = 0; i < n; i++) {
            if (i <= last) {
                t = i + A[i];
                if (last < t) last = t;
                if (last >= n-1) return true;
            } else return false;
        }
        return last >= n-1;
    }
};


class Solution {
public:
    int jump(int A[], int n) {
        int last = 0, step = 0, cur = 0, t;
        while (last < n-1) {
            int nextlast = last;
            for (int i = cur; i <= last; i++) {
                t = i + A[i];
                if (t > nextlast) nextlast = t;
            }
            step++;
            cur = last + 1;
            last = nextlast;
        }
        return step;
    }
};

 

分享到:
评论

相关推荐

    java-leetcode题解之Jump Game II.java

    java java_leetcode题解之Jump Game II.java

    java-leetcode题解之Jump Game.java

    java java_leetcode题解之Jump Game.java

    C语言-leetcode题解之45-jump-game-ii.c

    c语言入门 C语言_leetcode题解之45-jump-game-ii.c

    js-leetcode题解之45-jump-game-ii.js

    js js_leetcode题解之45-jump-game-ii.js

    java-leetcode题解之055-Jump-Game

    java入门 java_leetcode题解之055_Jump_Game

    fuxuemingzhu#Leetcode-Solution-All#55. Jump Game 跳跃游戏1

    1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一步之前的最优解则不作保留 2.由(1)中的介绍,可以知道贪

    js-leetcode题解之55-jump-game.js

    js js_leetcode题解之55-jump-game.js

    45jumpgame2.cpp

    leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题

    leetcode卡-Jump-Game-IV:跳跃游戏-IV

    在“Jump-Game-IV-main”文件中,可能包含了实现这个解决方案的源代码。通过分析和学习这段代码,我们可以更深入地理解上述概念,并了解如何在实际编程中应用这些算法。然而,为了适应大测试用例,可能需要进一步...

    leetcode71python-leetcode:leetcode

    leetcode 71 Python用 Python 编写 Leetcode (数据科学家的解决方案) - 易于理解的最佳解决方案,可以通过所有 Leetcode 测试用例,对于非 ...Game II (HARD) Leetcode 51. N-Queens (HARD) Leetcode 52. N-

    _leetcode-python.pdf

    - Jump Game / Jump Game II: 第一个问题要求判断是否能到达数组的最后一个位置,第二个问题要求求出最小跳跃次数到达最后一个位置。 - Permutations / Permutations II: 生成所有可能的排列组合,考虑重复元素的...

    Leetcode题目+解析+思路+答案.pdf

    - **Jump Game**:跳跃游戏,判断是否能到达数组末尾。 - **Gas Station**:寻找最短的加油路线。 - **Candy**:分糖果,确保每个孩子至少得到一块糖,尽可能公平。 - **Word Break**:判断一个字符串是否可以...

    gasstationleetcode-LeetCode_Practice:我的LeetCode练习从2020年开始

    加油站 leetcode 力扣_实践 标签: leetcode 我的 LeetCode 练习从 2020 年开始 ...Leetcode ...80_Remove_Duplicates_From_...45_Jump_Game_II 121_Best_Time_to_Buy_and_Sell_Stock 122_Best_Time_to_Buy_and_Sell_Stock_

    leetcode-常见考题2.pdf

    - 在 JumpGame 和 MinimumPathSum 题目中,动态规划用于找出跳跃游戏或路径选择中达到最优解的策略。 4. **堆栈**: - 堆栈数据结构可以用于处理与括号匹配、表达式求值等相关的题目。 - 在 ...

    LeetCode leetcode部分题解答代码实现

    * Jump Game:给定一个数组,判断是否可以跳跃到数组的末尾。这个题目需要使用贪心算法的思想,将数组分解成更小的子数组,并判断是否可以跳跃到末尾。 * Gas Station:给定一个数组,返回可以到达的加油站数量。这...

    leetcode代码200题c++

    4. **Jump Game II**:此问题涉及到广度优先搜索(BFS)或深度优先搜索(DFS)策略,以找出在给定限制下到达最远位置的跳跃次数。它考察了图遍历和优化算法性能的能力。 5. **Sliding Window Maximum**:这是一个...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...

    leetcode跳跃-leetcode:leetcode解题之路

    II](./Array/jump-game-ii.md) [0053 最大子序和](./Array/maximum-subarray.md) [0041 缺失的第一个整数](./Array/first-missing-positive.md) [0042 接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./...

    c++-c++编程基础之leetcode题解第45题跳跃游戏II.zip

    第45题“跳跃游戏II”(Jump Game II)是一道典型的动态规划问题,它要求我们找到在给定数组中达到最后一个元素的最小跳跃次数。在这道题目中,每个元素代表我们可以前进的最大步数,我们需要找到一个最优策略来最小...

Global site tag (gtag.js) - Google Analytics