c++ - 检查一个序列是否由两个相同的序列组成

Question

问题是找到一个 1<=n<=50000 元素的数字序列(1 到 10^5)，如果可以选择这样一个子序列，那么剩余的元素将创建所选子序列的另一个拷贝。换句话说，如果原始序列是由某些子序列的两个拷贝交织而成的。如果是这样，我们必须另外打印原始子序列。我的想法是天真地将同类的所有其他数字分成两个子序列。因此，例如，第一个子序列将得到第 1 个 5、第 3 个 5 和第 1 个 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]] << " ";
    }
}

Answer 1

您可以使用回溯来解决这个问题。还有一些优化可能。您知道第一个数字必须是序列的第一个数字。因此，该数字第一次出现和第二次出现之间的所有字母都必须按顺序排列。对于序列中的最后一个数字也是如此。此外，您可以检查是否还有足够的数字来完成序列。

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