45.jump-game-ii 跳跃游戏II

问题描述

45.跳跃游戏II

解题思路

外循环还是从末尾向前遍历，内循环从前往后遍历，每次找能到达终点的索引最小的位置，该位置作为新的终点，同时步数cnt++。

代码

#include <vector>
using std::vector;
class Solution {
  public:
    int jump(vector<int> &nums) {
        int cur_end = nums.size() - 1;
        int cnt = 0;
        while (cur_end != 0) {
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] + i >= cur_end) {
                    cur_end = i;
                    cnt++;
                    break;
                }
            }
        }
        return cnt;
    }
};