Share my greedy solution, starting from last Index


  • 2
    D

    Start from last index. For each step, find the smallest index it can jump from and then update the last index until last index reaches zero.

    public class Solution {
        public int jump(int[] nums) {
            int lastIndex = nums.length - 1;
            int step = 0;
            int i;
            
            while (lastIndex != 0) {
                for (i = 0; i < lastIndex; i++)
                    if (i + nums[i] >= lastIndex)
                        break;
                if (i == lastIndex)
                    return -1;
                lastIndex = i;
                step++;
            }
            
            return step;
        }
    }

  • 0
    H

    I ' d like to show everyone one of my fool solution, to reminded me do not makes such fool mistake!
    I have the same mind with you, but I search the samllest one from the index to 0. It works fine when the testcase was small,but time limited when the test case is 25000's one.

    int jump(vector<int>& nums) {
    	if(nums.empty()) return 0;
    	int n = nums.size(), ans = 0, index = n-1, next = -1;
    	while(index>0) {
    		for (int i = index-1; i >=0 ; i--)
    		{
    			if(nums[i] >= index-i) next = i;
    			// cout<<nums[i]<<","<<index-i<<endl;
    		}
    		index = next;
    		// cout<<index<<endl;
    		ans++;		
    	}
    	return ans;
    }

  • 0
    H

    Oh, No.Although your answer is better than mine,
    but your answer also time limited.when the test case was 25000's one.


  • 0
    B

    Time limited,it‘s O(N^2).


  • 0
    D

    Yes, you are right. I found the problem and so it's necessary to start from zero and to record the last farthest index.


  • 0
    D

    Yes, I have realized the problem. Actually it's O(n^2). So it's necessary to start from zero and record the last farthest index.
    But I thought this approach may be easy to understand...


Log in to reply
 

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