如何从数字列表中指示最长的回文？

Question

我正在尝试解决一个问题，该问题说我们需要编写一个函数，在该函数中给定一个数字列表，我们需要从仅给定列表中的数字中找到最长的回文。

例如：

如果给定的列表是：[3,47,6,6,5,6,15,22,1,6,15]

我们可以return最长的回文是长度为9的一个，例如[6,15,6,3,47,3,6,15,6]。

此外，我们还有以下限制条件：

一个人只能使用数组队列、数组堆栈和链接哈希图，而我们应该return 的列表，并且函数必须在线性时间内运行。而我们只能使用常量附加 space.

我的方法如下：

由于偶数个字符可以构成回文，我们可以遍历列表中的所有元素，并将每个数字在列表中出现的次数存储在链表中。这应该花费 O(N) 时间，因为链接哈希映射中的每次查找都需要常数时间，并且遍历列表需要线性时间。

然后我们可以遍历chaining hash map中的所有数字，看哪些数字出现了偶数次，据此做回文。在最坏的情况下，这将花费 O(n) 线性时间。

现在有两件事我想知道：

真正的回文应该怎么做？比如我如何使用允许我使用的数据结构来制作回文？我在想，由于队列是一个 LIFO 数据结构，对于出现偶数次的每个数字，我们将它一次添加到队列中，一次添加到堆栈中，依此类推。最后，我们可以将队列中的所有内容出列，然后从堆栈中弹出一次，然后将其添加到列表中！
看来用我的方法，我用了两个线性运行来解决这个问题。我想知道是否有更快的方法来做到这一点。

我们将不胜感激任何帮助。谢谢！

Answer 1

当它的回文只针对数字而不是数字时，我有一个解决方案。对于输入：[51,15] 我们将 return [15] || [51] 而不是 [51,15] =>(5,1,1,5)；将您的示例作为问题 3 没有出现两次（并出现在答案中）或者我没听懂问题。

public static int[] polidrom(int [] numbers){
        HashMap<Integer/*the numbere*/,Integer/*how many time appeared*/> hash = new HashMap<>();
        boolean middleFree= false;
        int middleNumber = 0;
        int space = 0;
        Stack<Integer> stack = new Stack<>();
        for (Integer num:numbers) {//count how mant times each digit appears
            if(hash.containsKey(num)){hash.replace(num,1+hash.get(num));}
            else{hash.put(num,1);}
        }
        for (Integer num:hash.keySet()) {//how many times i can use pairs
            int original =hash.get(num);
            int insert = (int)Math.floor(hash.get(num)/2);
            if(hash.get(num) % 2 !=0){middleNumber = num;middleFree = true;}//as no copy
            hash.replace(num,insert);
            if(insert != 0){
                for(int i =0; i < original;i++){
                    stack.push(num);
                }
            }
        }

        space = stack.size();
        if(space == numbers.length){ space--;};//all the numbers are been used
        int [] answer = new int[space+1];//the middle dont have to have an pair
        int startPointer =0 , endPointer= space;
        while (!stack.isEmpty()){
            int num = stack.pop();
            answer[startPointer] = num;
            answer[endPointer] = num;
            startPointer++;
            endPointer--;
        }
        if (middleFree){answer[answer.length/2] = middleNumber;}
        return answer;
    }

space O(n) => {stack , hashMap , answer Array}; 复杂度：O(n) 您可以跳过我使用堆栈的部分，并在同一个循环中构建答案数组。而且我想不出一种你不会至少迭代两次的方法；希望我帮到了你

Answer 2

不可能找到比 O(n) 更好的算法，因为必须检查输入中的每个数字，因为它可能提供一种可能性对于更长的回文。如果确实输出必须是最长的回文本身（而不仅仅是它的长度），那么产生该输出本身代表 O(n).

您还遗漏了在算法中必须做的另一件事：在最后的回文中可以有一个值只出现一次（在中心）。因此，每当您遇到一个出现奇数次的值时，您可以保留该值的一次出现以放在 odd-length 回文的中间。偶数余数可以照常使用。

关于您的问题：

How should I make the actual palindrome?

有很多方法可以做到。但是不要忘记，如果出现的次数是偶数，则应该使用 all 这些出现次数，而不仅仅是两次。所以将其中一半加入队列，一半加入栈。当频率为奇数时，仍然这样做（向下舍入），并将数字也记录为潜在的中心值。

当您对所有值都完成此操作后，然后按照您的建议将队列和堆栈一起转储到结果列表中，但如果您确定了这样的中心，请不要忘记将中心值放在两者之间值（即当并非所有事件都是偶数时）。

It seems that with my approach, it is taking me two linear runs to solve the question.

没有比使用线性时间复杂度更好的方法了。如果将堆栈也用于结果，则可以节省一些时间，并且只需将队列转储到堆栈（在可能推送中心值之后）。

如何从数字列表中指示最长的回文？

How to instruct longest palindrome from a list of numbers?

algorithm

palindrome

data-structures