This is a little like BFS, do you think so?


  • 0
    C

    I think this is like BFS problem, such as level order traverse.

    We get the range of "current level" initially, then use "current level" calculate "next level". Then replace "next level" to "current level". And do this iteratively.

    Here is level order traverse,
    https://leetcode.com/problems/binary-tree-level-order-traversal/, I think they are same idea. Do you think so?

    public int jump(int[] nums) {
        //BFS, parse level by level
        int step = 0;
        int left=0,right=0; //get the first level
        while(right<nums.length-1&&left<=right){ //if there are still elements left.
            int oldright = right;
            for(int i=left;i<=oldright;i++){  //traverse current level
                if(nums[i]+i>right) right=nums[i]+i; //renew the next level.
            }
            left=oldright+1; //replace the current level by the next level
            step++; // count the level numbers
        }
        return step;
    }
    

Log in to reply
 

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