Problem
题目简述
给你一个数列 \(a\)，有这两种情况，这个数列是「可爱的」。
- 它本身就是回文的。
- 定义变量 \(x\)，满足：序列 \(a\) 中所有值等于 \(x\) 的元素删除之后，它是回文的。
思路
首先考虑暴力。暴力枚举数组中的每一个数，当作变量 \(x\)，然后进行回文检验。
时间复杂度 \(O(n^2)\)，严重超时。
然后考虑如何优化。
根据回文判断的方法，我们很容易想到：双指针的优化。
设变量 \(l\) 和 \(r\)，初始值分别为 \(1\) 和 \(n\)。如果扫描到 a[l] != a[r] 的情况，用两个变量记录一下它们的值，然后停止循环。
然后删除 \(a\) 数组中值为 \(a_l\) 或者是 \(a_r\) 的数字，看看删除之后是否满足回文的条件。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int t, n, a[N], tmp[N];
bool ishuiwen(int n, int b[]) { // 是否是回文
for (int i = 1; i <= n; i++) {
if (b[i] != b[n - i + 1]) return false;
}
return true;
}
bool check(int x) { // 检验删除值为x的情况下是否满足回文
int idx = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != x) tmp[++idx] = a[i];
}
return ishuiwen(idx, tmp);
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
if (ishuiwen(n, a)) { // 本身就满足条件
printf("YES\n");
continue;
}
int l = 1, r = n, x, y;
while (l <= r) {
if (a[l] != a[r]) { // 不满足，删数字
x = a[l], y = a[r];
break;
} else l++, r--;
}
if (check(x) || check(y)) printf("YES\n"); // 只要一个满足条件就可以
else printf("NO\n");
}
return 0;
}