C, four implementations for the same approach


  • 0
    M

    Simplest illustration would be to scan from start to the end with nested loops for figuring out the greatest possible leap from every offset:

    int canJump(int* nums, int numsSize)
    {
        int i, len = numsSize;
        int *a = nums, leap_o;
    
        /* Loop while the array is valid, and there is a scope to move
        forward */
        for (i = 0; i < len - 1 && a[i]; i = leap_o)
        {
            int j = i + 1;
    
            /* Seek the longest possible leap within range [i, a[i] + i] */
            leap_o = i + a[i];
            for(; j < len - 1 && j < (a[i] + i) && leap_o < len - 1; ++j)
                leap_o = (a[leap_o] + leap_o < (a[j] + j)) ? j : leap_o;
        }
    
        /* Return depending on the offset */
        return (i < len - 1) ? 0 : 1;
    }
    

    Now collapse the two loops into one. Here with each iteration we attempt to expand the margins of the search. Note that the loop exits as soon as the offset exceeds the leap count ("leap >= i")

    int canJump(int* nums, int numsSize)
    {
        int i, len = numsSize;
        int leap = nums[0];
    
        /* Loop while the array is valid, and there is a scope to move
        forward. If the present offset offers the longer leap, then pick
        the same */
        for (i = 0; i <= len - 1 && leap >= i && leap < len - 1; ++i)
            leap = (leap < (nums[i] + i)) ? nums[i] + i : leap;
    
        /* Return depending on the offset */
        return (leap >= len - 1) ? 1 : 0;
    }
    

    We can also do the scan in reverse, from the end of the array to the start while attempting to narrow the margins:

    int canJump(int* nums, int numsSize)
    {
        int i = numsSize - 1, pos = i;
    
        /* Scan backwards while updating the target position */
        for (i = numsSize - 1; i >= 0; --i)
            pos = (nums[i] + i >= pos) ? i : pos;
    
        /* Return TRUE if the target is the start of the array */
        return !pos;
    }
    

    Same logic, but done recursively:

    int jump(int* a, int n, int i, int pos)
    {
        /* Update the target position */
        pos = (a[i] + i) >= pos ? i : pos;
        if (i == 0) // return
            return !pos;
        return jump(a, n, i - 1, pos);
    }
    
    int canJump(int* nums, int numsSize)
    {
        return jump(nums, numsSize, numsSize - 1, numsSize - 1);
    }
    

Log in to reply
 

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