【leetcode】55. 跳跃游戏

题目内容

55. 跳跃游戏

思路分析

一开始看到题目的时候，没什么思路，感觉可能要用动态规划，就直接去看了答案。看了答案感觉还是挺简单的，虽然说是贪心，但是没感觉贪心在哪了，只感觉是一种“聪明人”的做法。

翻评论的时候看到一句话

属于贪心，每一步都贪婪的计算最远到达位置。

那就勉强算贪心吧~

具体思路如下：

维护一个能够到达的最远位置
遍历输入的数组，不断地更新最远位置
如果发现遍历到某数时已可以跳到最后或跳出数组，则直接返回true
如果发现遍历到某数时次数大于能够到达的最远位置，则该位置不可达，终止循环，返回false
如果遍历完整个数组都没有返回true，则证明无法到达最后，返回false

代码

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution {
public:
    // 参考官方直接写的解
    // 时间复杂度O(N),空间复杂度O(1)
    bool canJump(vector<int>& nums) {
        int reach{ 0 };
        unsigned long n{ nums.size() };
        for (int i = 0; i < n && i <= reach; ++i) {
            reach = max(reach, i + nums[i]);
            if (reach >= n - 1) return true;
        }

        return false;

    }
};


int main() {
    Solution s;
    vector<int> input{ 3,2,1,0,4 };

    bool output;
    output = s.canJump(input);

    return output;
}

收获

没啥收获，感觉这个题的解法可能比较特殊，不是某一类的通用解法（随着做的题数的增加再看吧，说不定有点用）。还有就是不要太快看答案，还是得自己思考一下，不然做出来都没啥成就感。