当前位置: 首页 > 知识库问答 >
问题:

通过最大跳跃长度数组的最短路径

韦睿
2023-03-14

我正在调试以下问题并发布代码。不知道代码是否正确。我目前的疑问是,i是否应该一直增加(在这一行--for(;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;
        }
    };
    

  • 共有3个答案

    法玮
    2023-03-14

    我在分享算法。现在,做BFS描述如下:

    int A[N];         // It contains the initial values
    int result[N];    // Initialise all with positive infinty or INT_MAX in C
    bool visited[N];  // Initially, all initialise with '0' means none of the index is visited
    queue Q;          // create a queue 
    
    index = 1
    cost = 0
    push index in rear of Q.
    result[index] = cost
    visited[index] = true
    
    while(Q is not empty) {
        index = pop the value from the front of the Q.
        cost = cost + 1
    
        for(i in 1 to A[index]) {
            temp_index = index + i;
            if(temp_index <= N   AND  visited[temp_index] == false) {
                push temp_index in rear of Q.
                result[temp_index] = cost
                visited[temp_index] = true
            }
        }
    }
    
    // Finally print the value of result[N]
    print result[N]
    

    注:还存在一种DP方法,其时间复杂度为O(n2)。

    商飞翮
    2023-03-14

    我在这里看到两种解决方法。

    您只需从索引0开始,对于每个索引i尝试跳转到1到a[i]前面的索引,同时保留最后一个索引的最佳结果。它具有很高的算法复杂度,因此只有在效率确实不相关或者n非常小的情况下才应该选择它。

    算法如下所示:

    int best = 2147483647;
    vector<int> A;
    
    void Jump(int index, int step)
    {
        if (step > best)
        {
            // for positive values, if step > best we won't improve our result
            // avoid worthless calculations
            return; 
        }
        if (index == A.size() - 1)
        {
            if (step < best) best = step;
            return;
        }
    
        int maxJumps = A[index];
        for (int i = index; i <= min(index + maxJumps, A.size() - 1); i++) 
        {
            Jump(i, step + 1);
        }
    }
    
    int main()
    {
        // read input
        Jump(0, 0);
    }
    

    对于您的情况,递归将这样进行:

    Start from A[0] (equal to 2)                             step = 0
    > A[0+1] with step+1 (equal to 3)                        step = 1
    >> A[1+1] with step+1 (equal to 1)                       step = 2
    >>> A[2+1] with step+1 (equal to 1)                      step = 3
    >>>> A[3+1] with step+1 (equal to 4)                     step = 4
    >>>>> End of array. Compare step(4), best (MAXINT)         best = 4
    >> A[1+2] with step+1 (equal to 1)                       step = 2
    >>>> A[3+1] with step+1 (equal to 4)                      step = 3
    >>>>> End of array. Compare step (3), best (4)             best = 3
    >> A[1+3] with step+1 (equal to 4)                       step = 2
    >>>>> End of array. Compare step(2), best (3)              best = 2
    > A[0+2] with step+1 (equal to 1)                        step = 2
    >>> A[2+1] with step+1 (equal to 1)                       step = 3
    >>>> A[3+1] with step+1 (equal to 4)                      step = 4
    >>>>> End of array. Compare step(4), best(2)               best = 2
    

    动态聪明高效

    这种方法使用动态规划。让我们有一个与数组A长度相同的数组B。让B[i]表示“跳转到A[i]至少需要多少步”。如果我们知道B[i],那么我们可以说我们可以跳到B[i]1的所有可能索引(从i1iA[i])。因此,您所需要的只是从0到N-1遍历数组并向前看,改进每个iia[i]的结果。

    大概是这样的:

    vector<int> A, B;
    int n;
    
    int main() 
    {
        // read n; read A of size n
        B.reserve(n); // B should be the same size and initialized with zeroes (by default)
    
        B[0] = 0; // not obligatory, 0 by default, just for clearness
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j <= min(i + A[i], n - 1); j++)
            {
                // improve result if we weren't there yet or if we can come to A[j]
                // faster if we go from A[i]
                if (B[j] == 0 || B[i] + 1 < B[j]) 
                    B[j] = B[i] + 1;
            }
        }
    }
    

    该算法将这样工作:

    A = 2 3 1 1 4
    B = 0 0 0 0 0
    
    i = 0, improve 0+1, 0+2
    B = 0 1 1 0 0
    
    i = 1, improve 1+1, 1+2, 1+3
    B = 0 1 2 2 2
    
    i = 2, no improvements 
    i = 3, no improvements
    

    答案存储在B[n-1]中。我已经实现了一个工作的IDEOne演示。

    房冥夜
    2023-03-14

    假设给定的数组是A[1..n]。从第i个位置,你可以跳1或2或3。。。A[i]。您已经计算了所有j的结果

    ans[i]=min(ans[i+j],ans[i]) where i+j<=n && j=1,2,...A[i]
    

    这样你就可以计算一切。

    O(n^2)时间复杂度。

    您也可以在O(n)中计算它。从一个位置,您将始终移动到具有最高i A[i]值的位置。我的意思是假设你在jth的位置。然后,您将下一步移动到位置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)
    
     类似资料:
    • 问题内容: 基本上我有一个类似于以下问题: 有一个以2D正方形阵列表示的草莓植物花园。每棵植物(每个元素)都有许多草莓。您从数组的左上角开始,并且只能向右或向下移动。我需要设计一种递归方法来计算通过花园的路径,然后输出产量最高的草莓。 我认为我对非常简单的递归问题有所了解,但是这个问题已经超出了我的范围。我真的不确定创建递归方法的起点或终点。 非常感谢与代码相关的任何帮助或帮助我理解此问题背后的概

    • 问题内容: 当我尝试过时如何设置可以使用swift输入到UITextField中的最大字符数?,我看到如果我全部使用10个字符,我也无法删除该字符。 我唯一能做的就是取消该操作(一起删除所有字符)。 有谁知道如何不遮挡键盘(以便我不能添加其他字母/符号/数字,但可以使用退格键)? 问题答案: 对于Swift 5和iOS 12,请尝试以下协议实现方法的实现: 该代码最重要的部分是从()到()的转换。

    • 配置最大长度为数据存储提供了有关示意,示意其为给定属性使用合适的数据类型。最大长度仅被应用于数组数据类型,比如 string 和 byte[]。 注意 Entity Framework 在将数据传递给数据库提供程序之前不会做最大长度验证。是否合适是由数据库提供程序或数据储存验证的。比如,使用的是 SQL Server 时,超出最大长度将由于底层数据列的数据类型不允许数据超出而导致异常。 惯例 按照

    • 下面是寻找最小跳跃次数的算法谜题。发布了详细的问题声明和两个代码版本来解决这个问题。我做了测试,似乎两个版本都可以工作,我的第二个版本是版本一代码的优化版本,这使得我从开始,而不是持续增加,这可以通过不迭代所有的插槽来节省时间数组。 我的问题是,想知道我的第二个版本代码是否100%正确?如果有人发现任何逻辑问题,请指出。 问题陈述 给定一个非负整数数组,您最初位于数组的第一个索引处。 数组中的每个

    • 我正在从事一个JavaFX项目,使用TextField控件时遇到问题。我想将用户在每个文本字段中输入的字符限制为一个。如果将单个文本字段与侦听器一起使用,我找到了一个解决方案: 但问题是我有一个TextFields数组。你们知道如何为TextFieldArray重写这个侦听器吗? 阵列列表实现: 阵列初始化: 我使用了给定的解决方案: GamePresenter是编写侦听器的视图的演示者。在“Ga

    • 问题陈述:给定一个长度为N的非负整数数组A,您最初位于数组的第一个索引处。数组中的每个元素表示该位置的最大跳跃长度。返回到达最后一个索引所需的最小跳转次数。 输入:A=[2,3,1,1,4] 产出:2 说明:达到指数4的最短途径是指数0- 以下是解决方案: 我得到了上述解决方案的TLE。我无法在记忆后计算出解决方案的时间复杂度。有人能帮我估计一下上述解决方案的时间复杂度吗。