Jump Game II
文章目录
Jump Game II 题解
题目描述
即计算从起始位置到达目的位置的最短路径长度。某点可达的下一点应在以此点为半径,此点的可达路长为半径的范围内。还有一个限制,所有点在同一直线上。
某点的可达路长存储在数组中,数组第一个元素存储起始位置的信息,最后一个元素存储目的位置的信息。
如:A = [2,3,1,1,4],一个最短路径为{A0}->{A1}->{A4},即最短路长为2。
题解
利用BFS(广度搜索)即可。时间复杂度为O(N),空间复杂度可优化至O(1)(因为不要求得出路径且所有点在同一直线上)。
代码
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() < 2)
return 0;
long i = 0, max = 0, step = 1, end = nums.size() - 1;
do {
long j = i;
for (i = max + 1; j < i; ++j) {
long tmp = j + nums[j];
if (tmp > max) {
if (tmp >= end)
return step;
max = tmp;
}
}
++step;
} while (i <= max);
return -1;
}
};
总结
主要应用了图论中广度搜索的思想。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论