5

我正在从 Codility 解决以下问题：

一只小青蛙想去河的另一边。青蛙当前位于位置 0，并想到达位置 X。树叶从树上掉到河面上。给定一个非空的零索引数组 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) 的更好算法？

4

16 回答 16

9

将您的代码更改为以下内容：

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，整条河都被覆盖了；）

于 2013-09-19T09:37:44.890 回答
2

那是我基于 HashSet 的变体。结果在这里

public int solution(int X, int[] A)
{
  HashSet<int> hash = new HashSet<int>();

  for(int i=0;i<A.Length;i++)
  {
    if(A[i]<=X)
      {
          hash.Add(A[i]);

           if(hash.Count == X)
             return i;
      }
  }
  return -1;
}
于 2016-05-27T08:37:23.997 回答
1

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

对于1、3、1、4、2、3、5、4的样本数据

如果您尝试找到 3 它应该返回 5 但给出的答案会引发异常

一个更正的版本是，因为在位置 2 失败的叶子在第四分钟后完成

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

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

                    todo--;

                    tiles[internalIndex] = true;

                }
            }
            if (todo == 0)

                return steps;
        }
        return -1;
    }
于 2013-11-06T18:32:34.400 回答
1

这让我 100/100

public int solution(int X, int[] A)
{
    int z = -1;

    long combA = ((long) X)*(((long) X) + 1)/2;
    long sumA = 0;

    int[] countA = new int[X];

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

        if (countA[A[i] - 1] > 1)
        {
            countA[A[i] - 1] = 1;
        }
        else
        {
            sumA += A[i];
        }


        if (sumA == combA)
        {
            z = i;
            break;
        }

    }

    return z;
}
于 2013-11-09T13:40:52.160 回答
1

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

int solution(int X, vector<int> &A)
{
  vector<bool> removed( X );

  for( size_t i = 0; i < A.size(); i++ )
  {
    if( removed[ A[i] - 1 ] == false )
    {
      removed[ A[i] - 1 ] = true; 
      X--;

      if(X == 0)
      {
        return i;
      } 
    }
  }

  return -1; 
}
于 2014-06-06T12:37:24.263 回答
1

100% 分数：FrogRiverOne 的 PHP 代码：Ajeet Singh

function solution($X, $A) {
    for ($i = 0; $i < count($A); $i++){        
        if (!isset($position_achieved[$A[$i]])){
            $X--;   // reduce X by one position is achieved
            $position_achieved[$A[$i]] = true;
        }
        if (!$X){
            return $i;
        }
    }
    return -1;    
}
于 2014-07-28T14:12:51.677 回答
0

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

def solution(X, A):
    N = len(A)
    count = [0] * (X+1)
    steps = 0
    for k in xrange(N):
        if not count[A[k]]:
            count[A[k]] = 1
            steps += 1
            if steps == X:
                return k
    return -1
于 2014-02-13T22:36:56.690 回答
0

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

def solution(x, a)

  check_array = (0..a.length).to_a
  check_array.each { |i| check_array[i]=0 }

  a.each_with_index do |element, i|

      if (check_array[element]==0)
          check_array[element]=1
          x -= 1
      end

      return i if (x==0)
  end

  return -1

end
于 2014-08-05T12:07:14.943 回答
0

我碰巧这个练习有点晚了。我看到很多语言都涵盖了，除了C90. 像许多人一样，我确实通过创建辅助阵列找到了解决方案。我使用了典型calloc的然后free. 我的第一个解决方案与其他发布的解决方案类似：

int solution(int X, int A[], int N)
{
    int *n = calloc(X, sizeof(*A));
    int index;

    for (index = 0; index < N; index++) {
        if (n[A[index] - 1] == 0) {
            n[A[index] - 1] = 1;
            if (--X == 0) {
                free(n);
                return index;
            }
        }
    }

    free(n);
    return -1;
}

我意识到我可以完全不使用第二个数组，因为我们正在处理有符号整数并且该codility网站还说Elements of input arrays can be modified。它还说each element of array A is an integer within the range [1..X]。由于原始输入数组A总是有正数，我可以利用它来发挥我的优势。我可以使用数组中 s的符号位来表示我是否已经（或没有）看到特定的叶子位置。新版本的代码使用该函数来处理每个数组元素中的绝对值以进行索引。我设置符号位以指示我已经访问了特定的叶子位置，并且我在索引处检查实际值而不使用intint A[]absabs知道我是否已经访问过该职位。我的最终解决方案如下所示：

int solution(int X, int A[], int N)
{

    int index;
    int leaftimeidx;

    for (index = 0; index < N; index++) {
        leaftimeidx = abs(A[index]) - 1;

        if (A[leaftimeidx] > 0) {
            A[leaftimeidx] *= -1;

            if (--X == 0)
                return index;
        }
    }
    return -1;
}

我的解决方案的两种变体都通过了所有测试。

于 2014-10-11T03:25:29.423 回答
0

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

int solution(int X, int A[], int N) {

    if (X <= 1) return 0; //if we only need to go 1 step we are already there
    if (N == 0) return -1;//if we don't have timing we can't predict 

    int B[X+1];

    for (int i=0; i <= X; i++) {
        B[i] = -1; //i set default value to -1 so i can see later if we missed a step. 
    }

    for (int i=0; i < N; i++) {
        if (A[i] <= X && (B[A[i]] == -1 || B[A[i]] > i)) B[A[i]] = i; //prepare my second array here with timing data 
    }

    int max_min = 0; //store the highest timing later on.

    for (int i=1; i <= X; i++) {
        if (B[i] == -1) return -1; //if we have any elements with -1 then we didn't cross the river
        if (max_min < B[i]) max_min = B[i]; //keep setting the highest timing seen the steps.
    }

    return max_min;
}
于 2014-10-22T17:21:34.337 回答
0

100% 使用 C#

 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Threading.Tasks;
 using System.Collections;

  public int solution(int X, int[] A)
{
    // write your code in C# 5.0 with .NET 4.5 (Mono)

    int N = A.Length;
    int step = 0;
    List<int> k = new List<int>();


    for (int i = 0; i < X; i++)
    {
        k.Add(0);
    }

    //Inserts an element into the ArrayList at the specified index.
    for (int i = 0; i < N; i++)
    {
        int diff = A[i] - 1;

        k[diff] = A[i];

        if (i >= X-1 && (k.Contains(0) == false))
        {
           return i;

        }

    }


    return -1;

}
于 2015-04-23T21:16:47.390 回答
0

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

public int solution(int X, int[] A) {
        int result = -1;
         Dictionary<int, int> jumps = new Dictionary<int, int>();
            int res =  (X*(X+1))/2;
            int sum = 0;

            for (int i = 0; i < A.Length; i++)
            {
                if (!jumps.ContainsKey(A[i]))
                {
                    sum = sum + A[i];
                    jumps.Add(A[i],i);
                    if (sum == res)
                    {
                        result = i;
                        break;
                    }
                }
            }
            return result;
    }

上面的代码是创建直到 X 的整数之和，即如果 X=5，那么我们使用高斯公式 (X*(X+1))/2 计算 (1+2+3+4+5)，这将允许我们稍后知道是否添加或发生了总跃点。该值将与添加到字典中的不同步骤的总和进行比较。根据描述“只有当叶子出现在从 1 到 X 横跨河流的每个位置时，青蛙才能越过。”我尝试使用列表而不是 dic，但它在某些性能测试中失败了，Dictionay 的强大功能来了当我们通过键查找对象时。

于 2015-06-17T09:26:27.103 回答
0

这在 O(N) 中运行并返回 100%：

    public int solution(int X, int[] A) {
            Hashtable spaces = new Hashtable();
            int counter = 0;
            foreach(int i in A)
            {
                //Don't insert duplicate keys OR 
                //keys greater than requested path length
                if (!spaces.ContainsKey(i) && i <= X)
                    spaces.Add(i, i);

                //If Hashtable contents count = requested number of leaves,
                //then we're done
                if (spaces.Count == X)
                    return (counter);

                counter++;
            }

            return -1;
    }
于 2020-01-14T18:25:47.920 回答
0

这是我的 100% 解决方案，时间复杂度为 O(N)。请记住，您可以在这些作业中使用泛型和 Linq。

public int solution(int X, int[] A)
{
    SortedSet<int> leaves = new SortedSet<int>();
    for (int i = 0; i < A.Length; i++)
    {
        leaves.Add(A[i]);
        if (leaves.Count() == X) return i;
    }
    return -1;
}
于 2020-07-17T13:32:21.727 回答
0

这是Python3中的解决方案

def solution(target, data_list):
    check_set = set()
    for i, value in enumerate(data_list):
        if value <= target:
             check_set.add(target)
        if len(check_set) == data_list:
            return i

    return -1
于 2021-11-12T07:43:27.160 回答
0 
    public static int solution(int X, int[] A)
    {
        HashSet<int> hash = new HashSet<int>();

        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] <= X)
            {
                hash.Add(A[i]);

                if (hash.Count == X)
                    return i;
            }
        }
        return -1;
    }
于 2022-02-06T08:32:29.547 回答