如何在O(n)时间内找到到达数组末尾的最小跳转次数

Question

题

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

例

输入:arr [] = {1,3,5,8,9,2,6,7,6,8,9}
输出:3(1-> 3 - > 8 - > 9)

找到了从动态规划方法到其他线性方法的多种方法.我无法理解在时间上线性的方法.HERE是提出线性方法的链接.

我根本无法理解它.我能理解的是,作者建议做一个贪婪的方法,看看我们是否达到目的......如果没有那么回溯？

Answer 1

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

变量maxReach始终存储数组中的最大可达位置.jump存储到达该位置所需的跳跃量.step存储我们仍然可以采取的步数(并使用第一个数组位置的步数进行初始化)

在迭代期间,上述值更新如下:

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

接下来,我们更新最大可达位置.这等于最大值maxReach和i+A[i](我们可以从当前位置获取的步数).

我们用了一步来获得当前的指数,所以steps必须减少.

如果没有剩下更多的步骤(即steps=0,我们必须使用跳跃.因此增加jump.因为我们知道有可能以某种方式达到maxReach,我们将步骤初始化为maxReach从位置到达的步数i.

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 = 1 + 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 = 1 + 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 = 1 + 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 = 1 + 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 untill 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];
} 

Answer 2

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

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

一旦我们决定坚持哪一个，我们就会采用跳跃大小并更新迄今为止的跳跃次数，以及我们最多可以到达的位置以及我们现在有多少步来决定下一步行动。就是这样。这就是我们最终选择线性遍历数组的最佳选项的方式。这就是您可能正在寻找的算法的基本思想，接下来是对其进行编码以使算法能够工作。干杯!

希望有人进行时间旅行并发现直觉有帮助！:) :P “晚了几年”@Vasilescu Andrei - 说得好。有时我觉得我们是时间旅行者。