Leetcode-45.跳跃游戏

发表于 分类于 阅读次数：

题目描述

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

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

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

示例:

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

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

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

解法1：贪心

采用贪心策略，计算每一步所能到达的最远位置，选择当前步能跳到的最优位置进行跳跃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        if(n==0)
            return 0;
        int i=0;
        int s=nums[0];
        int count=0;
        int max=-1;
        int j=i;
        i=i+1;
        int l;
        while(i<n)
        {
            if(s+j>=n-1)
            {
                count++;
                break;
            }
            while(i<=s+j)
            {
                if(max<=(nums[i]+i))
                {
                    max=nums[i]+i;
                    l=i;
                }
                i++;
            }
            s=nums[l];
            j=l;
            i=l+1;
            count++;
            max=-1;
        }
        return count;
    }
};

代码优化

创建一个end变量，表示能跳到的边界，如果遍历数组到达了边界就重新更新新的边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        int end=0;
        int count=0;
        int i;
        int maxs=0;
        for(i=0;i<n-1;i++)
        {
            maxs=max(maxs,nums[i]+i);
            if(i>=end)
            {
                end=maxs;
                count++;
            }
        }
        return count;
    }
};