The most intuitive solution yet still accepted as best in C++, well-explained


  • 1

    Using greedy method is quite strai
    ght-forward here, we need to finish this jumping as soon as possible but the question is what should be the factor for us to be greedy for: <font color="#ff0000">the farthest jump</font>

    Once we are in a position i the farthest position we can reach is i+nums[i] and within this range we should find the most potential index j which will give us the biggest j+nums[j] and then we move to the most potential position j and then on and on till we move to the last or over it.

    int next = 0, maxDes = 0;
    for(int j = i+1; j <= i+nums[i]; ++j)
    {
        if(nums[j]+j > maxDes) 
        next = j, maxDes = nums[j]+j;   
    }
    

    Quite direct and simple though some details should be cared about.


    class Solution {
    public:
        //AC - 16ms - greedy method selecting the proper factor to be greedy for;
        int jump(vector<int>& nums) 
        {
            int i = 0, jumps = 0, size = nums.size();
            if(size == 1) return 0;
            while(i < size)
            {
                if(i+nums[i] > size-2) return ++jumps; //the last jump to or over the last;
                int next = 0, maxDes = 0;
                for(int j = i+1; j <= i+nums[i]; ++j) //searching for the most potential position;
                {
                    if(nums[j]+j > maxDes) 
                        next = j, maxDes = nums[j]+j;
                }
                i = next; //jump to the most potential position;
                jumps++; //count the jump;
            }
            return 0; //for compilation matter, actually this statement will never be invoked;
        }
    };

  • 0
    N

    this explanation is really easy for understanding, thanks!


Log in to reply
 

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