leetcode 45.跳跃游戏Ⅱ 贪心法求解（c++版本）

题目描述

与leetcode 55不一样的地方在于这个需要计算出次数。因此仅需计算出次数即可，那么要明白步数在什么时候增加
达到当前的最大位移时，但是仍然不是数组的最后一个节点时+1

代码实现

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 0;
        int cur_index = 0;
        int cover = 0;
        if(nums.size() == 1)
        {
            return 0;
        }
        for(int i = 0; i < nums.size(); i++)
        {	// 计算并且获取最大位移
            cover = max(nums[i]+i, cover);
            if(i==cur_index) // 遍历到最大位移处
            {
                if(cur_index != nums.size()-1)
                {	// 非最后一个元素处
                    count++; // 步数加一
                    cur_index = cover; // 更新
                    if(cover >= nums.size()-1)
                    {
                        break;
                    }
                }
            }
        }
        return count;
    }
};
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