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 回答