C++ implement with a different idea


  • 0
    S

    record: 1) last: last jump point; 2) jumps: number of jumps so far; 3) left_j: number of jumps left when jumping from the last jump point to the current one. When left_j < 0, it means it can't jump to the current point from the last one, then search for the point which has the maximum left_j and record it as the last jump point.

    class Solution {
    public:
        int jump(vector<int>& nums) {
            int len = nums.size();
            if(len < 2) return 0;
            int last=0, jumps=1, left_j=nums[0];
            for(int i=1; i<len; i++)
            {
                left_j--;
                if(left_j < 0)
                {
                    for(int j=last+1; j<i; j++)
                    {
                        if(nums[j] >= i-j && nums[j]-(i-j) > left_j)
                        {
                            left_j = nums[j]-(i-j);
                            last = j;
                        }
                    }
                    jumps++;
                }
            }
            return jumps;
            
        }
    };

  • 0
    G
    class Solution {
    

    public:
    int jump(vector<int>& nums) {
    int size = nums.size();
    if(size == 1) return 0;
    int nextpos = 0, max_jmp_range = 0;
    int steps = 0;
    //as i was already placed on the first index so didn't count that step;
    for(int i = 0; i < size; i++) {
    if(i > nextpos) {
    steps++;
    nextpos = max_jmp_range;
    }
    max_jmp_range = max(i+nums[i], max_jmp_range);
    }
    return steps;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.