leetcode45 -- Jump Game2 (被面过)

leetcode45 -- Jump Game2 (被面过)

题目

Given an array of positive integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.


这次和刚才的不太一样了,之前是要看能不能到达,现在是要看到达当前的位置需要的最小的步数,

解法1

我最初想到的是DP,可以设f(n)为到达第n个位置时所需要的最小的步数,因为题目中说了,每个位置都是正数,所以每个位置肯定是都可以到达的. 那么到达第n个位置肯定是从之前的某一个位置跳过来的,

所以f(n) = 1+min(f(m), m 是个集合,满足 可以从位置m跳到位置n.)

解法2

看网上可以用贪婪的解法

比如


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

意思是在当前位置的时候并不一定是它的能力所能达到的位置, 所以要找到它的能力所能达到的那个位置,然后从那个位置再继续考虑.

用python的话就是

class Solution:
    def jump(self, nums: List[int]) -> int:
        res = 0
        n = len(nums)
        
        cur = 0
        
        # cur 的意思是虽然当前在这个位置,但是其实说不定能够跳得更远一些
        while cur<n-1:
            res +=1 
            pre = cur
            
            for i in range(pre+1):
                cur = max(cur, i+nums[i])
        return res
                

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦