前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode 第45题:跳跃游戏2

leetcode 第45题:跳跃游戏2

作者头像
帅地
发布2019-10-23 19:04:56
4750
发布2019-10-23 19:04:56
举报
文章被收录于专栏:苦逼的码农

学好算法没有捷径,最好的捷径就是多刷题,并且跳出舒适区,每道题都要寻找最优解,也不能老是做那些你自己比较擅长的题,不定期更新 Leetcode 的题,每道题都会给出多种解法以及最优解。

题目描述

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

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

代码语言:javascript
复制
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

说明:假设你总是可以到达数组的最后一个位置。

方法一、从右往左搜索

我们的目的是要跳跃到最后一个点上,我们可以从最后一个点往左开始寻找,例如非负数组为 arr = {2,3,1,1,4,2,1},从最右边的 1 往左寻找,找那个离右边的点最远,却又能到达它的点,如下图:

寻找每一个点的过程中,我们每次都需要遍历一遍数组,看看哪一个点更加合适,所以需要两层循环,时间复杂度为 O(n^2),空间复杂度为 O(1)。代码如下

代码语言:javascript
复制
    public int jump(int[] nums){
        int right = nums.length - 1;
        int sum = 0;
        while(right > 0){
            // 寻找离 last 最远,且能够到达 last 的点
            int cur = right - 1;
            for(int i = right - 2; i >= 0; i--){
                // 是否能够达到 last 这个点
                if( i + nums[i] >= right){
                    cur = i;
                }
            }
            right = cur;
            sum++;
        }
        return sum;
    }

方法二:贪心算法

这道题的最优解是可以时间复杂度优化到 O(n) 的,那就是采用贪心算法,我们从左边的起点开始跳跃的时候,我们应该跳跃到哪一个点比较合适呢?,显然,每次都跳跃最大长度的话,是不行的。例如对于上面 arr = {2, 3, 1, 1, 4, 2, 1} 这个例子,刚开 arr[0] = 2,那么我们可以跳到 arr[1] = 3 或者 arr[2] = 1 上,显然,我们跳跃 arr[1] = 3 会更好一点。如图(图片来源于网络)

接着同样的道理,我们可以从 arr[1] = 3 这个位置开始跳跃,它可以跳跃到 arr[2] = 1, arr[3] = 1, arr[4] = 4 这三个位置,显然,我们跳到 arr[4] = 4 这个位置好一点,如图(图片来源于网络)

也就是说,我们要跳跃的那个点,可以使得上一次 + 下一次的跳跃总距离最远。代码如下

代码语言:javascript
复制
    public int jump(int[] nums) {
        if(nums.length < 2)
            return 0;

        int sum = 0;
        int end = 0; // 能跳到的最远距离
        int max = 0; // 下一步可以跳到的最远距离
        for(int i = 0; i < nums.length - 1; i++){
            max = Math.max(max, i + nums[i]);
            // 更新当前点
            if(i == end){
                end = max;
                sum++;
            }
        }

        return sum;
    }

时间复杂度是 O(n),空间复杂度是 O(1)。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 帅地玩编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 方法一、从右往左搜索
  • 方法二:贪心算法
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档