我正在调试以下问题并发布代码。想知道代码是否正确。我目前的疑问是，是否 i应该总是增加(在这一行 -- for (;i <= end; i++) )？
给定一个非负整数数组，您最初位于数组的第一个索引处。
数组中的每个元素代表您在该位置的最大跳跃长度。
您的目标是以最少的跳跃次数到达最后一个索引。
例如: 给定数组
A = [2,3,1,1,4], 到达最后一个索引的最少跳转次数为 2。 (从索引 0 跳 1 步到 1，然后跳 3 步到最后一个索引。)
class Solution {
public:
int jump(vector<int>& nums) {
int i = 0, n = nums.size(), step = 0, end = 0, maxend = 0;
while (end < n - 1) {
step++;
for (;i <= end; i++) {
maxend = max(maxend, i + nums[i]);
if (maxend >= n - 1) return step;
}
if(end == maxend) break;
end = maxend;
}
return n == 1 ? 0 : -1;
}
};
最佳答案
动态规划解决思路:O(n^2)
假设给定的数组是A[1..n]。从第 i 个位置，您可以跳转 1 或 2 或 3...A[i]。您已经计算了所有 j>=i && j<=n 的结果。所以现在
ans[i]=min(ans[i+j],ans[i]) where i+j<=n && j=1,2,...A[i]
这样你就可以计算一切。
O(n^2) 时间复杂度。
修改:O(n)
您也可以在 O(n) 中计算它。从一个位置，您将始终移动到具有最高 i+A[i] 值的位置。
我的意思是假设你在第 j 个位置。然后您接下来将移动到 j 位置，使得 j+A[j] 最大。
如果其中一个元素是最后一个元素，则跳转到最后一个元素。否则，跳转到具有最大 j+A[j] 的元素。
O(n) 解...
Jump 2 3 1 1 4
position 1 2 3 4 5
j+A[j] 3 5 4 5 9
^ . . . .
. ^ . . .
. . . . ^ ---> so 2 jumps.. :)
Jump 2 5 1 1 1 1 1 1
position 1 2 3 4 5 6 7 8
j+A[j] 3 7 4 5 6 7 8 9
^ . . . . . . .
. ^ . . . . . .
. . . . . . . ^ (Here it is giving 2 jumps)
关于c++ - 通过最大跳跃长度数组的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33227584/