查找数组列表中的最大序列 [英] Find largest sequence within an arraylist

问题描述

一些背景

上周我在我的教科书中做了一个问题，它告诉我生成 20 个随机数，然后在相等的连续数字周围加上括号考虑以下我的程序输出

Last week I did a problem in my textbook where It told me to generate 20 random numbers and then put brackets around successive numbers that are equal Consider the following which my program outputs

697342(33)(666)(44)69(66)1(88)

我需要做什么

接下来的问题是基本上得到这些单词的最长序列并在它们周围加上括号.如果你有

The next problem was to basically get the longest sequence of these words and put brackets around them. If you have

1122345(6666)

基本上你需要在四个 6's 周围加上括号，因为它们最常出现.我已经完成了我正在学习的那一章(数组和数组列表)中的所有其他问题，但是我似乎无法解决这个问题.

Basically you need to put brackets around four 6's , since they occur most often. I've finished all other problems in the chapter I am studying ( Arrays and ArrayLists), however I can't seem to figure this one out.

这是我为在连续数字周围放置括号而制定的解决方案:

Here is the solution that I have made for putting brackets around successive numbers:

class Seq
{
    private ArrayList<Integer> nums;
    private Random randNum;
    public Seq()
    {
        nums = new ArrayList<Integer>();
        randNum = new Random();
    }
    public void fillArrList()
    {
        for (int i = 0 ; i < 20 ; i++)
        {
            int thisRandNum = randNum.nextInt(9)+1;
            nums.add(thisRandNum);
        }
    }

    public String toString() {
        StringBuilder result = new StringBuilder();
        boolean inRun = false;
        for (int i = 0; i < nums.size(); i++) {
            if (i < nums.size() - 1 && nums.get(i).equals(nums.get(i + 1))) {
                if (!inRun) {
                    result.append("(");
                }
                result.append(nums.get(i));
                inRun = true;

            } else {
                result.append(nums.get(i));
                if (inRun) {
                    result.append(")");
                }
                inRun = false;

            }
        }
        return result.toString();
    }
}

我的想法

遍历整个列表.创建一个计数变量，以跟踪彼此连续的数字数量.即 22 的计数为 2.444 个 3接下来创建一个 oldCount，它将当前的 count 与 oldCount 进行比较.如果我们的新 count 大于 oldCount

Iterate through the whole list. Make a count variable, that keeps track of how many numbers are successive of each other. I.e 22 would have a count of 2. 444 a count of 3 Next make an oldCount, which compares the current count to the oldCount. We only want to keep going if our new count is greater than oldCount

之后我们需要一种方法来获得最大的count变量的起始索引，以及结束.

After that we need a way to get the starting index of the largest count variable, as well as the end.

我的想法正确吗?因为我在比较它们时更新 oldCount 和 count 变量时遇到问题，因为它们的值不断变化.我不是在寻找代码，而是在寻找一些有价值的提示.

Is my way of thinking correct? Because I'm having trouble updating the oldCount and count variable while comparing them, since there values constantly change. I'm not looking for the code, but rather some valuable hints.

我的计数是这样重置的

int startIndex, endIndex = 0;
        int count = 0;
        int oldCount = 0;

            for(int i = 0 ; i < nums.size(); i++)
            {
                if(nums.get(i) == nums.get(i+1) && count >= oldCount)
                {
                    count++;
                }
                oldCount = count;
            }

推荐答案

只有遍历完所有元素，你才会知道最长的子序列.

Only after walking all elements you will know the longest subsequence.

11222333333444555
11222(333333)444555

因此只有在循环之后才能插入两个括号.

Hence only after the loop you can insert both brackets.

所以你必须保持一个局部最优:开始索引加上长度或最优的最后一个索引.然后对于每个序列当前序列的起始索引.

So you have to maintain a local optimum: start index plus length or last index of optimum. And then for every sequence the start index of the current sequence.

按照要求:

最佳状态(序列)和当前状态是两件事.不能预先说任何当前状态都是最终的最优状态.

The optimal state (sequence) and the current state are two things. One cannot in advance say that any current state is the final optimal state.

public String toString() {
    // Begin with as "best" solution the empty sequence.
    int startBest = 0; // Starting index
    int lengthBest = 0; // Length of sequence

    // Determine sequences:
    int startCurrent = 0; // Starting index of most current/last sequence
    for (int i = 0; i < nums.size(); i++) {
        // Can we add the current num to the current sequence?
        if (i == startCurrent || nums.get(i).equals(nums.get(i - 1)))) {
            // We can extend the current sequence with this i:
            int lengthCurrent = i - startCurrent + 1;
            if (lengthCurrent > lengthBest) { // Current length better?
                // New optimum:
                startBest = startCurrent;
                lengthBest = lengthCurrent;
            }
        } else {
            // A different num, start here.
            // As we had already a real sequence (i != 0), no need for
            // checking for a new optimum with length 1.
            startCurrent = i;
        }
    }
    // Now we found the best solution.
    // Create the result:
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < nums.size(); i++) {
        result.append(nums.get(i));
    }
    // Insert the right ')' first as its index changes by 1 after inserting '('.
    result.insert(startBest + lengthBest, ")");
    result.insert(startBest, "(");
    return result.toString();
}

第一个问题是如何找到一个序列的结尾，并设置正确的序列开始.

The first problem is how to find the end of a sequence, and set the correct start of the sequence.

原始算法的问题是只处理了一个序列(一个子序列开始).

The problem with the original algorithm is that there is handled just one sequence (one subsequence start).

这篇关于查找数组列表中的最大序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！