力扣(LeetCode)55

CodeSheep 发布于2019-08-16 15:52 / 671人阅读

摘要：解答解法一动态规划。令为跳到第个位置是否可达。代码这个时间复杂度有点大，看了下面的提示这个题其实是贪心算法。那么如何用贪心算法来做呢可以用一个变量来维护当前能够到达的最远节点坐标，初始时，即为点能到达的最远节点。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
给定一个非负整数数组，你最初位于数组的第一个位置。

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

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

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:

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

解答：
解法一：动态规划。
令dp[i]为跳到第i个位置是否可达。
那么dp[0] = true。
对于dpi
如果在存在一个k(k>=0,k < i)使得dp[k] = true （即到k是可达的）并且 nums[k]+k>=i（从k可以跳到i）
那么dp[i] = true。
这个时间复杂度为O(N²)。

java ac代码：

class Solution {
    
    public boolean canJump(int[] nums) {
        
        boolean[]dp = new boolean[nums.length];
        dp[0] = true;
        for(int i = 1;i < nums.length;i++)
        {
            for(int k = 0;k <= i-1;k++)
                if(dp[k]&&nums[k] >= i-k)
                {
                    dp[i] = true;
                    break;
                }
        }
        
        return dp[nums.length-1];
        
    }
    
    
}

这个时间复杂度有点大，看了下面的提示这个题其实是贪心算法。
那么如何用贪心算法来做呢？
可以用一个max变量来维护当前能够到达的最远节点坐标，初始时max=nums[0]，即为0点能到达的最远节点。
然后从1开始(i=1...nums.length-1)，如果max >= i代表能够到达i节点，如果nums[i] + i > max代表
从这个点能够到达超过max的点，那么就更新max为nums[i] + i。
这样一来每个节点只被访问一次，时间复杂度为O(N)。

java ac代码：

class Solution {
    
    public boolean canJump(int[] nums) {
        
        //max为当前最大可达的位置
        int max = nums[0];
        int len = nums.length;
        
        for(int i = 1;i <= max && i < len ;i++)
            if(nums[i] + i > max)
            max = nums[i]+i;
        return max >= nums.length-1;
        
    }
    
    
}

海外云主机私有云力扣 LeetCode LeetCode_String leetcode_35_SearchIn

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

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

力扣(LeetCode)45

摘要：数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例输入输出解释跳到最后一个位置的最小跳跃数是。不过可惜的是复杂度过大，为，用例不通过。也只访问一次，时间复杂度为。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位...

wangshijun 2019-08-16 15:52 评论0 收藏0
力扣(LeetCode)357

摘要：示例输入输出解释答案应为除去外，在区间内的所有数字。即这个数最多位。解答这一题就是利用回溯法求组合数，从这个集合中求。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10的n次方。示例: 输入: 2输出: 91 解释: 答案应为除去 11,22,33,44,55,...

JasinYip 2019-08-16 15:17 评论0 收藏0
力扣(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