Leetcode 55 Jump Game

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.

Determine if you are able to reach the last index.

For example: A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

和之前用最少步数跳到终点的方法一样,贪心!

http://blog.csdn.net/accepthjp/article/details/52484618

如果能够跳到终点,则用最小步数的试探方法一定能够到达终点!

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 41 First Missing Positive 正解不是盛传的桶排序

    Given an unsorted integer array, find the first missing positive integer. For ...

    triplebee
  • Leetcode 45 Jump Game II

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

    triplebee
  • Leetcode 164 Maximum Gap 桶排序好题

    Given an unsorted array, find the maximum difference between the successive ele...

    triplebee
  • 经典笔试题-编程题

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

    cwl_java
  • LeetCode90. 子集 II

     升级版子集问题,最简单的办法,先把所有元素存储到set中去重,然后再重新赋值给数组,再dfs,但这样做太简单了,没什么难度,于是换了一种做法,不去重,直...

    mathor
  • LeetCode题解-Two Sum

    Given an array of integers, return indices of the two numbers such that they add...

    卡尔曼和玻尔兹曼谁曼
  • 树状数组解析

    prefixSum(idx):求从数组第一个位置到第idx(含idx)个位置所有数字的和。

    黑白格
  • 【USACO 1.5】SuperPrime Rib

    饶文津
  • LeetCode70|最小K个数

    排序在整个工作中还是比较的常用的一种场景,排序的目的是为了更加高效的检索自己需要的数据,对于数据库优化,为什么要加索引,难道不是为了更加高效的检索自己需要的数据...

    后端Coder
  • LeetCode78.子集

     dfs经典题,对每一个数字都有一个boolean数组去对应,没选过就是false,选过就是true,在边界条件中进行枚举,将所有结果为true的下标对应的数值...

    mathor

扫码关注云+社区

领取腾讯云代金券