LeetCode题解55.jump-game

题目地址

https://leetcode.com/problems/jump-game/description/

题目描述

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.

思路

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

关键点解析

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

代码

• 语言支持: 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

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈

LeetCode题解白石搭白塔

输入黑块和白块的数量，用输入的方块数目建塔，输出最大高度和种数，两种方法至少一层颜色不同才能算不同的方法塔满足下列要求:1. 塔底层块数和高度数值相同，逐层递减1，最高层为12. 每层颜色相同

LeetCode题解分鸡块

外卖鸡块分别有 4，6，12 块， 每 固定块数不能分开装， 用户给一个数字， 要求返回满足用户订单（可以等于也可以大于）的最少的盒数的组合