专栏首页刷题笔记【LeetCode】45. Jump Game II

【LeetCode】45. Jump Game II

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

本文链接:https://blog.csdn.net/shiliang97/article/details/102785855

【LeetCode】45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index. Note:

You can assume that you can always reach the last index.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

感觉这种题目叫做贪心?

CPP

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

大佬的答案,优化了点?

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

java

class Solution {
   public int jump(int[] nums) {
    int end = 0;
    int maxPosition = 0; 
    int steps = 0;
    for(int i = 0; i < nums.length - 1; i++){//找能跳的最远的
        maxPosition = Math.max(maxPosition, nums[i] + i); 
        if( i == end){ //遇到边界,就更新边界,并且步数加一
            end = maxPosition;
            steps++;
        }
    }
    return steps;
   }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode】494. 目标和

    给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一...

    韩旭051
  • 【LeetCode第178场周赛】5344. 有多少小于当前数字的数字

    给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

    韩旭051
  • 【LeetCode】215. 数组中的第K个最大元素

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    韩旭051
  • Dimple在左耳听风ARTS打卡(第一期)

    参加了左耳听风的ARTS打卡,坚持一个月,对自己会有什么情况呢,我不知道,但我会照着这个目标坚持下去,坚持100天。一个习惯养成是21天,那如果坚持100天,效...

    程序员小跃
  • 2018年各大互联网前端面试题二(滴滴打车)

    王小婷
  • 【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法

    给定一个数组,包含从 到 所有的整数,但其中缺了两个数字。你能在 时间内只用 的空间找到它们吗?

    godweiyang
  • LeetCode 137 Single Number II

    ShenduCC
  • 剑指offer java版(一)

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    蜻蜓队长
  • Leetcode 215. Kth Largest Element in an Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Android技能树 — 排序算法基础小结

    现在安卓面试,对于算法的问题也越来越多了,要求也越来越多,特别是排序,基本必考题,而且还动不动就要手写,所以陆续要写算法的文章,也正好当自己学习。o(╥﹏╥)o

    青蛙要fly

扫码关注云+社区

领取腾讯云代金券