一种更好的青蛙穿越算法

Question

我正在解决Codility中的以下问题：

一只小青蛙想去河的另一边。青蛙当前位于位置0，并且想要到达位置X。树叶从树上掉到河面上。给您一个非空的零索引数组A，该数组A由代表落叶的N个整数组成。 A [K]表示在时间K处一片叶子掉落的位置，以分钟为单位。目的是找到青蛙跳到河对岸的最早时间。只有当叶子从1到X穿过河的每个位置时，青蛙才能穿过。

我使用以下解决方案，但仅获得81分：

代码在C＃中。

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int X, int[] A) {
        bool[] tiles = new bool[X];

        for (int i = 0; i < A.Length; i++)
        {
            tiles[A[i] - 1] = true;

            bool complete = true;

            for (int j = 0; j < tiles.Length; j++)
            {
                if (!tiles[j])
                {
                    complete = false;
                    break;
                }
            }

            if (complete)
                return i;
        }

        return -1;
    }
}

我的算法在O（NX）运行。什么是仅需要O（N）的更好算法？

Answer 1

将您的代码更改为类似这样的内容：

public int solution(int X, int[] A) 
{
    bool[] tiles = new bool[X];
    int todo = X;

    for (int i = 0; i < A.Length; i++)
    {
        int internalIndex = A[i] - 1;
        if (internalIndex < X && !tiles[internalIndex])
        {
            todo--;
            tiles[internalIndex] = true;
        }

        if (todo == 0)
            return i;
    }

    return -1;
}

此算法只需要O(A.length)时间，因为它始终跟踪我们仍然需要用树叶填充多少“洞”。

这里如何完成？

todo是建立叶子“桥”所需的叶子数。每当叶子掉落时，我们首先检查叶子掉落的位置是否还没有叶子。如果不是，我们递减todo，填充孔并继续。todo到达0后，整个河流就会被覆盖；）

Answer 2

这是我在C99中的解决方案，可能不是最优雅的解决方案。但我希望是可读和可理解的。这是我测试的链接。 https://codility.com/demo/results/demoNGRG5B-GMR/

Answer 3

使用C＃的100％

Answer 4

下面是使用字典的另一种方法：

Answer 5

这在O（N）中运行并返回100％：

Answer 6

虽然我同意您获得100分，但并不满足所有测试用例

Answer 7

这让我100/100

Answer 8

这里是一个简单的C ++解决方案：

Answer 9

100％得分：FrogRiverOne的PHP代码：Ajeet Singh

Answer 10

这是我基于HashSet的变体。结果为here

Answer 11

这是我想出的Python解决方案（Codility为100/100）：

Answer 12

Ruby解决方案（Codility为100/100）：

Answer 13

我在进行这项练习时发生了一些晚。除了C90，我看到了很多语言。像许多人一样，我确实通过创建辅助阵列找到了解决方案。我先使用典型的calloc，然后再使用free。我的第一个解决方案与其他发布的类似：