一些背景
上周我在教科书上做了一道题,它告诉我生成 20 个随机数,然后用括号括起连续相等的数字 考虑以下我的程序输出
697342(33)(666)(44)69(66)1(88)
我需要做什么
下一个问题基本上是获取这些单词的最长序列并将它们括起来。如果你有
1122345(6666)
基本上,您需要将四个 6 放在方括号中,因为它们出现的频率最高。 我已经完成了我正在学习的章节中的所有其他问题(Arrays 和 ArrayLists),但是我似乎无法解决这一问题。
这是我为将连续数字放在方括号中而做出的解决方案:
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
之后,我们需要一种方法来获取最大的 count
变量的起始索引以及结束。
我的思路对吗?因为我在比较 oldCount 和 count 变量时遇到问题,因为它们的值不断变化。 我不是在寻找代码,而是在寻找一些有值(value)的提示。
我的计数是这样重置的
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;
}
最佳答案
只有遍历所有元素后,您才能知道最长的子序列。
11222333333444555
11222(333333)444555
因此只有在循环之后你才能插入两个括号。
所以你必须保持局部最优:起始索引加上长度或最优的最后一个索引。 然后对于每个序列,当前序列的起始索引。
如问:
最优状态(序列)和当前状态是两个东西。不能事先说任何当前状态就是最终的最优状态。
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();
}
第一个问题是如何找到序列的结尾,并设置序列的正确起点。
原始算法的问题在于只处理了一个序列(一个子序列开始)。
关于java - 在数组列表中查找最大序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38830199/