c++ - 检查一个序列是否由两个相同的序列组成
问题描述
问题是找到一个 1<=n<=50000 元素的数字序列(1 到 10^5),如果可以选择这样的子序列,那么其余元素将创建所选子序列的另一个副本。换句话说,如果原始序列是由某些子序列的两个副本交织而成的。如果是这样,我们必须额外打印原始子序列。我的想法是天真地将所有其他相同类型的数字分成两个子序列。因此,例如,第一个子序列将得到第 1 个 5、第 3 个 5 和第 4 个,而第二个子序列将得到第 2 个 5、第 4 个 5 和第 2 个 4。我认为该序列不能表示为两个副本的组合,如果它里面有一些奇数个数。然而,整个方法是错误的,很少能给出好的答案;
请帮我找到一个更聪明的算法来真正解决这个问题。为了更好地理解(C++),我实现了简单的方法:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<short> arr(n);
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
}
vector<vector<unsigned short>> positions(10001, vector<unsigned short>(0));
for (int i = 0; i < n; ++i)
{
positions[arr[i]].push_back(i);
}
vector<unsigned short> out;
for (int i = 0; i <= 10000; ++i)
{
if (positions[i].size() % 2)
{
cout << "NO" << "\n";
return 0;
}
for (int j = 0; j < positions[i].size(); j += 2)
{
out.push_back(positions[i][j]);
}
}
sort(out.begin(), out.end());
cout << "YES" << "\n";
for (int i = 0; i < out.size(); ++i)
{
cout << arr[out[i]] << " ";
}
}
解决方案
您可以使用回溯来解决此问题。还有一些可能的优化。你知道第一个数字必须是序列的第一个数字。所以这个数字的第一次和第二次出现之间的所有字母都必须按顺序排列。对于序列中的最后一个数字也是如此。此外,您可以检查是否有足够的数字来完成序列。
public int[] solve(int[] arr) {
if (arr.length % 2 != 0)
return null;
int[] solution = new int[arr.length / 2];
if (solve(arr, 0, 0, solution))
return solution;
return null;
}
private boolean solve(int[] arr, int i, int j, int[] solution) {
if (i == j) {
solution[i] = arr[i + j];
return solve(arr, i + 1, j, solution);
} else if (i == solution.length) {
for (int k = 0; k + i + j < arr.length; k++)
if (arr[k + i + j] != solution[j + k])
return false;
return true;
} else {
for (int k = 0; i + k <= solution.length; k++) {
if (arr[i + j + k] == solution[j] && solve(arr, i + k, j + 1, solution))
return true;
if (i + k < solution.length)
solution[i + k] = arr[i + j + k];
}
return false;
}
}
这只是从左到右而不是从两端检查。其他可能的改进:
- 检查每个数字的计数是否在开始时是偶数
- 跟踪数字计数,以便您更早知道一个数字何时不能再进入第一个序列,因为它已经有一半
它是 Java 代码,但可以很容易地转换为 C++。数组通过引用传递。我测试了一些简单的案例,并且对于那些有效的案例。
通过记忆,我可以在几毫秒内轻松解决多达 50000 个问题。但我不得不将堆栈大小增加到 100M。您可能希望将其重写为迭代解决方案而不是递归解决方案。
public static int[] solve(int[] arr) {
if (arr.length % 2 != 0)
return null;
int[] solution = new int[arr.length / 2];
if (solve(arr, 0, 0, solution, new Node(null, null)))
return solution;
return null;
}
private static boolean solve(int[] arr, int i, int j, int[] solution, Node node) {
if (node.checked)
return false;
if (i == j) {
if (node.children.containsKey(arr[i + j]))
node = node.children.get(arr[i + j]);
else
node = new Node(node, arr[i + j]);
if (node.checked)
return false;
solution[i] = arr[i + j];
Node n = new Node(node, solution[i]);
if (solve(arr, i + 1, j, solution, n))
return true;
n.checked = true;
return false;
} else if (i == solution.length) {
for (int k = 0; k + i + j < arr.length; k++)
if (arr[k + i + j] != solution[j + k]) {
node.checked = true;
return false;
}
return true;
} else {
Node n = node;
for (int k = 0; i + k <= solution.length; k++) {
if (arr[i + j + k] == solution[j] && solve(arr, i + k, j + 1, solution, n))
return true;
if (i + k < solution.length) {
if (n.children.containsKey(arr[i + j + k]))
n = n.children.get(arr[i + j + k]);
else
n = new Node(n, arr[i + j + k]);
if (n.checked)
return false;
solution[i + k] = arr[i + j + k];
}
}
node.checked = true;
return false;
}
}
private static class Node {
public boolean checked;
public Map<Integer, Node> children = new HashMap<>();
public Node(Node parent, Integer value) {
if (parent != null)
parent.children.put(value, this);
}
}
推荐阅读
- excel - Delphi - 使用 VarArrayCreate 循环遍历 Excel 数据范围
- python - How to remove <_io.TextIOWrapper name='xyz.txt' mode='w' encoding='UTF-8'> from file?
- java - 我应该怎么做才能获得我的 javafx spring boot 桌面应用程序的 OAuth2 访问令牌?
- mysql - MySQL:查询奇怪的行为 - 在 FROM 之前需要新行才能成功
- amazon-web-services - 如何将 Sentry 设置为 AWS lambda 函数?很多错误
- java-8 - 为什么流不受限,limit() 之前有 filter() 吗?
- php - 计算多个数组的匹配元素
- r - 为数据框中的每个唯一组复制行
- android - 片段中的getColor
- c++ - 计算直角三角形:如何提高时间复杂度?