C++ implementation


  • 1

    This is my ac implementation, before AC.

    I got some error as I miss to update end in the loop end

      start=end+1;
      end=limit;
    

    Here is the final code:

    class Solution {
    public:
        int jump(vector<int>& nums) {
            int n=nums.size(), start=0, end=0, limit=0;
            int result=0;
            while(limit<n-1){
                result++;
                limit=end;
                for(int i=start; i<=end; i++){
                    if(nums[i]+i >= n-1) return result;
                    if(nums[i]+i > limit) limit=nums[i]+i;
                }
                start=end+1;
                end=limit;
            }
            return result;
        }
    };

  • 0
    2

    Here is a more concise implementation ....

    class Solution {
    public:
        int jump(vector<int>& nums) {
            int size_nums = nums.size();
            int start = 0, end = 0, limit = 0;
            int step = 0;
            while(end < size_nums - 1) {
                step++;
                limit = end;
                for(int i = start; i <= end; i++) {
                    limit = max(limit, nums[i] + i);
                }
                start = end + 1;
                end = limit;
            }
            return step;
        }
    };

Log in to reply
 

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