查找数组列表中的最大序列 [英] 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周围加上方括号，因为它们最常出现. 我已经学习了本章中的所有其他问题(Arrays和ArrayLists)，但是我似乎无法弄清楚这一点.

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

我的想法

遍历整个列表.创建一个count变量，该变量跟踪彼此连续的数字.即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.

我的计数正在像这样重置

My count is resetting like this

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.

根据要求:

As asked:

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

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屋！