处理不断变化的数组

Question

给定一个数组，如果两个相邻的数字相等，则它们可以合并，并且它们的值增加1。在此过程之后，找到数组中剩余元素的最小可能数量。例:[1,1,1,2,1]->[1,2,2,1]->(1, 3, 1)。因此答案是3。我试过使用链表来存储数组，然后遍历整个数组，直到没有相等的相邻数字被检测到，但这似乎非常不够。任何提示或建议是非常感谢。谢谢你的宝贵时间

Answer 1

这是一个递归解决方案，但我不知道它是否是最佳的:

从数组中最小的数字开始。以[1 1 1 2 1]为例，取值为1。原因是合并其他元素后不会得到新的1。所以它们很容易使用。

很明显，如果你有偶数个连续的1，合并它们从来都不是次优的。所以，我们需要决定如何处理奇数个连续元素。其中一个需要被省略(而不是合并)，一旦我们选择了那个，剩下的部分都有偶数个1。

这里的重要观察是，一旦您选择要忽略的元素，它左边的数组和它右边的数组构成两个独立的问题。因为中间会有一个1，所以你不能将左边和右边的任何数字合并。因此，对于每个可能的选择，您都可以递归地解决右子数组和左子数组的问题，然后找到最小结果。

算法总结一下该方法，以下是要遵循的步骤:

• 如果数组长度为0，则返回0。
• 查找数组中的最小元素。称之为x。
• 再次遍历数组，创建一个新数组，其中偶数个连续的x都被合并。
• 如果你在数组中看到一个奇数的x，这样做:
  • 设第一个元素的索引为i，对于每个j = i, i+2, i+4，…属于x序列，解决子数组[0 ..]的问题。[j+1]和[j+1 ..]结束)。将其结果称为n1和n2。
  • 从这些可能的分割中返回最小n1 + n2 + 1。
• 如果你没有看到奇数个x，那么数组中就没有x了。返回到步骤1

请注意，您可以在第4步中用x+1替换x，并相应地选择子问题索引，以可能节省递归调用中的一些工作。

下面是一段c++代码:

#include <iostream>
#include <limits>
#include <vector>
// the range is [start, end)
int
solve(std::vector<int>& array, int start, int end)
{
if (start >= end)
return 0;
int length = end - start;
// find the minimum element
int min = array[start];
for (int i = start; i < end; i++)
if (array[i] < min)
min = array[i];
std::vector<int> newArray;
newArray.reserve(length + 1);
int minCount = 0; // number of consecutive elements that are equal to min
int firstOddNumber =
-1; // index of an odd number of consecutive min's in the new array
int oddNumbers = 0; // number of min's starting at firstOddNumber
for (int i = start; i <= end; i++) {
// iterate one last time with i == end to run the checks again.
// hence the special case. we pop this element after the loop.
int elem = i < end ? array[i] : min + 1;
if (elem == min) {
minCount++;
} else if (minCount != 0) {
// even number of min's
if (minCount % 2 == 0) {
// merge them
for (int j = 0; j < minCount / 2; j++)
newArray.push_back(min + 1);
} else {
// do not merge them but save their index in the new array
firstOddNumber = newArray.size();
oddNumbers = minCount;
for (int j = 0; j < minCount; j++)
newArray.push_back(min);
// ^^^ this part could be modified as I wrote in the note in my
// answer
}
minCount = 0;
newArray.push_back(elem);
} else
newArray.push_back(elem);
}
// remove the min+1 element pushed when i == end
newArray.pop_back();
if (firstOddNumber == -1)
// no odd number of consecutive min's, repeat the procedure
return solve(newArray, 0, newArray.size());
else {
int minResult = newArray.size();
// solve two subproblems for each possible split
for (int i = firstOddNumber; i <= firstOddNumber + oddNumbers; i += 2) {
int result = 1 + solve(newArray, 0, i) +
solve(newArray, i + 1, newArray.size());
if (result < minResult)
minResult = result;
// ^^^ this part could be modified as I wrote in the note in my
// answer
}
return minResult;
}
}
void
test(std::vector<int> v, int expected)
{
int result = solve(v, 0, v.size());
std::cout << result << 'n';
if (result == expected)
std::cout << "CORRECTn" << std::endl;
else
std::cout << "EXPECTED: " << expected << 'n' << std::endl;
}
int
main()
{
test({ 1, 1, 1, 2, 1 }, 3);
test({ 1, 1, 1, 1, 1 }, 2);
test({ 1, 1, 1, 1, 1, 1 }, 2);
test({ 1, 2, 1, 1, 1 }, 3);
test({ 1, 2, 1, 2, 1 }, 5);
}

Answer 2

我假设这个问题需要从末尾读取输入，而不是从开始。因为如果它需要从一开始读取，那么第二次迭代必须是:[2,1,2,1]

假设问题需要从末尾读取输入，那么解决方案如下:

算法如下:

• 将所有元素添加到栈1。Stack1: [1,2,1,1,1];结果:[]and top = 1;

• 检查1和2是否相等，如果不相等则将其添加到结果堆栈中。结果:[2,1]

• 检查1和1是否相等，如果相等，将元素加1并将元素压入堆栈1，并将所有结果堆栈元素添加到堆栈1。Stack1: [1,2,2,1]， result: [].

• 重复此过程，直到stack1为空。

  类解决方案{public int mergeadjacentsimilareelements (int[] arr) {//栈1Stack = new Stack<>();//栈2

  = new Stack<>

  //add all the elements to the stack, as stack follows LIFO, the last element would be at the top
  for (int i = 0; i < arr.length; i++) {
  stack.push(arr[i]);
  }
  while (!stack.isEmpty()) {
  int top = !stack.isEmpty() ? stack.pop() : -1; // assign -1 in case stack is empty
  int temp = !stack.isEmpty() ? stack.peek() : -1; // assign -1 in case stack is empty
  //if top and temp are equal
  if (top != -1 && temp != -1 && top == temp) {
  stack.pop();
  //increment the value of the top, and add it to stack
  stack.push(++top);
  //check if there are any elements in the result stack, 
  // as they have to be added to stack1, as stack1 is modified.
  if (!result.isEmpty()) {
  stack.push(result.pop());
  }
  } else {
  //else simply add the element to the stack.
  result.push(top);
  }
  }
  //for testing
  result.stream().forEach(System.out::println);
  return result.size();
  }
  

  }