如何在O（n）时间内找到到达数组末尾的最小跳跃次数

Question

给定一个整数数组，其中每个元素表示可以从该元素向前执行的最大步数。编写一个函数，返回到达数组末尾（从第一个元素开始）的最小跳转次数。如果元素为0，则无法在该元素中移动。

输入： arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
输出： 3（1-

发现了从动态规划方法到其他线性方法的多种方法。我无法理解所谓的时间线性方法。这里是一个链接，其中提出了一种线性方法。

我完全不能理解它。我能理解的是，作者建议做一个贪婪的方法，看看我们是否到达终点...如果没有，那就回溯？

Answer 1

派对晚了几年，但这里有另一个对我来说有意义的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);
}

Answer 2

以下是关于上述问题贪婪方法的基本直觉，其余是代码需求。

给定数组是输入：[] = { 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步。因此，我们从当前位置调查每个大小的跳跃，并选择一个可以使我们最大限度地进入阵列的跳跃。

一旦我们决定了，我们坚持哪一个，我们就采取跳跃的规模，更新我们到目前为止的跳跃次数，以及我们最多能到达的地方，以及我们现在有多少步来决定我们的下一步行动。就这样。这就是我们如何最终选择线性遍历数组的最佳选项。所以这是你可能要找的算法的基本思想，接下来是为算法工作编码。干杯！

希望有人时间旅行，发现直觉有帮助！！：）：瓦西里斯库·安德烈（Vasilescu Andrei）说：“聚会迟到了好几年。”。有时我觉得我们是时间旅行者。

Answer 3

站点上提出的解决方案的时间复杂度是线性的，因为您只在数组上迭代一次。通过使用一些巧妙的技巧，该算法避免了我提出的解决方案的内部迭代。

变量maxReach始终存储数组中最大可达位置。跳转存储到达该位置所需的跳转量。步骤存储我们仍然可以采取的步骤量（并且被初始化与第一个数组位置的步数）

在迭代过程中，上述值更新如下：

首先，我们测试是否已经到达数组的末尾，在这种情况下，我们只需要返回jump变量。

接下来我们更新最大可达位置。这等于maxReach和i A[i]的最大值（我们可以从当前位置执行的步数）。

我们使用了一个步骤来获取当前索引，因此必须减少步骤。

如果没有剩余的步骤（即步骤=0，那么我们必须使用跳转。因此增加跳转。因为我们知道有可能以某种方式到达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数组中最大的元素，并使用内部循环在数组[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];
}