[LeetCode] 45. Jump Game II

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

解题想法

先初始化一些变数

主要思路是判断当前可触及的长度有无超越 nums 的长度

如果有则回传 res

否则更新当前 cur_max_reach

而在由 index 0 到 cur_max_reach 的值更新 max_reach

Python

class Solution:    def jump(self, nums: List[int]) -> int:        max_reach = 0  # current max index that can be reached        max_len = len(nums)  # the length of nums        res = 0  # the minimum number of jumps        if max_len == 1:            return 0        while max_reach < max_len - 1:            res += 1            cur_max_reach = max_reach            for i in range(cur_max_reach + 1):                max_reach = max(max_reach, i + nums[i])        return res

C++

class Solution {public:    int jump(vector<int>& nums) {        int res = 0, max_len = nums.size(), max_reach = 0;        if (max_len == 1)            return 0;        while (max_reach < max_len - 1) {            res += 1;            int cur_max_reach = max_reach;            for (int i = 0; i < cur_max_reach + 1; i++)                max_reach = max(max_reach, i + nums[i]);        }        return res;    }};

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