leetcode55-跳跃游戏

原题

原题

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

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

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

示例1:

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

示例2:

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

解法

思想

  1. 动态规划,看某一个点是否能到达最后一个点,如果能,那是否另外某个点能到达这个点。
  2. 贪心算法,如果能到达点a,那么a之前的点也一定能够到达。从右往左找到一个能到达最后一个点的位置,然后继续往左找到一个能到达当前点的位置,如此循环,如果能找到第一个点则返回true。

代码

动态规划+记忆:

class Solution {
    int[] numsGlobal; 
    Boolean[] canJump;
    public boolean canJump(int[] nums) {
        numsGlobal = nums;
        canJump = new Boolean[nums.length];
        return canJumpTo(nums.length-1);
    }

    public boolean canJumpTo(int index){
        if(index == 0) return true;
        if(canJump[index]!=null) return canJump[index];
        for(int i = 0;i<index;i++){
            if(numsGlobal[i]>=index-i) {
                if(canJumpTo(i)) {
                    canJump[i] = true;
                    return true;
                }
            }
        }
        canJump[index] = false;
        return false;
    }
}

贪心算法:

倒序

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

正序

func canJump(nums []int) bool {
    farest := 0
    for index, distance := range nums{
        if index > farest{
            return false
        }
        if index + distance > farest{
            farest = index + distance
            if farest >= len(nums) - 1{
                return true
            }
        }
    }
    return true
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode55-%e8%b7%b3%e8%b7%83%e6%b8%b8%e6%88%8f/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月8日
下一篇 2020年2月9日

相关推荐

  • leetcode887-鸡蛋掉落

    原题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 &…

    算法 2020年4月11日
    0120
  • leetcode125-验证回文串

    原题 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明: 本题中,我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a …

    算法 2020年5月21日
    0140
  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0140
  • leetcode374-猜数字大小

    原题 我们正在玩一个猜数字游戏。 游戏规则如下:我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了,我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接…

    算法 2019年12月31日
    0370
  • leetcode4-寻找两个有序数组的中位数

    这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m…

    算法 2020年1月9日
    0620
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    090
  • leetcode945-使数组唯一的最小增量

    原题 给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入: [1,2,2] 输出: 1…

    算法 2020年3月22日
    0630
  • leetcode25-K个一组翻转链表

    原题 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原…

    算法 2020年5月9日
    0540
  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080
  • leetcode530-二叉搜索树的最小绝对差

    原题 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例: 输入:    1    &n…

    算法 2020年2月22日
    01330

发表回复

登录后才能评论