专栏首页算法工程师之路贪心算法问题-LeetCode 55、45(贪心算法,跳跃问题)

贪心算法问题-LeetCode 55、45(贪心算法,跳跃问题)

贪心算法问题:LeetCode #55 #45

1

编程题

【LeetCode #55】跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。

示例 1:

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

算法原理: 遍历整个nums数组,每次计算从i位置的最大可能到达的距离,然后依次更新这个最大值,如果最大值大于nums的大小nums.size(),那么就返回true, 否则返回false.

其中i的范围是:小于nums.size()同时还要小于从当前位置i可以到达的距离。这就是正常人取求解这个问题的思路,很容易想到的!

C++代码:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = ;
        for(int i =  ;i < nums.size() && i <= maxReach; i++){
            maxReach = max(maxReach, i+nums[i]);
        }
        if(maxReach < nums.size()-1){
            return false;
        }
        return true;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game

【LeetCode #45】跳跃游戏II

给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。

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

示例:

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

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

算法原理: 由于题目中规定总能到达数组的最后一个位置,因此我们在遍历数组时每次都要去找最大的跳跃位置,只有到达了这个最远的边界end,我们才让step进行自加,同时更新最远的边界end为最远可以跳跃的位置。

如下图,开始的位置是 2,可跳的范围是橙色的。然后因为 3 可以跳的更远,所以跳到 3 的位置。

如下图,然后现在的位置就是 3 了,能跳的范围是橙色的,然后因为 4 可以跳的更远,所以下次跳到 4 的位置。

class Solution {
public:
    int jump(vector<int>& nums) {
        int end = ;
        int maxReach = ;
        int step = ;
        for(int i = ;i < nums.size()-1;i++){
            maxReach = max(maxReach, nums[i] + i);
            if(i == end){
                end = maxReach;
                step++;
            }
        }
        return step;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game-ii

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538),作者:TeddyZhang

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

原始发表时间:2019-09-26

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 位运算问题-LeetCode 136、137、260(只出现一次的数,异或运算)

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。你可以不使用额外...

    算法工程师之路
  • 哈希表-LeetCode 217、219、220、232(hashset、hashmap)

    给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

    算法工程师之路
  • 单调栈-LeetCode 739、287(单调栈,桶计数)

    根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定...

    算法工程师之路
  • [6张信息图]余额宝周岁大数据报告

    大数据文摘
  • 封装之路 (二)BaseActivity

    ? 封装之路 (二)BaseActivity 目标 :作为封装,实现BaseActivity,基于Dagger2+Databinding的模式。 当前主要实...

    用户1263308
  • 「性能测试实战30讲」之问题问答整理五

    第一个问题:如何理解“服务端的并发能力”这一描述? 首先我们从数据视角来理解,可以把服务端程序用一个模型来看待,即由「网络 API 请求」所驱动的。 服务端的...

    高楼Zee
  • c语言实现TCP的socket通信

    ######################################## #makefile #############################...

    特立独行的猫a
  • 【剑指offer】二维数组中的查找

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • Java并发-23.Fork/Join框架

    悠扬前奏
  • 源码阅读--Retrofit

    提莫队长

扫码关注云+社区

领取腾讯云代金券