如何在 O(n) 时间内找到到达数组末尾的最少跳转次数
How to find minimum number of jumps to reach the end of the array in O(n) time
Question
Given an array of integers where each element represents the max number of steps that can be made forward from that element.
Write a function to return the minimum number of jumps to reach the
end of the array (starting from the first element). If an element is
0, then cannot move through that element.
Example
Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 ->9)
从 Dynamic Programming approach to other linear approaches. I am not able to understand the approach which is said to linear in time. HERE 中找到了多种方法 link 提出了线性方法。
完全看不懂。我能理解的是，作者建议采用贪婪的方法，看看我们是否到达终点。如果没有，则回溯？
网站上提出的解决方案的时间复杂度是线性的，因为您只迭代数组一次。该算法通过使用一些巧妙的技巧避免了我提出的解决方案的内部迭代。
变量maxReach始终存储数组中最大可达位置。 jump 存储到达该位置所需的跳跃次数。 step 存储我们仍然可以走的步数（并在第一个数组位置用步数初始化）
在迭代过程中，上述值更新如下：
首先我们测试是否已经到达数组的末尾，在这种情况下我们只需要 return jump 变量。
接下来我们更新最大可达位置。这等于 maxReach 和 i+A[i] 中的最大值（我们从当前位置可以采取的步数）。
我们用了一步到达当前索引，因此必须减少 steps。
如果没有剩余步数（即 steps=0，那么我们一定使用了跳跃。因此增加 jump。因为我们知道有可能以某种方式到达 maxReach ，我们将步数初始化为从位置 i.
到达 maxReach 的步数
public class Solution {
public int jump(int[] A) {
if (A.length <= 1)
return 0;
int maxReach = A[0];
int step = A[0];
int jump = 1;
for (int i = 1; i < A.length; i++) {
if (i == A.length - 1)
return jump;
if (i + A[i] > maxReach)
maxReach = i + A[i];
step--;
if (step == 0) {
jump++;
step = maxReach - i;
}
}
return jump;
}
}
示例：
int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0]; // A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0]; // A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1; // we will always need to take at least one jump.
/*************************************
* First iteration (i=1)
************************************/
if (i + A[i] > maxReach) // 1+3 > 1, we can reach further now!
maxReach = i + A[i] // maxReach = 4, we now know that index 4 is the largest index we can reach.
step-- // we used a step to get to this index position, so we decrease it
if (step == 0) {
++jump; // we ran out of steps, this means that we have made a jump
// this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
// but we can continue with the 3 steps received at array position 2.
steps = maxReach-i // we know that by some combination of 2 jumps, we can reach position 4.
// therefore in the current situation, we can minimaly take 3
// more steps to reach position 4 => step = 3
}
/*************************************
* Second iteration (i=2)
************************************/
if (i + A[i] > maxReach) // 2+5 > 4, we can reach further now!
maxReach = i + A[i] // maxReach = 7, we now know that index 7 is the largest index we can reach.
step-- // we used a step so now step = 2
if (step==0){
// step
}
/*************************************
* Second iteration (i=3)
************************************/
if (i + A[i] > maxReach) // 3+8 > 7, we can reach further now!
maxReach = i + A[i] // maxReach = 11, we now know that index 11 is the largest index we can reach.
step-- // we used a step so now step = 1
if (step==0){
// step
}
/*************************************
* Third iteration (i=4)
************************************/
if (i + A[i] > maxReach) // 4+9 > 11, we can reach further now!
maxReach = i + A[i] // maxReach = 13, we now know that index 13 is the largest index we can reach.
step-- // we used a step so now step = 0
if (step == 0) {
++jump; // we ran out of steps, this means that we have made a jump.
// jump is now equal to 3.
steps = maxReach-i // there exists a combination of jumps to reach index 13, so
// we still have a budget of 9 steps
}
/************************************
* remaining iterations
***********************************
// nothing much changes now until we reach the end of the array.
我的次优算法在 O(nk) 时间内工作，其中 n 数组中的元素数和 k 数组中最大的元素，并使用内部循环遍历 array[i]。下面的算法避免了这个循环。
代码
public static int minimum_steps(int[] array) {
int[] min_to_end = new int[array.length];
for (int i = array.length - 2; i >= 0; --i) {
if (array[i] <= 0)
min_to_end[i] = Integer.MAX_VALUE;
else {
int minimum = Integer.MAX_VALUE;
for (int k = 1; k <= array[i]; ++k) {
if (i + k < array.length)
minimum = Math.min(min_to_end[i+k], minimum);
else
break;
}
min_to_end[i] = minimum + 1;
}
}
return min_to_end[0];
}
这是另一个线性解决方案。该代码比 leet 代码 link 中建议的代码长，但我认为它更容易理解。它基于两个观察：到达 i + 1 位置所需的步数永远不会少于到达 i 位置所需的步数并且每个元素每个元素分配其值 + 1到 i + 1 ... i + a[i] 段。
public class Solution {
public int jump(int[] a) {
int n = a.length;
// count[i] is the number of "open" segments with value i
int[] count = new int[n];
// the number of steps to reach the i-th position
int[] dp = new int[n];
Arrays.fill(dp, n);
// toDelete[i] is the list of values of segments
// that close in the i-th position
ArrayList<Integer>[] toDelete = new ArrayList[n];
for (int i = 0; i < n; i++)
toDelete[i] = new ArrayList<>();
// Initially, the value is 0(for the first element).
toDelete[0].add(0);
int min = 0;
count[0]++;
for (int i = 0; i < n; i++) {
// Finds the new minimum. It uses the fact that it cannot decrease.
while (min < n && count[min] == 0)
min++;
// If min == n, then there is no path. So we can stop.
if (min == n)
break;
dp[i] = min;
if (dp[i] + 1 < n) {
// Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
count[dp[i] + 1]++;
if (i + a[i] < n)
toDelete[i + a[i]].add(dp[i] + 1);
}
// Processes closing segments in this position.
for (int deleted : toDelete[i])
count[deleted]--;
}
return dp[n - 1];
}
}
复杂度分析：
toDelete 个列表中的元素总数为 O(n)。之所以如此，是因为在每个位置 i 最多添加一个元素。这就是为什么处理所有 toDelete 列表中的所有元素需要线性时间。
min值只能增加。这就是为什么内部 while 循环总共最多进行 n 次迭代的原因。
外部 for 循环显然进行了 n 次迭代。因此，时间复杂度是线性的。
晚了几年，但这是另一个对我有意义的 O(n) 解决方案。
/// <summary>
///
/// The actual problem is if it's worth not to jump to the rightmost in order to land on a value that pushes us further than if we jumped on the rightmost.
///
/// However , if we approach the problem from the end, we go end to start,always jumping to the leftmost
///
/// with this approach , these is no point in not jumping to the leftmost from end to start , because leftmost will always be the index that has the leftmost leftmost :) , so always choosing leftmost is the fastest way to reach start
///
/// </summary>
/// <param name="arr"></param>
static void Jumps (int[] arr)
{
var LeftMostReacher = new int[arr.Length];
//let's see , for each element , how far back can it be reached from
LeftMostReacher[0] = -1; //the leftmost reacher of 0 is -1
var unReachableIndex = 1; //this is the first index that hasn't been reached by anyone yet
//we use this unReachableIndex var so each index's leftmost reacher is the first that was able to jump to it . Once flagged by the first reacher , new reachers can't be the leftmost anymore so they check starting from unReachableIndex
// this design insures that the inner loop never flags the same index twice , so the runtime of these two loops together is O(n)
for (int i = 0; i < arr.Length; i++)
{
int maxReach = i + arr[i];
for (; unReachableIndex <= maxReach && unReachableIndex < arr.Length; unReachableIndex++)
{
LeftMostReacher[unReachableIndex] = i;
}
}
// we just go back from the end and then reverse the path
int index = LeftMostReacher.Length - 1;
var st = new Stack<int>();
while (index != -1)
{
st.Push(index);
index = LeftMostReacher[index];
}
while (st.Count != 0)
{
Console.Write(arr[st.Pop()] + " ");
}
Console.WriteLine();
}
static void Main ()
{
var nrs = new[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
Jumps(nrs);
}
这是关于上述问题的贪婪方法的基本直觉，其余是代码要求。
给定的数组是输入：a[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}。
现在我们从第一个元素开始，即 i=0 和 a[i] = 1。看到这一点，我们最多可以进行大小为 1 的跳跃，所以因为我们别无选择，所以我们实现这一步。
目前我们在 i=1 和 a[i]=3。所以我们目前可以进行大小为 3 的跳跃，但是我们考虑了我们可以从当前位置进行的所有可能跳跃并达到（数组）边界内的最大距离。那么我们的选择是什么？我们可以跳 1 步、2 步或 3 步。因此，我们从当前位置调查每个大小跳跃，并选择可以使我们最大程度地进入数组的那个。
一旦我们决定坚持哪一个，我们就会采用跳跃大小并更新我们到目前为止的跳跃次数，以及我们最多可以到达的位置以及我们现在有多少步来决定我们的下一步行动.就是这样。这就是我们最终select线性遍历数组的最佳选择。
所以这就是您可能正在寻找的算法的基本思想，接下来是对其进行编码以使算法正常工作。干杯！
希望有人能穿越时空发现直觉有用！！ :) :P
"Years late to the party" @Vasilescu Andrei - 说得好。有时我觉得我们是时间旅行者。
到达终点的最少跳转次数问题的简单 python 代码。
ar=[1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
minJumpIdx=0
res=[0]*len(ar)
i=1
while(i<len(ar) and i>minJumpIdx):
if minJumpIdx+ar[minJumpIdx]>=i:
res[i]=res[minJumpIdx]+1
i+=1
else:
minJumpIdx+=1
if res[-1]==0:
print(-1)
else:
print(res[-1])
好吧，我花了很多时间来思考 O(n) 算法，我会尽量用最简单的方式解释逻辑：
在数组中的每个 "i"，你知道那个值是什么 currentFarthest 值，你可以达到，还有 currentEnd 值，每当你达到 currentEnd 值，你就知道它的时间跳转并用 currentFarthest 更新 currentEnd。
下图可能有帮助：
我用 Python 完成了这个。
使用简单术语的不太复杂的代码。这可能对你有帮助。
def minJump(a):
end=len(a)
count=0
i=a[0]
tempList1=a
while(i<=end):
if(i==0):
return 0
tempList1=a[count+1:count+i+1]
max_index=a.index(max(tempList1))
count+=1
i=a[max_index]
end=end-max_index
return count+1
static void minJumps(int a[] , int n)
{
int dp[] = new int[n];
dp[0] = 0; //As the min jumps needed to get to first index is zero only.
//Fill the rest of the array with INT_MAX val so we can make math.min comparisions.
for(int i=1;i<n;i++)
dp[i] = Integer.MAX_VALUE;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{ //If we have enough jumps from the position j to reach i.
if(j+a[j]>=i)
{ //Take the min of current stored value & jumps req to
//reach i from j by getting jumps req to reach j plus 1.
//(Plus 1 because since we have enough jumps to reach 1 from j we
//simply add 1 by taking the jumps required to reach j.)
dp[i] = Math.min(dp[i],dp[j]+1);
}
}
}
//If first element has zero jumps in store or if the final jumps value
//becomes MAX value because there's an element in between which gives zero
//jumps.
if(a[0]==0 || dp[n-1] == Integer.MAX_VALUE )
System.out.println("-1");
else System.out.println(dp[n-1]);
}
到目前为止这里的许多答案都很棒，但我觉得我可以帮助解释 为什么 该算法是正确的以及它背后的直觉。
我喜欢这个问题，因为这是一个直观的动态规划方法在O(n^2)最坏情况下运行秒，贪婪方法（激发这个问题的方法）在 O(n) 最坏情况下 运行s（它实际上只访问数组的每个元素一次）。这个算法对我来说也有点让人想起Dijkstra的算法，它解决了另一个单源最短路径问题，也是贪婪的。
首先，请记住问题陈述中 A[i] 持有您可以从该索引跳转到的最大位置，但是您 可以 采取 从i更短的跳跃如果A[i]>1，那么从i=0的最短跳跃序列可能是比更短的跳跃每个索引允许的内容。这很重要，因为您会看到该算法从不考虑那些较小的跳跃或它们的位置显式。
其次，将您提到的算法想象成一个让自己 "strands of rope" (steps = maxReach - i;) 到达终点并消耗这条绳子 (steps--;) 因为它试图在数组中前进。
第三，请注意该算法 不是 跟踪可能属于 a 的特定索引 i 最短输入数组A从头到尾的序列。事实上，该算法仅在"runs out of rope"（从前一根绳子开始）时增加变量jump（它给自己一根新的绳子），这样它就可以在主循环中不断迭代到"try" 到达终点。
更具体地说，要使算法正确，它需要：
从每个位置 i 跟踪 的 "how far it can reach" (maxReach)，因为它在数组中向前移动.请注意，如果当时已经很清楚到达新位置 will require[，则每个位置都会更新此数量 even =67=] 它需要更多 "jumps" 因为你超过了你之前给自己的步数（即你 运行 失去了绳索），even 如果没有最短路径实际上会访问该元素。这些更新的目标是确定下一次跳跃可以达到多远，以便在用尽当前跳跃后它可以给自己提供那么多绳子。
帐户 最少 次跳转（jumps) 你 必须 如果你想继续遍历数组直到结束，因为你 运行 脱离绳索 (steps)前一串。
您链接的算法，供参考：
public class Solution {
public int jump(int[] A) {
if (A.length <= 1)
return 0;
int maxReach = A[0];
int step = A[0];
int jump = 1;
for (int i = 1; i < A.length; i++) {
if (i == A.length - 1)
return jump;
if (i + A[i] > maxReach)
maxReach = i + A[i];
step--;
if (step == 0) {
jump++;
step = maxReach - i;
}
}
return jump;
}
}
另一个O(n)的解，最好的解释
以下解决方案提供了 o(n) 时间复杂度
为了解决到达数组末尾的最小跳跃，
对于每个跳跃索引，我们考虑需要评估索引中相应的步长值，并使用索引值将数组分成子部分并找出覆盖索引的最大步长。
下面的代码和解释会让你思路清晰：
在每个子数组中找出最大距离覆盖索引作为数组的第一部分，第二个数组
Input Array : {1, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> index position starts with 0
Steps :
Initial step is considering the first index and incrementing the jump
Jump = 1
1, { 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> 1 is considered as a first jump
next step
From the initial step there is only one step to move so
Jump = 2
1,3, { 5, 9, 6,2, 6, 7, 6, 8, 9} -> 1 is considered as a first jump
next step
Now we have a flexibility to choose any of {5,9,6} because of last step says we can move upto 3 steps
Consider it as a subarray, evaluate the max distance covers with each index position
As {5,9,6} index positions are {2,3,4}
so the total farther steps we can cover:
{7,12,10} -> we can assume it as {7,12} & {10} are 2 sub arrays where left part of arrays says max distance covered with 2 steps and right side array says max steps cover with remaining values
next step:
Considering the maximum distanc covered in first array we iterate the remaining next elements
1,3,9 {6,2, 6, 7, 6, 8, 9}
From above step ww already visited the 4th index we continue with next 5th index as explained above
{6,2, 6, 7, 6, 8, 9} index positions {4,5,6,7,8,9,10}
{10,7,12,14,14,17,19}
Max step covers here is 19 which corresponding index is 10
代码
//
// Created by Praveen Kanike on 07/12/20.
//
#include <iostream>
using namespace std;
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
// The number of jumps needed to
// reach the starting index is 0
if (n <= 1)
return 0;
// Return -1 if not possible to jump
if (arr[0] == 0)
return -1;
// stores the number of jumps
// necessary to reach that maximal
// reachable position.
int jump = 1;
// stores the subarray last index
int subArrEndIndex = arr[0];
int i = 1;
//maximum steps covers in first half of sub array
int subArrFistHalfMaxSteps = 0;
//maximum steps covers in second half of sub array
int subArrSecondHalfMaxSteps =0;
// Start traversing array
for (i = 1; i < n;) {
subArrEndIndex = i+subArrEndIndex;
// Check if we have reached the end of the array
if(subArrEndIndex >= n)
return jump;
int firstHalfMaxStepIndex = 0;
//iterate the sub array and find out the maxsteps cover index
for(;i<subArrEndIndex;i++)
{
int stepsCanCover = arr[i]+i;
if(subArrFistHalfMaxSteps < stepsCanCover)
{
subArrFistHalfMaxSteps = stepsCanCover;
subArrSecondHalfMaxSteps = 0;
firstHalfMaxStepIndex = i;
}
else if(subArrSecondHalfMaxSteps < stepsCanCover)
{
subArrSecondHalfMaxSteps = stepsCanCover;
}
}
if(i > subArrFistHalfMaxSteps)
return -1;
jump++;
//next subarray end index and so far calculated sub array max step cover value
subArrEndIndex = arr[firstHalfMaxStepIndex];
subArrFistHalfMaxSteps = subArrSecondHalfMaxSteps;
}
return -1;
}
// Driver program to test above function
int main()
{
int arr[] = {100, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9};
int size = sizeof(arr) / sizeof(int);
// Calling the minJumps function
cout << ("Minimum number of jumps to reach end is %d ",
minJumps(arr, size));
return 0;
}
以防万一您需要为贪婪方法编写 python 解决方案，此代码将帮助您解决上述问题:)
def minJumps(self, arr, n):
#code here
if(n <= 1):
return(0)
if(arr[0] == 0):
return -1
maxrange, step = arr[0], arr[0]
jumps = 1
for i in range(1,n):
if (i == len(arr) - 1):
return jumps
maxrange = max(maxrange, i+arr[i])
step -= 1
if(step == 0):
jumps += 1
if(i>=maxrange):
return -1
step = maxrange - i
return(jumps)
这是另一种解决方案。在此解决方案中，最坏情况复杂度为 O(n)，而平均情况复杂度小于 O(n)。我不知道如何进行平均案例复杂性分析。所以，我无法说出确切的平均案例复杂度。但是，是的，它比 99.22% 的 leet 代码提交更快。
def minJumps(self, arr, n):
current_w=0 # current_index
last_w=n-1 # last_index
max_reach=0 # value of index upto which we have analysed array for optimum solution
max_jumps=arr[0] # maximum jumps that can be taken from a current_index
hop=0 # total jumps
while current_w<last_w:
max_jumps=arr[current_w]
if max_jumps==0:
return -1
if max_jumps==1:
max_reach=max_jumps+current_w
current_w+=1
elif max_jumps<last_w-current_w: # if maximum steps does not reach to last index
can_jump_to=arr[max_reach+1:max_jumps+current_w+1] # subarray in which we have to search for a wall,jumping to which can take us to required solution
jump_to=max(range(len(can_jump_to)),key=lambda x: x+can_jump_to[x])+max_reach+1 # finding index of wall whoose definition mentioned in above comment
max_reach=max_jumps+current_w #updating max_reach
current_w=jump_to #updating current position
else:
current_w=last_w
hop+=1
return hop
Question
Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.
Example
Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 ->9)
从 Dynamic Programming approach to other linear approaches. I am not able to understand the approach which is said to linear in time. HERE 中找到了多种方法 link 提出了线性方法。
完全看不懂。我能理解的是，作者建议采用贪婪的方法，看看我们是否到达终点。如果没有，则回溯？
网站上提出的解决方案的时间复杂度是线性的，因为您只迭代数组一次。该算法通过使用一些巧妙的技巧避免了我提出的解决方案的内部迭代。
变量maxReach始终存储数组中最大可达位置。 jump 存储到达该位置所需的跳跃次数。 step 存储我们仍然可以走的步数（并在第一个数组位置用步数初始化）
在迭代过程中，上述值更新如下：
首先我们测试是否已经到达数组的末尾，在这种情况下我们只需要 return jump 变量。
接下来我们更新最大可达位置。这等于 maxReach 和 i+A[i] 中的最大值（我们从当前位置可以采取的步数）。
我们用了一步到达当前索引，因此必须减少 steps。
如果没有剩余步数（即 steps=0，那么我们一定使用了跳跃。因此增加 jump。因为我们知道有可能以某种方式到达 maxReach ，我们将步数初始化为从位置 i.
maxReach 的步数
public class Solution {
public int jump(int[] A) {
if (A.length <= 1)
return 0;
int maxReach = A[0];
int step = A[0];
int jump = 1;
for (int i = 1; i < A.length; i++) {
if (i == A.length - 1)
return jump;
if (i + A[i] > maxReach)
maxReach = i + A[i];
step--;
if (step == 0) {
jump++;
step = maxReach - i;
}
}
return jump;
}
}
示例：
int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0]; // A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0]; // A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1; // we will always need to take at least one jump.
/*************************************
* First iteration (i=1)
************************************/
if (i + A[i] > maxReach) // 1+3 > 1, we can reach further now!
maxReach = i + A[i] // maxReach = 4, we now know that index 4 is the largest index we can reach.
step-- // we used a step to get to this index position, so we decrease it
if (step == 0) {
++jump; // we ran out of steps, this means that we have made a jump
// this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
// but we can continue with the 3 steps received at array position 2.
steps = maxReach-i // we know that by some combination of 2 jumps, we can reach position 4.
// therefore in the current situation, we can minimaly take 3
// more steps to reach position 4 => step = 3
}
/*************************************
* Second iteration (i=2)
************************************/
if (i + A[i] > maxReach) // 2+5 > 4, we can reach further now!
maxReach = i + A[i] // maxReach = 7, we now know that index 7 is the largest index we can reach.
step-- // we used a step so now step = 2
if (step==0){
// step
}
/*************************************
* Second iteration (i=3)
************************************/
if (i + A[i] > maxReach) // 3+8 > 7, we can reach further now!
maxReach = i + A[i] // maxReach = 11, we now know that index 11 is the largest index we can reach.
step-- // we used a step so now step = 1
if (step==0){
// step
}
/*************************************
* Third iteration (i=4)
************************************/
if (i + A[i] > maxReach) // 4+9 > 11, we can reach further now!
maxReach = i + A[i] // maxReach = 13, we now know that index 13 is the largest index we can reach.
step-- // we used a step so now step = 0
if (step == 0) {
++jump; // we ran out of steps, this means that we have made a jump.
// jump is now equal to 3.
steps = maxReach-i // there exists a combination of jumps to reach index 13, so
// we still have a budget of 9 steps
}
/************************************
* remaining iterations
***********************************
// nothing much changes now until we reach the end of the array.
我的次优算法在 O(nk) 时间内工作，其中 n 数组中的元素数和 k 数组中最大的元素，并使用内部循环遍历 array[i]。下面的算法避免了这个循环。
代码
public static int minimum_steps(int[] array) {
int[] min_to_end = new int[array.length];
for (int i = array.length - 2; i >= 0; --i) {
if (array[i] <= 0)
min_to_end[i] = Integer.MAX_VALUE;
else {
int minimum = Integer.MAX_VALUE;
for (int k = 1; k <= array[i]; ++k) {
if (i + k < array.length)
minimum = Math.min(min_to_end[i+k], minimum);
else
break;
}
min_to_end[i] = minimum + 1;
}
}
return min_to_end[0];
}
这是另一个线性解决方案。该代码比 leet 代码 link 中建议的代码长，但我认为它更容易理解。它基于两个观察：到达 i + 1 位置所需的步数永远不会少于到达 i 位置所需的步数并且每个元素每个元素分配其值 + 1到 i + 1 ... i + a[i] 段。
public class Solution {
public int jump(int[] a) {
int n = a.length;
// count[i] is the number of "open" segments with value i
int[] count = new int[n];
// the number of steps to reach the i-th position
int[] dp = new int[n];
Arrays.fill(dp, n);
// toDelete[i] is the list of values of segments
// that close in the i-th position
ArrayList<Integer>[] toDelete = new ArrayList[n];
for (int i = 0; i < n; i++)
toDelete[i] = new ArrayList<>();
// Initially, the value is 0(for the first element).
toDelete[0].add(0);
int min = 0;
count[0]++;
for (int i = 0; i < n; i++) {
// Finds the new minimum. It uses the fact that it cannot decrease.
while (min < n && count[min] == 0)
min++;
// If min == n, then there is no path. So we can stop.
if (min == n)
break;
dp[i] = min;
if (dp[i] + 1 < n) {
// Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
count[dp[i] + 1]++;
if (i + a[i] < n)
toDelete[i + a[i]].add(dp[i] + 1);
}
// Processes closing segments in this position.
for (int deleted : toDelete[i])
count[deleted]--;
}
return dp[n - 1];
}
}
复杂度分析：
toDelete个列表中的元素总数为O(n)。之所以如此，是因为在每个位置i最多添加一个元素。这就是为什么处理所有toDelete列表中的所有元素需要线性时间。min值只能增加。这就是为什么内部while循环总共最多进行n次迭代的原因。外部
for循环显然进行了n次迭代。因此，时间复杂度是线性的。
晚了几年，但这是另一个对我有意义的 O(n) 解决方案。
/// <summary>
///
/// The actual problem is if it's worth not to jump to the rightmost in order to land on a value that pushes us further than if we jumped on the rightmost.
///
/// However , if we approach the problem from the end, we go end to start,always jumping to the leftmost
///
/// with this approach , these is no point in not jumping to the leftmost from end to start , because leftmost will always be the index that has the leftmost leftmost :) , so always choosing leftmost is the fastest way to reach start
///
/// </summary>
/// <param name="arr"></param>
static void Jumps (int[] arr)
{
var LeftMostReacher = new int[arr.Length];
//let's see , for each element , how far back can it be reached from
LeftMostReacher[0] = -1; //the leftmost reacher of 0 is -1
var unReachableIndex = 1; //this is the first index that hasn't been reached by anyone yet
//we use this unReachableIndex var so each index's leftmost reacher is the first that was able to jump to it . Once flagged by the first reacher , new reachers can't be the leftmost anymore so they check starting from unReachableIndex
// this design insures that the inner loop never flags the same index twice , so the runtime of these two loops together is O(n)
for (int i = 0; i < arr.Length; i++)
{
int maxReach = i + arr[i];
for (; unReachableIndex <= maxReach && unReachableIndex < arr.Length; unReachableIndex++)
{
LeftMostReacher[unReachableIndex] = i;
}
}
// we just go back from the end and then reverse the path
int index = LeftMostReacher.Length - 1;
var st = new Stack<int>();
while (index != -1)
{
st.Push(index);
index = LeftMostReacher[index];
}
while (st.Count != 0)
{
Console.Write(arr[st.Pop()] + " ");
}
Console.WriteLine();
}
static void Main ()
{
var nrs = new[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
Jumps(nrs);
}
这是关于上述问题的贪婪方法的基本直觉，其余是代码要求。
给定的数组是输入：a[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}。
现在我们从第一个元素开始，即 i=0 和 a[i] = 1。看到这一点，我们最多可以进行大小为 1 的跳跃，所以因为我们别无选择，所以我们实现这一步。
目前我们在 i=1 和 a[i]=3。所以我们目前可以进行大小为 3 的跳跃，但是我们考虑了我们可以从当前位置进行的所有可能跳跃并达到（数组）边界内的最大距离。那么我们的选择是什么？我们可以跳 1 步、2 步或 3 步。因此，我们从当前位置调查每个大小跳跃，并选择可以使我们最大程度地进入数组的那个。
一旦我们决定坚持哪一个，我们就会采用跳跃大小并更新我们到目前为止的跳跃次数，以及我们最多可以到达的位置以及我们现在有多少步来决定我们的下一步行动.就是这样。这就是我们最终select线性遍历数组的最佳选择。 所以这就是您可能正在寻找的算法的基本思想，接下来是对其进行编码以使算法正常工作。干杯！
希望有人能穿越时空发现直觉有用！！ :) :P "Years late to the party" @Vasilescu Andrei - 说得好。有时我觉得我们是时间旅行者。
到达终点的最少跳转次数问题的简单 python 代码。
ar=[1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
minJumpIdx=0
res=[0]*len(ar)
i=1
while(i<len(ar) and i>minJumpIdx):
if minJumpIdx+ar[minJumpIdx]>=i:
res[i]=res[minJumpIdx]+1
i+=1
else:
minJumpIdx+=1
if res[-1]==0:
print(-1)
else:
print(res[-1])
好吧，我花了很多时间来思考 O(n) 算法，我会尽量用最简单的方式解释逻辑：
在数组中的每个 "i"，你知道那个值是什么 currentFarthest 值，你可以达到，还有 currentEnd 值，每当你达到 currentEnd 值，你就知道它的时间跳转并用 currentFarthest 更新 currentEnd。
下图可能有帮助：
我用 Python 完成了这个。 使用简单术语的不太复杂的代码。这可能对你有帮助。
def minJump(a):
end=len(a)
count=0
i=a[0]
tempList1=a
while(i<=end):
if(i==0):
return 0
tempList1=a[count+1:count+i+1]
max_index=a.index(max(tempList1))
count+=1
i=a[max_index]
end=end-max_index
return count+1
static void minJumps(int a[] , int n)
{
int dp[] = new int[n];
dp[0] = 0; //As the min jumps needed to get to first index is zero only.
//Fill the rest of the array with INT_MAX val so we can make math.min comparisions.
for(int i=1;i<n;i++)
dp[i] = Integer.MAX_VALUE;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{ //If we have enough jumps from the position j to reach i.
if(j+a[j]>=i)
{ //Take the min of current stored value & jumps req to
//reach i from j by getting jumps req to reach j plus 1.
//(Plus 1 because since we have enough jumps to reach 1 from j we
//simply add 1 by taking the jumps required to reach j.)
dp[i] = Math.min(dp[i],dp[j]+1);
}
}
}
//If first element has zero jumps in store or if the final jumps value
//becomes MAX value because there's an element in between which gives zero
//jumps.
if(a[0]==0 || dp[n-1] == Integer.MAX_VALUE )
System.out.println("-1");
else System.out.println(dp[n-1]);
}
到目前为止这里的许多答案都很棒，但我觉得我可以帮助解释 为什么 该算法是正确的以及它背后的直觉。
我喜欢这个问题，因为这是一个直观的动态规划方法在O(n^2)最坏情况下运行秒，贪婪方法（激发这个问题的方法）在 O(n) 最坏情况下 运行s（它实际上只访问数组的每个元素一次）。这个算法对我来说也有点让人想起Dijkstra的算法，它解决了另一个单源最短路径问题，也是贪婪的。
首先，请记住问题陈述中 A[i] 持有您可以从该索引跳转到的最大位置，但是您 可以 采取 从i更短的跳跃如果A[i]>1，那么从i=0的最短跳跃序列可能是比更短的跳跃每个索引允许的内容。这很重要，因为您会看到该算法从不考虑那些较小的跳跃或它们的位置显式。
其次，将您提到的算法想象成一个让自己 "strands of rope" (steps = maxReach - i;) 到达终点并消耗这条绳子 (steps--;) 因为它试图在数组中前进。
第三，请注意该算法 不是 跟踪可能属于 a 的特定索引 i 最短输入数组A从头到尾的序列。事实上，该算法仅在"runs out of rope"（从前一根绳子开始）时增加变量jump（它给自己一根新的绳子），这样它就可以在主循环中不断迭代到"try" 到达终点。
更具体地说，要使算法正确，它需要：
从每个位置
i跟踪 的 "how far it can reach" (maxReach)，因为它在数组中向前移动.请注意，如果当时已经很清楚到达新位置 will require[，则每个位置都会更新此数量 even =67=] 它需要更多 "jumps" 因为你超过了你之前给自己的步数（即你 运行 失去了绳索），even 如果没有最短路径实际上会访问该元素。这些更新的目标是确定下一次跳跃可以达到多远，以便在用尽当前跳跃后它可以给自己提供那么多绳子。帐户 最少 次跳转（
jumps) 你 必须 如果你想继续遍历数组直到结束，因为你 运行 脱离绳索 (steps)前一串。
您链接的算法，供参考：
public class Solution {
public int jump(int[] A) {
if (A.length <= 1)
return 0;
int maxReach = A[0];
int step = A[0];
int jump = 1;
for (int i = 1; i < A.length; i++) {
if (i == A.length - 1)
return jump;
if (i + A[i] > maxReach)
maxReach = i + A[i];
step--;
if (step == 0) {
jump++;
step = maxReach - i;
}
}
return jump;
}
}
另一个O(n)的解，最好的解释 以下解决方案提供了 o(n) 时间复杂度 为了解决到达数组末尾的最小跳跃， 对于每个跳跃索引，我们考虑需要评估索引中相应的步长值，并使用索引值将数组分成子部分并找出覆盖索引的最大步长。
下面的代码和解释会让你思路清晰：
在每个子数组中找出最大距离覆盖索引作为数组的第一部分，第二个数组
Input Array : {1, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> index position starts with 0
Steps :
Initial step is considering the first index and incrementing the jump
Jump = 1
1, { 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} -> 1 is considered as a first jump
next step
From the initial step there is only one step to move so
Jump = 2
1,3, { 5, 9, 6,2, 6, 7, 6, 8, 9} -> 1 is considered as a first jump
next step
Now we have a flexibility to choose any of {5,9,6} because of last step says we can move upto 3 steps
Consider it as a subarray, evaluate the max distance covers with each index position
As {5,9,6} index positions are {2,3,4}
so the total farther steps we can cover:
{7,12,10} -> we can assume it as {7,12} & {10} are 2 sub arrays where left part of arrays says max distance covered with 2 steps and right side array says max steps cover with remaining values
next step:
Considering the maximum distanc covered in first array we iterate the remaining next elements
1,3,9 {6,2, 6, 7, 6, 8, 9}
From above step ww already visited the 4th index we continue with next 5th index as explained above
{6,2, 6, 7, 6, 8, 9} index positions {4,5,6,7,8,9,10}
{10,7,12,14,14,17,19}
Max step covers here is 19 which corresponding index is 10
代码
//
// Created by Praveen Kanike on 07/12/20.
//
#include <iostream>
using namespace std;
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
// The number of jumps needed to
// reach the starting index is 0
if (n <= 1)
return 0;
// Return -1 if not possible to jump
if (arr[0] == 0)
return -1;
// stores the number of jumps
// necessary to reach that maximal
// reachable position.
int jump = 1;
// stores the subarray last index
int subArrEndIndex = arr[0];
int i = 1;
//maximum steps covers in first half of sub array
int subArrFistHalfMaxSteps = 0;
//maximum steps covers in second half of sub array
int subArrSecondHalfMaxSteps =0;
// Start traversing array
for (i = 1; i < n;) {
subArrEndIndex = i+subArrEndIndex;
// Check if we have reached the end of the array
if(subArrEndIndex >= n)
return jump;
int firstHalfMaxStepIndex = 0;
//iterate the sub array and find out the maxsteps cover index
for(;i<subArrEndIndex;i++)
{
int stepsCanCover = arr[i]+i;
if(subArrFistHalfMaxSteps < stepsCanCover)
{
subArrFistHalfMaxSteps = stepsCanCover;
subArrSecondHalfMaxSteps = 0;
firstHalfMaxStepIndex = i;
}
else if(subArrSecondHalfMaxSteps < stepsCanCover)
{
subArrSecondHalfMaxSteps = stepsCanCover;
}
}
if(i > subArrFistHalfMaxSteps)
return -1;
jump++;
//next subarray end index and so far calculated sub array max step cover value
subArrEndIndex = arr[firstHalfMaxStepIndex];
subArrFistHalfMaxSteps = subArrSecondHalfMaxSteps;
}
return -1;
}
// Driver program to test above function
int main()
{
int arr[] = {100, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9};
int size = sizeof(arr) / sizeof(int);
// Calling the minJumps function
cout << ("Minimum number of jumps to reach end is %d ",
minJumps(arr, size));
return 0;
}
以防万一您需要为贪婪方法编写 python 解决方案，此代码将帮助您解决上述问题:)
def minJumps(self, arr, n):
#code here
if(n <= 1):
return(0)
if(arr[0] == 0):
return -1
maxrange, step = arr[0], arr[0]
jumps = 1
for i in range(1,n):
if (i == len(arr) - 1):
return jumps
maxrange = max(maxrange, i+arr[i])
step -= 1
if(step == 0):
jumps += 1
if(i>=maxrange):
return -1
step = maxrange - i
return(jumps)
这是另一种解决方案。在此解决方案中，最坏情况复杂度为 O(n)，而平均情况复杂度小于 O(n)。我不知道如何进行平均案例复杂性分析。所以，我无法说出确切的平均案例复杂度。但是，是的，它比 99.22% 的 leet 代码提交更快。
def minJumps(self, arr, n):
current_w=0 # current_index
last_w=n-1 # last_index
max_reach=0 # value of index upto which we have analysed array for optimum solution
max_jumps=arr[0] # maximum jumps that can be taken from a current_index
hop=0 # total jumps
while current_w<last_w:
max_jumps=arr[current_w]
if max_jumps==0:
return -1
if max_jumps==1:
max_reach=max_jumps+current_w
current_w+=1
elif max_jumps<last_w-current_w: # if maximum steps does not reach to last index
can_jump_to=arr[max_reach+1:max_jumps+current_w+1] # subarray in which we have to search for a wall,jumping to which can take us to required solution
jump_to=max(range(len(can_jump_to)),key=lambda x: x+can_jump_to[x])+max_reach+1 # finding index of wall whoose definition mentioned in above comment
max_reach=max_jumps+current_w #updating max_reach
current_w=jump_to #updating current position
else:
current_w=last_w
hop+=1
return hop