力扣(LeetCode)45

wangshijun 发布于2019-08-16 15:52 / 323人阅读

摘要：数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例输入输出解释跳到最后一个位置的最小跳跃数是。不过可惜的是复杂度过大，为，用例不通过。也只访问一次，时间复杂度为。

题目地址：
https://leetcode-cn.com/probl...
题目描述：

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

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

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

示例:

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

解答：
和第55题一样，首先试一下动态规划dp[i]代表到坐标为i的节点所用的最短步骤。
那么dp[0] = 0，dp[i] = min(dp[i-k]+1) , k >= 0 并且 k <= i-1,并且nums[k]+k >= i。
不过可惜的是复杂度过大，为O(N²)，用例不通过。

换一种思路，这个和第55题一样，这是个贪心问题，用一个max变量记录当前能够到达的最远节点。那么初始时
max = nums[0]，对于i=1...nums.length-1，如果nums[i]+i > max（即该节点能够到达比max更远的节点）
就更新max，并且把dp[max+1]...dp[nums[i]+i]更新为dp[i]+1否则跳过。这样一来，每一个节点只计算一次。
也只访问一次，时间复杂度为O(N)。

java ac代码：

class Solution {
    public int jump(int[] nums) {
        
        int[]dp = new int[nums.length];
      
        //用这个最大值代替优先队列，因为效果是一样的
        //用优先队列保存已经求出的最大下标也可以，但是
        //每次都是从小到大求，所以每次求出更新max即可
        //保持是最大的，不需要使用优先队列。
        int max = nums[0];
        
        for(int i = 1;i < nums.length && i <= nums[0];i++)
        {
            dp[i] = 1;
        }
        
        for(int i = 1;i < nums.length;i++)
        {
            for(int k = max+1;k < nums.length&&k<=i+nums[i];k++)
            {
                dp[k] = dp[i]+1;
                max = k;
            }
        }
        
        return dp[nums.length-1];
        
    }
}

动态规划超时代码：

class Solution {
    public int jump(int[] nums) {
        
        int[] dp = new int[nums.length];
        dp[0] = 0;
        for(int i = 1;i < nums.length;i++)
        {
            int temp = Integer.MAX_VALUE;
            for(int k = i-1;k >= 0;k--)
                if(nums[k] >= i-k)
                    temp = Math.min(temp,dp[k]);
            dp[i] = temp+1;
            
        }
        return dp[nums.length-1];
        
    }
}

私有云 GPU服务器力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73752.html

力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
LeetCode.2 两数相加(Add Two Numbers)(JS)

摘要：更新之前说感觉优秀答案的最后三行可以用尾递归优化不知道尾递归的小伙伴可以点这里，仔细想了一下，并不能。尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。上周日就想写vue.nextTick的源码分析，可是总是不知道从哪儿下手，今天有时间，先把leetcode第二题补了，感觉这道题还挺简单的一、题目两数相加：给出两个非空的链表用来表示两个非负的整数。其中，它们各自...

Binguner 2019-08-23 16:26 评论0 收藏0
力扣(LeetCode)452

摘要：对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。解答这是一道区间覆盖问题，不太好说清楚，利用模板即可。题目地址：https://leetcode-cn.com/probl...题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方...

fanux 2019-08-16 15:20 评论0 收藏0