专栏首页脑洞前端55. 跳跃游戏

55. 跳跃游戏

题目描述

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

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

示例 2:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这道题目是一道典型的 回溯类型题目。思路就是用一个变量记录当前能够到达的最大的索引,我们逐个遍历数组中的元素去更新这个索引。变量完成判断这个索引是否大于数组下表即可。

关键点解析

  • 建模 (记录和更新当前位置能够到达的最大的索引即可)

代码

  • 语言支持: Javascript,Python3
/*
 * @lc app=leetcode id=55 lang=javascript
 *
 * [55] Jump Game
 *
 * https://leetcode.com/problems/jump-game/description/
 *
 * algorithms
 * Medium (31.38%)
 * Total Accepted:    252.4K
 * Total Submissions: 797.2K
 * Testcase Example:  '[2,3,1,1,4]'
 *
 * 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.
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  let max = 0; // 能够走到的数组下标

  for(let i = 0; i < nums.length; i++) {
      if (max < i) return false; // 当前这一步都走不到,后面更走不到了
      max = Math.max(nums[i] + i, max);
  }

  return max >= nums.length - 1
};

Python3 Code:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """思路同上"""
        _max = 0
        _len = len(nums)
        for i in range(_len-1):
            if _max < i:
                return False
            _max = max(_max, nums[i] + i)
            # 下面这个判断可有可无,但提交的时候数据会好看点
            if _max >= _len - 1:
                return True
        return _max >= _len - 1

本文分享自微信公众号 - 脑洞前端(fe_lucifer),作者:一个脑洞很大的程序员

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 47. 全排列 II

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations-ii 著作权归领扣网络所有。商...

    lucifer210
  • 46. 全排列

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载...

    lucifer210
  • 一文看懂《最大子序列和问题》(内含Java,Python,JS代码)

    最大子序列和是一道经典的算法题, leetcode 也有原题《53.maximum-sum-subarray》,今天我们就来彻底攻克它。

    lucifer210
  • Leetcode 198 House Robber

    You are a professional robber planning to rob houses along a street. Each house...

    triplebee
  • Leetcode 213 House Robber II

    Note: This is an extension of House Robber. After robbing those houses on that...

    triplebee
  • <DQueue、双端队列、滑动窗口>239.Sliding Window Maximum

    Given an array nums, there is a sliding window of size k which is moving from th...

    大学里的混子
  • 在Linux最大打开文件数限制下 MySQL 对参数的调整

    非root用户运行MySQL,当MySQL配置比较高时,MySQL运行中生效的参数值与配置的值不一样。 这篇文章的目的是为了说明在系统资源不够的情况下,MySQ...

    二狗不要跑
  • Leetcode Golang 136. Single Number.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88966147

    anakinsun
  • leetcode 26 Remove Duplicates from Sorted Array

    Remove Duplicates from Sorted ArrayTotal Accepted: 66627 Total Submissions: 2127...

    流川疯
  • leetcode330. Patching Array

    假设有一个有序的正整数数组nums和一个整数n,最少添加几个元素到这个数组中,使得从1-n的所有整数都可以由这个数组中的值的或是几个值的和构成。

    眯眯眼的猫头鹰

扫码关注云+社区

领取腾讯云代金券