我编写了一个又长又复杂的方法来检查队列中的元素列表是否是回文。我知道它可以改进,但我现在的目标是让它通过实践中的所有测试。我已经通过了十分之九的测试,但我似乎唯一无法通过的测试是奇数元素/不是回文。
例如: 前面 [5, 10, -1, 4, 3, 2, 2, 4, -1, 10, 5] 后面。预期输出应为 FALSE。我的输出是 TRUE。
此外,与其他测试不同,队列中的元素不会显示。与之前提出的与此问题类似的问题不同,我的队列必须恢复到其原始状态。这是到目前为止我的代码:
public static boolean isPalindrome(Queue<Integer> q) {
Stack<Integer> s = new Stack<Integer>();
int size = q.size();
int extra = 0;
if(q.isEmpty())
return true;
else
if (size % 2 == 0) {
for (int i = 0; i < size / 2; i++) {
s.push(q.remove());
}
while (!s.isEmpty()) { // While Stack is not empty:
if (s.peek() != q.peek()) {
int first = s.pop();
s.push(q.remove());
s.push(first);
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty()) {
q.add(s.pop());
}
return false;
}
else {
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty()) {
q.add(s.pop()); // Restore Queue to original order
}
return true;
}
}
for (int k = 0; k < size / 2; k++) {
q.add(q.remove());
s.push(q.remove());
}
for (int l = 0; l < size / 2; l++)
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
}
return true;
}
如果有人在阅读本文时遇到困难,或者可以提出一种使其不那么复杂的方法,我将不胜感激。谢谢您,再次对臃肿的代码表示歉意。
最佳答案
为什么不使用简单的算法,它不在乎过程中是否会破坏队列,而是第一步复制队列?
public static boolean isPalindrome(Queue<Integer> q) {
return isPalindromeDestructive(copyQueue(q));
}
private static boolean isPalindromeDestructive(Queue<Integer> q) {
//Destructive algorithm that treats q as disposable.
}
private static Queue<Integer> copyQueue(Queue<Integer> q) {
return new LinkedList<Integer>(q);
}
您可以根据需要实现 copyQueue,但这可行。
关于使用队列的Java回文检查器并将队列恢复到原始状态,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24293910/