c# - カエル交差アルゴリズムの改善

Question

Codility から次の問題を解決しています。

小さなカエルが川の向こう側に行きたがっています。カエルは現在位置 0 にあり、位置 X に移動しようとしています。葉が木から川の水面に落ちます。落ち葉を表す N 個の整数で構成される空でないゼロ インデックスの配列 A が与えられます。A[K] は、時間 K で 1 枚の葉が落ちる位置を分単位で表します。目標は、カエルが川の反対側にジャンプできる最も早い時間を見つけることです。カエルが渡れるのは、川を渡る 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

これは、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;
}

Answer 3

これは私に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;
}

Answer 4

あなたが 100 のスコアを得ることに同意しますが、それはすべてのテスト ケースを満たしているわけではありません

1、3、1、4、2、3、5、4のサンプルデータの場合

3 を見つけようとすると 5 が返されますが、与えられた答えは例外をスローします

修正されたバージョンは、位置 2 で失敗したリーフが 4 分後に満たされるためです。

    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;
    }

Answer 5

簡単な 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; 
}

Answer 6

C# で 100%

 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;

}

Answer 7

以下は、辞書を使用した別のアプローチです。

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の代わりにリストを使用しようとしましたが、いくつかのパフォーマンステストで失敗しました。キーを介してルックアップを行うときのオブジェクト。

Answer 8

これが私が思いついたPythonソリューションです（Codilityで100/100）：

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

Answer 9

私はこの演習に少し遅れてたどり着きました。を除く多くの言語がカバーされているのを見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;
}

私のソリューションの両方のバリアントは、すべてのテストに合格しました。

Answer 10

これは、時間の複雑さが O(N) である私の 100% ソリューションでした。これらの割り当てでは Generics と 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;
}

Answer 11

これが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;
}

Answer 12

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