h*****e
发帖数: 14 | 1 给定一个整数数组，初始位置是下标为0，里面的值代表可以向右跳跃的最大步数，问
能否跳出这个数组，如果可以的话，找出最小的跳出路径（就是给出数组下标）。
例如输入是：array = [5, 6, 0, 4, 2, 4, 1, 0, 0, 4]
初始状态在下标为0的地方，array[0]等于5，可以向右跳跃5下，也就是说可以跳跃到
array[1],array[2],array[3],array[4],array[5]。以此类推，直到跳出数组为止（一
定要跳出，停在数组的最后一个也是不行）。那么这个例子的最小跳出路径就是从下标
0开始， 跳到下标5， 下标9最后跳出数组。
题目还说输入的数组可能非常大。是不是用BFS来解这道题啊，有更好的方法吗？ | s******y
发帖数: 936 | 2 是jump game II 吗？
【在 h*****e 的大作中提到】
: 给定一个整数数组，初始位置是下标为0，里面的值代表可以向右跳跃的最大步数，问
: 能否跳出这个数组，如果可以的话，找出最小的跳出路径（就是给出数组下标）。
: 例如输入是：array = [5, 6, 0, 4, 2, 4, 1, 0, 0, 4]
: 初始状态在下标为0的地方，array[0]等于5，可以向右跳跃5下，也就是说可以跳跃到
: array[1],array[2],array[3],array[4],array[5]。以此类推，直到跳出数组为止（一
: 定要跳出，停在数组的最后一个也是不行）。那么这个例子的最小跳出路径就是从下标
: 0开始， 跳到下标5， 下标9最后跳出数组。
: 题目还说输入的数组可能非常大。是不是用BFS来解这道题啊，有更好的方法吗？
| e*****i
发帖数: 182 | 3 每一跳都有可能扩大一下范围。。。没扩大return -1.。。扩大了继续
【在 h*****e 的大作中提到】
: 给定一个整数数组，初始位置是下标为0，里面的值代表可以向右跳跃的最大步数，问
: 能否跳出这个数组，如果可以的话，找出最小的跳出路径（就是给出数组下标）。
: 例如输入是：array = [5, 6, 0, 4, 2, 4, 1, 0, 0, 4]
: 初始状态在下标为0的地方，array[0]等于5，可以向右跳跃5下，也就是说可以跳跃到
: array[1],array[2],array[3],array[4],array[5]。以此类推，直到跳出数组为止（一
: 定要跳出，停在数组的最后一个也是不行）。那么这个例子的最小跳出路径就是从下标
: 0开始， 跳到下标5， 下标9最后跳出数组。
: 题目还说输入的数组可能非常大。是不是用BFS来解这道题啊，有更好的方法吗？
| h*****e
发帖数: 14 | 4
对的，几乎是一样的，区别在于要跳出数组而不是最后一个
【在 s******y 的大作中提到】
: 是jump game II 吗？
| n*******1
发帖数: 145 | 5 跟jump ii 差不多 如果nextmax大于array范围的话就是结果 结果也许有多个 | d****n
发帖数: 12461 | 6 搞个相同尺寸的array，表示从0开始最少几步到达，开始都刷成INT_MAX
每次如果r[i]=k则把r[i]右边的若干位刷成min(r[i],k+1)，如果刷到超过数组长度就
表示成功。
【在 h*****e 的大作中提到】
: 给定一个整数数组，初始位置是下标为0，里面的值代表可以向右跳跃的最大步数，问
: 能否跳出这个数组，如果可以的话，找出最小的跳出路径（就是给出数组下标）。
: 例如输入是：array = [5, 6, 0, 4, 2, 4, 1, 0, 0, 4]
: 初始状态在下标为0的地方，array[0]等于5，可以向右跳跃5下，也就是说可以跳跃到
: array[1],array[2],array[3],array[4],array[5]。以此类推，直到跳出数组为止（一
: 定要跳出，停在数组的最后一个也是不行）。那么这个例子的最小跳出路径就是从下标
: 0开始， 跳到下标5， 下标9最后跳出数组。
: 题目还说输入的数组可能非常大。是不是用BFS来解这道题啊，有更好的方法吗？
| h*****e
发帖数: 14 | 7
这题略微有区别。是要输出最短的路径，不是true or false
【在 d****n 的大作中提到】
: 搞个相同尺寸的array，表示从0开始最少几步到达，开始都刷成INT_MAX
: 每次如果r[i]=k则把r[i]右边的若干位刷成min(r[i],k+1)，如果刷到超过数组长度就
: 表示成功。
| d****n
发帖数: 12461 | 8 在记录步数的同时记录跳跃起始点的下标就可以了。
一旦跳出就可以反过来打印路径。
【在 h*****e 的大作中提到】
:
: 这题略微有区别。是要输出最短的路径，不是true or false
| f**********t
发帖数: 1001 | 9 unsigned MinJump(vector jumps) {
unsigned res = UINT_MAX;
vector minJumps(jumps.size(), UINT_MAX);
if (jumps.empty()) {
return res;
}
minJumps[0] = 0;
for (size_t i = 0; i < jumps.size(); ++i) {
if (jumps[i] == 0 || minJumps[i] >= res) {
continue;
}
if (i + jumps[i] >= jumps.size()) {
res = min(res, minJumps[i] + 1);
continue;
}
for (size_t k = jumps[i]; k != 0; --k) {
minJumps[i + k] = min(minJumps[i + k], minJumps[i] + 1);
}
}
return res;
}
void MinJumpTest() {
cout << "MinJump: " << MinJump({5, 6, 0, 4, 2, 4, 1, 0, 0, 4})
<< ' ' << MinJump({0}) << ' ' << MinJump({1}) << endl;
} | f**********t
发帖数: 1001 | 10 unsigned MinJump(vector jumps) {
vector minJumps(jumps.size(), UINT_MAX);
if (jumps.empty()) {
return UINT_MAX;
}
minJumps[0] = 0;
if (jumps[0] >= jumps.size()) {
return 1;
}
for (size_t i = 0; i < jumps.size(); ++i) {
if (jumps[i] == 0) {
continue;
}
for (size_t k = jumps[i]; k != 0; --k) {
minJumps[i + k] = min(minJumps[i + k], minJumps[i] + 1);
if (jumps[i + k] + i + k >= jumps.size()) {
return minJumps[i + k] + 1;
}
}
}
return UINT_MAX;
}
void MinJumpTest() {
cout << "MinJump: " << MinJump({5, 6, 0, 4, 2, 4, 1, 0, 0, 4})
<< ' ' << MinJump({0}) << ' ' << MinJump({1}) << endl;
} |
|
