博客

codeforce Kalindrome Array题解**

题意

：给定一个数组，可以对这个数组进行以下操作：选定一个值，并且删除值x（可以删除零个x，一个x，两个x，三个x……）。进行操作之后，判断这个数组是不是回文串序列。是的话输出YES，反之输出NO。

思路 ：

1 ： 首先判断这个数组首字母和尾字母是否相等，如果相等，再继续向前判断

2： 如果这两个值不相等，就把这两个值的其中一个删掉，在进行判断

代码如下

// 首先判断首与尾是否相等，相等则继续向下判断 。 如果不相等，就把这个值删掉 再继续判断是不是相等
#include<bits/stdc++.h>
using namespace std ;
#define int long long
const int N = 1e6 + 99 ;
int a[N] , n , t , flag;
int check(int x){
	for(int i = 0 , j = n - 1 ; i < j ; i ++ , j -- ){
		while(a[i] == x) i ++ ;
		while(a[j] == x) j -- ;
		if(a[i] == a[j]) continue ;
		return 0 ; 
	}
	return 1 ;
}
void solve(){
	for(int i = 0 , j = n - 1 ; i < j ; i ++ , j -- ){
		if(a[i] == a[j]){
			continue ;
		}else{
			if(check(a[i]) == 1){
				flag = 1 ;               // 如果删掉a【i】 值 ，这个序列满足回文串。 
				return ;
			}
			if(check(a[j]) == 1){
				flag = 1 ;               // 同上 。 
				return ;
			}
			flag = 0 ;                   // 如果删掉两个值都不满足就直接退出，。 
			return ;
		}
	}
}
void print(){
	if(flag){
		cout << "YES" << endl ;
	}else{
		cout << "NO" << endl ;
	}
}
signed main(){
    cin >> t ;
	while(t --){
		cin >> n ; 
	    flag = 1 ;   // 0 代表 no ， 1 代表 yes 
		for(int i = 0 ; i < n ; i++ ){
			cin >> a[i] ;
		}
		solve() ;
		print() ;
	}	
	return 0 ;
} ```