首页 > 代码库 > 45. Jump Game II

45. Jump Game II

一、题目

  1、描述

     技术分享

  2、题意

      给出一个数组,每一步最多前进该下标所表示的数值,求到达数组末尾所花费的最小步数。

 

二、解答

  1、思路:  

      贪心策略, 每步前进的地方使下一步能达到的地方最远,最后所得即为最小步数。

    /**
     *     本题用贪心法求解,
     *         贪心策略是每步前进的地方使下一步能达到的地方最远
     */
    public int jump(int[] nums) {

        if(nums.length <= 1){
            return 0;
        }
        int index,max = 0;
        int step = 0,i = 0; // i = 起始位置
        while(i < nums.length){
            //如果能直接一步走到最后,直接步数+1结束
            if(i + nums[i] >= nums.length - 1){
                step++;
                break;
            }
            
            max = 0;//每次都要初始化, 走的最大长度
            index = i+1;//记录索引,最少前进1步
            
            for(int j = i+1; j <= nums[i]+i; j++){//搜索最大步长内行走最远的那步  // j - i = 步长,
                if(max + i < nums[j] + j){
                    max = nums[j] + j-i;//记录最大值
                    index = j;//记录最大值索引
                }
            }
            i = index;//直接走到下一步能走最远的那步
            step++; // 步数
        }
        return step;
    
    }

 

45. Jump Game II