专栏首页木又AI帮打卡群刷题总结1006——跳跃游戏 II

打卡群刷题总结1006——跳跃游戏 II

题目:45. 跳跃游戏 II

链接:https://leetcode-cn.com/problems/jump-game-ii

给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。

解题:

1、只要当前位置(cur_index)能够跳到的最远位置(max_index)不是最后一个位置,则必定需要至少一步再能跳到最后一个位置。

我们从cur_index + 1到max_index中找到一个位置index,该位置能够跳到的最远位置index + nums[index]是最大的,所需步数在原始步数上加1。不断迭代,直到能跳到最后一个位置,这样得到的步数就是最小的。

代码:

class Solution:
    def jump(self, nums: List[int]) -> int:
        step = 0
        last_len = 0
        max_len = 0
        # 只要没到最后一个元素,就得不断循环(保证能到达)
        while max_len < len(nums) - 1:
            tmp_max_len = max_len
            # last_len 到 max_len 选择 i + nums[i]最大的
            for i in range(last_len, max_len + 1):
                tmp_max_len = max(tmp_max_len, i + nums[i])
             
            last_len = max_len + 1
            max_len = tmp_max_len
            step += 1
        return step

PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

PPS:还是得日更呀,总结一下总是好的。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

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

原始发表时间:2020-10-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结1005——跳跃游戏

    链接:https://leetcode-cn.com/problems/jump-game

    木又AI帮
  • 【leetcode刷题】T173-跳跃游戏 II

    可以用动态规划来做,对于所有的j=i,dp[i] = min(dp[j] + 1)

    木又AI帮
  • ​LeetCode刷题实战45:跳跃游戏 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 打卡群刷题总结0610——猜数字游戏

    链接:https://leetcode-cn.com/problems/bulls-and-cows

    木又AI帮
  • 打卡群刷题总结0922——丑数 II

    链接:https://leetcode-cn.com/problems/ugly-number-ii

    木又AI帮
  • 贪心算法:跳跃游戏II

    题目地址:https://leetcode-cn.com/problems/jump-game-ii/

    代码随想录
  • 打卡群刷题总结0920——打家劫舍 II

    链接:https://leetcode-cn.com/problems/house-robber-ii

    木又AI帮
  • 打卡群刷题总结0827——组合总和 II

    链接:https://leetcode-cn.com/problems/combination-sum-ii

    木又AI帮
  • 打卡群刷题总结0812——路径总和 II

    链接:https://leetcode-cn.com/problems/path-sum-ii

    木又AI帮
  • LeetCode40-60题汇总,速度收藏!

    今天把最近发布的40-60篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相信很多人都没看过,如果对于算法感兴趣的,建议可以每篇认真阅读一...

    程序IT圈
  • 打卡群刷题总结0713——螺旋矩阵 II

    链接:https://leetcode-cn.com/problems/spiral-matrix-ii

    木又AI帮
  • 打卡群刷题总结0717——不同路径 II

    链接:https://leetcode-cn.com/problems/unique-paths-ii

    木又AI帮
  • 打卡群刷题总结0802——反转链表 II

    方法:得找到第m-1个节点,在翻转m->n链表后,再修改m和m-1位置上节点指针。

    木又AI帮
  • 打卡群刷题总结0601

    链接:https://leetcode-cn.com/problems/valid-anagram/

    木又AI帮
  • LeetCode1-100题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到100道题了。今天把发布的1-100篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • 打卡群刷题总结0723——组合

    链接:https://leetcode-cn.com/problems/combinations

    木又AI帮
  • 打卡群刷题总结0724——子集

    链接:https://leetcode-cn.com/problems/subsets

    木又AI帮
  • LeetCode50-80题汇总,速度收藏!

    今天把最近发布的50-80篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相信很多人都没看过,如果对于算法感兴趣的,建议可以每篇认真阅读一...

    程序IT圈
  • 打卡群刷题总结0919——打家劫舍

    链接:https://leetcode-cn.com/problems/house-robber

    木又AI帮

扫码关注云+社区

领取腾讯云代金券