0

私は、サイコロを 20 回印刷し、繰り返される値を括弧でグループ化する必要がある演習に取り組んでいます。以下の私のコードは、私が読んでいる本が使用するように言っている疑似コードに従います。繰り返される値を括弧でグループ化することはできますが、次の演習では、最も多く繰り返される値を括弧でグループ化する必要があります。

例えば：

(333)51314121(22)326(55)14

だろう：

(333)51314121223265514

編集: 繰り返される値の最大のグループが複数ある場合は、最初のグループのみが括弧でグループ化されます。

どうすればこれを達成できますか? これについて何か助けてくれてありがとう。

public void run() {

    Random generator = new Random();
    ArrayList<Integer> a = new ArrayList<Integer>();

    for (int i = 0; i < 21; i++) {
        int die = generator.nextInt(6)+ 1;
        a.add(die);
    }

    for (int j = 0; j < a.size() - 1; j++) {
        if (inRun) {
             if (a.get(j) != a.get(j - 1)) {
                 System.out.print(")");
                 inRun = false;
             }

        }
        else {
            if (a.get(j) == a.get(j + 1)) {
                System.out.print("(");
                inRun = true;
            }
        }
        System.out.print(a.get(j));

    }
    if (inRun) {
        System.out.print(")");
    }

}
4

3 に答える 3

1

通常の配列以外のデータ構造は本当に必要ありません。

挿入中にチェックすることで、 O（n）にすることができます：

  • 追加された数が前の と等しい場合は、シーケンス カウントをインクリメントします。そうでない場合は、カウントをリセットします。
  • シーケンス カウントをインクリメントするときは、既に格納されている最大シーケンス カウント長よりも大きいかどうかを確認します。それより大きい場合は、現在のシーケンス カウント が最大シーケンス カウントになります。

コードを確認してください - 理解に役立ついくつかのコメントがあります (ここでデモをオンラインで実行してください):

public void run() {
    Random generator = new Random();
    int[] a = new int[20];

    int biggerSequence = 1;         // starts pointing to the first char
    int biggerSequenceEndIndex = 1; // starts pointing to the first char
    int currentSequence = 1;
    int previous = -1;
    for (int i = 0; i < 20; i++) {
        int die = generator.nextInt(6)+ 1;
        a[i] = die;
        if (die == previous) { // if inserted equals previous
            currentSequence++; // increment sequence
            if (currentSequence > biggerSequence) { // if it is bigger than max
                biggerSequence = currentSequence; // max becomes it
                biggerSequenceEndIndex = i+1;
            }
        } else {
            previous = die;
            currentSequence = 1; // reset the count
        }
    }

    for (int i = 0; i < a.length; i++) {
       if (i == biggerSequenceEndIndex-biggerSequence) { System.out.print("("); }
       System.out.print(a[i]);
       if (i+1 == biggerSequenceEndIndex) { System.out.print(")"); }
    }
}

出力例:

(1)2345678901234567890
(11)345678901234567890
1(22)45678901234567890
1(22)45578901234567890
123456789012345678(99)
54(3333)43514564513551
于 2013-07-05T17:21:26.857 に答える
0

特定のインデックスから始まる繰り返し値の数を保存してみてください。何かのようなもの：

public void run(){

    Random generator = new Random();
    ArrayList<Integer> a = new ArrayList<Integer>();

    for (int i = 0; i < 21; i++) {//Generate your numbers
        int die = generator.nextInt(6)+ 1;
        a.add(die);
    }

    //store the number of repeats by index. (index is key, # of repeats is key)
    HashMap<Integer, Integer> repeats = new HashMap<Integer, Integer>();

    //This will find store the number of repeated numbers starting at any given index.
    int index = 0;
    repeats.put(index, 1);
    for(int i = 1; i < a.size(); i++){
        if(a.get(i) == a.get(index)){//Repeated values occurring
            repeats.put(index, repeats.get(index) + 1);
        } else {//End of a repeated sequence (even if that sequence was only 1 number long)
            repeats.put(i, 1);
            index = i;
        }
    }

    //Find the index at which the maximum number of repeats occurs
    int max = 0;
    int startIndex = 0;
    for(Integer i : repeats.keySet()){
        //If the number of repeats is bigger than anything seen before
        if(repeats.get(i) > max){
            //Store the number of repeats and the index at which they start
            max = repeats.get(i);
            startIndex = i;
        }
    }

    //print everything out
    for(int i = 0; i < a.size(); i++){
        if(i == startIndex)//Prints the open parenthesis before the repeats start
            System.out.print("(");
        System.out.print(a.get(i)); //Prints the number
        if(i == startIndex + max)
            System.out.print(")");//Prints the close parenthesis after the repeats end
    }
}

このアルゴリズムは、最大サイズの反復シーケンスが 1 つしかないことを前提としていることに注意してください。保持したいものが複数ある場合は、すべてのインデックスを別のリストに保存する必要があります。しかし、それは次のようなソリューションのマイナーな修正です。

ArrayList<Integer> startIndeces = new ArrayList<Integer>();
int max = 0;
for(Integer i : repeats.keySet()){
    //If the number of repeats is bigger than anything seen before
    if(repeats.get(i) > max){
        //Store the number of repeats and the index at which they start
        max = repeats.get(i);
        startIndeces = new ArrayList<Integer>();
        startIndeces.add(i);
    } else if(repeats.get(i) == max)
        startIndeces.add(i);
}

それ以外の場合、アルゴリズムは最長シーケンスの最初のインスタンスを格納します。

于 2013-07-05T16:26:12.050 に答える
0

配列に対して複数のパスを作成する必要があります。一度それを調べて、すべてのランの長さを集計してください。次に、最大実行長を決定します。最後に、戻って配列を出力し、最大長のランを括弧で囲みます。

このようなことを試してください（正確な実装はあなたに任されています）：

runContents = a list containing the first random number
runLength = [1], i.e. a one element list with the number 1 in it
maxLength = 1
for each subsequent random number you want to consider {
  if the last element of runContents == the next random number {
    add 1 to the last element of runLength
  } else {
    if maxLength < the last element of runLength {
      maxLength = the last element of runLength
    }
    append the random number to runContents
    append a 1 to runLength
  }
}

i = 0
while i < length(runContents) {
  if runLength[i] == maxLength {
    print runLength[i] copies of runContents[i] surrounded by parens
  } else {
    print runLength[i] copies of runContents[i]
  }
}
于 2013-07-05T16:27:16.680 に答える