[LeetCode] 55. Jump Game

Medium
Related Topics: Array / Dynamic Programming / Greedy
LeetCode Source

解题想法

应该算大部分人的解法，这题因为我有印象，所以有写出来

但当时也是看别人解法 XD

主要是寻访每一个 nums 里头的值

并透过 count 来判断能否顺利完成 Jump Game

int count = nums[0];　来初始化第一步

count = max(count - 1, nums[i]); 使用贪婪选先前 count-1 或是当下的值

结果判断是透过 count 有没有小于等于零

Python

class Solution:    def canJump(self, nums: List[int]) -> bool:        count = nums[0]        for i in range(1, len(nums)):            if count <= 0:                return False            count = max(count - 1, nums[i])        return True

C++

class Solution {public:    bool canJump(vector<int>& nums) {        int count = nums[0];        for (int i = 1; i < nums.size(); i++) {            if (count <= 0)                return false;            count = max(count - 1, nums[i]);        }        return true;    }};

这系列文被记录在 Top Interview 150 Series