力扣45. 跳跃游戏 II

Problem: 45. 跳跃游戏 II

题目描述

思路

1.获取数组的长度len，定义int类型变量end用于标记每次在当前可以跳到的最远距离，farthest用于记录每次可以跳跃到的最远距离，jumps用于记录最小的跳跃次数；
2.从0 ~ len遍历nums，并每次更新farthest（farthest = max(nums[i] + i, farthest);），若走到了当前可以跳跃到的最远距离，则更新end（end = farthest;），并使jump++，若当end >= len - 1时则直接返回jumps即可

复杂度

时间复杂度:

$O(n)$；其中$n$是数组nums的长度；

空间复杂度:

$O(1)$

Code

class Solution {
public:
    /**
     * Greedy algorithm
     * 
     * @param nums Given array
     * @return int
     */
    int jump(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        int len = nums.size();
        int end = 0;
        int farthest = 0;
        int jumps = 0;
        for (int i = 0; i < len; ++i) {
            farthest = max(nums[i] + i, farthest);
            if (end == i) {
                jumps++;
                end = farthest;
            }
            if (end >= len - 1) {
                return jumps;
            }
        }
        return jumps;
    }
};

原文地址：https://blog.csdn.net/LNsupermali/article/details/137694670

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！