首页 > 其他 > 详细

45. Jump Game II

时间:2018-03-10 22:39:01      阅读:190      评论:0      收藏:0      [点我收藏+]

45. Jump Game II

题目

 Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

解析

  • 运用bfs的思想,更新每一层的start,end,判断是否到达数组结尾,返回bfs的层数
// 45. Jump Game II
class Solution_45 {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), step = 0;
        int start = 0, end = 0; //bfs每一层的开始结束位置 //每层结束更新
        while (end<n-1) //end<n时,end=n-1就可以结束了
        {
            step++;
            int maxend = end + 1;
            for (int i = start; i <= end;i++)
            {
                if (i+nums[i]>n)
                {
                    return step;
                }
                maxend = max(i+nums[i],maxend);
            }
            start = end + 1;
            end = maxend;
        }
        return step;
    }

    int jump(int A[], int n) {

        vector<int> vec(A,A+n);
        return jump(vec);
    }
};

题目来源

45. Jump Game II

原文:https://www.cnblogs.com/ranjiewen/p/8542163.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!