V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  算法

[每日 Leetcode] 55. 跳跃游戏

  •  
  •   Acceml · 2018-08-27 23:11:28 +08:00 · 2237 次点击
    这是一个创建于 2040 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1:

    输入: [2,3,1,1,4]
    输出: true
    解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
    

    示例 2:

    输入: [3,2,1,0,4]
    输出: false
    解释: 无论怎样,你总会到达索引为 3 的位置。
    但该位置的最大跳跃长度是 0, 所以你永远不可能到达最后一个位置
    

    题解

    这个题要先理解题目,题目中说的是:数字代表的是最大的可跳跃长度,比如数字是 3,那么你跳 1,2,3 都行,而不是只可以跳 3 步。

    遍历数组一直跳就好,用 max 记录当前可以跳到的最大的步数,然后中间的用 num[i] + i 去贪心的更新最大步骤即可。 遍历的时候有几种情况: 1.遍历完恰好跳到最后,或者可以跳过,是目标解; 2.遍历的过程中遍历到第 i 个元素,结果前面无论怎么跳都跳不到这个地方,这个时候再怎么跳也跳不出来了.直接返回 false.

    class Solution {
        public boolean canJump(int[] nums) {
            int max = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i > max) {
                    return false;
                }
                //贪心求解可以到达的最远步数.
                max = Math.max(nums[i] + i, max);
            }
            return true;
        }
    }
    

    热门阅读


    最近在刷题,有组队的可以加QQ 群:805423079 Leetcode 名企之路

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   992 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 20:05 · PVG 04:05 · LAX 13:05 · JFK 16:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.