2

私はこのプログラミングの課題に取り組んでいます。スタックとそのアプリケーションについての理解をテストします。効率的かつ正確に機能するアルゴリズムを考え出すのは非常に難しいと思います。一部のテスト ケースには 200,000 以上の「ツリー」があります。私のアルゴリズムは、ツリーが 10 個未満の単純なテスト ケースでは機能しますが、「ツリー」の数が非常に多い場合 (100 以上以上) には、精度と効率の面で失敗します。

皆さんが親切に私にヒントを与えたり、正しい方向に向けてくれたりすることができれば、とても感謝しています. ありがとうございました。

タスク ステートメント

サルは木から木へとスイングするのが好きです。2 本の木のいずれかよりも高いか同じ高さの木が間にない限り、2 本の木から別の木に直接スイングできます。たとえば、高さ19m、17m、20m、20m、20mの順に5本の木が並んでいる場合、サルは下図のように木から木へとスイングすることができます。

1. from first tree to second tree
2. from first tree to third tree
3. from second tree to third tree
4. from third tree to fourth tree
5. from fourth tree to fifth tree

サルと意思疎通ができるジャングルの王者ターザンは、サルが木から木へ直接スイングできるペアの総数を数えることができるかどうか、サルをテストしたいと考えています。しかし、彼自身は数を数えるのがあまり得意ではありません。そこで彼は、国内最高の Java プログラマーであるあなたに、ジャングルのさまざまな場所にある木の正確な数を取得するためのプログラムを作成するよう依頼しました。

入力

最初の行には、パス内のツリーの数である N が含まれています。次の行には、N 個の整数 a1 a2 a3 ... aN が含まれます。ここで、ai はパス内の i 番目のツリーの高さを表し、0 < ai ≤ 231 および 2 ≤ N ≤ 500,000 です。

上記では、便宜上、短い記号 N が使用されていることに注意してください。プログラムでは、わかりやすい名前を付ける必要があります。

出力

指定された木の高さのリストを使用して、サルが一方から他方へ直接スイングできる木のペアの総数。

サンプル入力 1

4

3 4 1 2

サンプル出力 1

4

サンプル入力 2

5

19 17 20 20 20

サンプル出力 2

5

サンプル入力 3

4 1

2 21 21 12

サンプル出力 3

3

これが私のコードです。これは、サルがスイングできる木のペアの数を返すメソッドです。パラメータは入力の配列です。

私のアルゴリズムは次のようになります。

numPairs を (配列の長さ - 1) に設定します。これは、すべてのツリーが 1 つのツリーから別のツリーにスイングできるためです。

これで、余分な numPairs (スイングする余分なツリー) が見つかりました。

最初の入力を空のスタックにプッシュします

for ループに入ります。

配列の終わりまでの次の入力:

ケース1:

スタックのトップが現在の入力よりも小さく、スタックのサイズが 1 の場合、トップを入力に置き換えます。

ケース 2:

スタックのトップが現在の入力よりも小さく、スタックのサイズが 1 より大きい場合、トップをポップし、while ループに入り、スタックの現在のトップよりも小さい前の要素をポップします。

while ループを終了した後、現在の入力をプッシュします。

ケース3:

それ以外の場合、上記の条件が満たされない場合は、現在の入力をスタックにプッシュするだけです。

forループを終了します

numPairs を返す

public int solve(int[] arr) {

    int input, temp;
    numPairs = arr.length-1;
    for(int i=0; i<arr.length; i++)
    {
        input = arr[i];

        if(stack.isEmpty())
            stack.push(input);

        else if(!stack.isEmpty())
        {
            if(input>stack.peek() && stack.size() == 1)
            {
                stack.pop();
                stack.push(input);
            }
            else if(input>stack.peek() && stack.size() > 1)
            {
                temp = stack.pop();
                while(!stack.isEmpty() && temp < stack.peek())
                {
                    numPairs++;
                    temp = stack.pop();
                }
                stack.push(input);
                //numPairs++;
            }
            else
                stack.push(input);
        }
    }
    return numPairs;
}
4

2 に答える 2

3

これが私の解決策です、それは反復的なものです。

class Result {

  // declare the member field
  Stack<Integer> stack;
  int numPairs = 0;
  // declare the constructor
  public Result()
  {
    stack = new Stack<Integer>();
  }


  /* 
   * solve   : to compute the result, return the result
   *  Pre-condition : parameter must be of array of integer type
   * Post-condition : return the number of tree pairs that can be swung with
   */
  public int solve(int[] arr) {
    // implementation
    int input;

    for(int i=0; i<arr.length; i++)
    {
      input = arr[i];
      if(stack.isEmpty()) //if stack is empty, just push the input
        stack.push(input);

      else if(!stack.isEmpty())
      {
        //do a while loop to pop all possible top stack element until 
        //the top element is bigger than the input
        //or the stack is empty
        while(!stack.isEmpty() && input > stack.peek()) 
        {
          stack.pop();
          numPairs++;
        }

        //if the stack is empty after exiting the while loop
        //push the current element onto the stack
        if(stack.isEmpty())
          stack.push(input);
        //this condition applies for two cases:
        //1. the while loop is never entered because the input is smaller than the top element by default
        //2. the while loop is exited and the input is pushed onto the non-empty stack with numPairs being incremented 
        else if(!stack.isEmpty() && input < stack.peek())
        {
          stack.push(input);
          numPairs++;
        }
        //this is the last condition:
        //the input is never pushed if the input is identical to the top element
        //instead we increment the numPairs
        else if(input == stack.peek())
          numPairs++;

      }

    }
    return numPairs;
  }
}
于 2013-03-17T03:38:35.553 に答える
2

問題を正しく理解していれば、相互にアクセスできる 2 種類のツリーがあります。

  1. 隣接する (隣接する) ツリーは、常に相互にアクセス可能です。
  2. 隣接していないツリーは、間にあるすべてのツリーが両方のツリーよりも短い場合にのみアクセスできます。

これには、いくつかのタイプの解決策が思いつくかもしれません。

  • 強引な解決策: 上記の条件をチェックして、すべてのツリーを他のすべてのツリーと比較します。実行時間: O(n^2)
  • アクセス可能な近くの隣人を見つけるソリューション: アクセス可能な近くの隣人を探します。実行時間: O(n) に近い。これがどのように機能するかは次のとおりです。

指定された順序でツリー サイズの配列を作成します。次に、この配列を順番に、 index のすべてのツリーについて調べますi。

から右へi

  1. i+1のツリーがブレーク アウトのツリーよりも高い場合i(これ以上アクセス可能なネイバーは見つかりません)
  2. ツリー at がツリー atより短い1場合、アクセス可能なツリーの数に追加しますi+1i+2
  3. より高い木が見つかるまで、木i+2についても同じことを行います。i+3i

これにより、すべてのツリーについて、隣接していないアクセス可能なツリーの数が取得されます。N*2-2次に、隣接するすべてのツリーを考慮してカウントを追加するだけで完了です。

于 2013-03-15T17:49:31.593 に答える