首页 > 试题广场 > 回文数索引
[编程题]回文数索引
给定一个仅由小写字母组成的字符串。现在请找出一个位置,删掉那个字母之后,字符串变成回文。请放心总会有一个合法的解。如果给定的字符串已经是一个回文串,那么输出-1。

输入描述:
第一行包含T,测试数据的组数。后面跟有T行,每行包含一个字符串。


输出描述:
如果可以删去一个字母使它变成回文串,则输出任意一个满足条件的删去字母的位置(下标从0开始)。例如:

bcc

我们可以删掉位置0的b字符。
示例1

输入

3
aaab
baa
aaa

输出

3
0
-1
#include<iostream>
#include<bits/stdc++.h>
#include<cstring>
usingnamespacestd;
string s;
intjudge(inta){
string s1;
for(inti=0;i<s.length();i++){
if(i==a) continue;
s1+=s[i];
}
//   cout<<s1<<endl;
for(inti=0;i<=s1.length()/2;i++){
if(s1[i]!=s1[s1.length()-i-1]) return0;
}
cout<<a<<endl;
return1;
}
intmain()
{
intn;
cin>>n;
//string s;
for(inti=0;i<n;i++){
cin>>s;
if(judge(-1)) continue;
for(intj=0,k=s.length()-1;j<=(s.length()/2);j++,k--){
if(s[j]!=s[k]){
if(!judge(j)) cout<<k<<endl;
break;
}
}
}
return0;
}

编辑于 2019-06-13 23:12:05 回复(0)
#include<bits/stdc++.h>
using namespace std;
string aa;
int main()
{
    int line,len,i,k,j;
    int count,cas;
    cin>>line;
    count=0;
    for(k=0;k<line;k++)
    {
        cin>>aa;
        len=aa.length();
        for(i=0,j=len-1;i<j;i++,j--)
        {
            if(aa[i]==aa[j]) cas=-1;
            else
            {
                if(aa[i]==aa[j-1])  cas=j;
                else cas=i;
                break;
            }
        }
        if(cas==-1)  printf("-1\n");
        else printf("%d\n",cas);
    }
}

发表于 2019-07-26 21:39:02 回复(0)
#include <bits/stdc++.h>
usingnamespacestd;
boolcal(string s,intindex){
    vector<char> a,b;
    auto ite=s.begin();
    s.erase(ite+index);
    intn=s.size();
    if(s[0] != s[n-1]) returnfalse;
    for(inti=0;i<n;++i){
        a.push_back(s[i]);
        b.push_back(s[n-i-1]);
    }
    returna==b;
}
boolcal(string s){
    vector<char> a,b;
    intn=s.size();
    if(s[0] != s[n-1]) returnfalse;
    for(inti=0;i<n;++i){
        a.push_back(s[i]);
        b.push_back(s[n-i-1]);
    }
    returna==b;
}
intmain(void){
    vector<int> res;
    intn=0;
    cin>>n;
    for(inti=0;i<n;++i){
        string s;
        cin>>s;
        intn=s.size();
        if(cal(s)){
            res.push_back(-1);
            continue;
        }
        for(intj=0;j<n;++j){
            if(cal(s,j)){
                res.push_back(j);
                break;
            }
        }
    }
    for(inti=0;i<res.size();++i){
        cout<<res[i]<<endl;
    }
    return0;
}

发表于 2019-06-26 14:26:12 回复(0)
#include<string>
#include<iostream>
using namespace std;
bool FlagError = false;
int isHW(string str,int left,int right)//回文数判断
{
    while(left < right)
    {
        if(str[left]==str[right])
        {
            left ++;
            right --;
        }
        else if(!FlagError)
        {
            FlagError = true;
            if(isHW(str,left+1,right)!=-2)
            {
                return left;
            }
            else if(isHW(str,left,right-1)!=-2)
            {
                return right;
            }
        }
        else
            return -2;//无法纠正
    }
    return -1;//输入原本就是一个回文串
}
int main()
{
    int num = 0;
    string str;
    cin>>num;
    while(num--)
    {
        FlagError = false;
        cin>>str;
        cout<<isHW(str,0,str.size()-1)<<endl;
    }
    return 0;
}
 

发表于 2019-06-09 14:48:28 回复(0)
n = int(input())
res =[]
for i in range(n):
    res.append(input())
for i in res:
    start,end,flag = 0,len(i)-1,False
    while(start<=end):
        if i[start]!=i[end]:
            if i[start]==i[end-1]:
                print(end)
                flag=True
                break
            elif i[end]==i[start+1]:
                print(start)
                flag=True
                break
        start+=1
        end-=1
    if not flag: print(-1)

发表于 2019-08-12 11:59:29 回复(0)
"""
1. 首先排除回文串情况
2. 处理每个字符串,两个前后指针,判断是否相等,如果不相等,判断x[i+1]与x[j]相等,则删除i,反之如果x[i]与x[j-1]相等,则删除j
"""


n = int(input().strip())

def func(x):
    if x == x[::-1]:
        return -1
    else:
        j = len(x) - 1
        for i in range(len(x)):
            if x[i] != x[j]:
                if x[i] == x[j-1]:
                    return j
                elif x[i+1] == x[j] :
                    return i
            j -= 1
                

for i in range(n):
    line = input().strip()
    print(func(line))
发表于 2019-08-01 15:32:39 回复(0)
def helper(s):
    l = 0
    r = len(s)-1
    count = -1
    while l < r:
        if s[l] != s[r]:
            if s[l+1] != s[r]:
                count = r
            else:count = l
            break
        l += 1
        r -= 1
    return count

n = int(input())
for i in range(n):
    s = input()
    print(helper(s))

发表于 2019-07-31 22:05:37 回复(3)
// 本题的关键是找那个不匹配的点,跳出就可
#include<iostream>
#include<string>
using  namespace std;
int main(){
    int n, i, j;
    string s;
    cin>>n;
    for(i=0; i<n; i++){
        cin>>s;
        int left = 0, right = s.size()-1, res = -1;
        while(left<right){
            if(s[left] != s[right]){
                if(s[left+1] == s[right]){
                    res = left;
                }else if(s[left] == s[right-1]){
                    res = right;
                }
                break;
            }
            left++;
            right--;
        }
        cout<<res<<endl;
    }
    return 0;
}
发表于 2019-07-31 20:54:18 回复(0)
每个字符串从两头开始找,两边不相等,就是两种情况,要么左边往右下,要么右边往左下!
这个题给的比较死,字符串去掉一个肯定就是回文,所以就不用判断了,直接break
如果一直执行到两个之间只差2以内了,那就是字符串本身就是回文!

import java.math.BigInteger;
import java.util.*;
 public class Main {
     public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int num=sc.nextInt();
        String string=sc.nextLine();
        for (int i = 0; i < num; i++) {
        char [] array= sc.nextLine().toCharArray(); 
        for(int j=0,k=array.length-1;j<k;j++,k--)
        {    
            if(array[j]!=array[k])
            {
                if(array[j]==array[k-1])
                    System.out.println(k);    
                if(array[j+1]==array[k])
                    System.out.println(j);
                break;            
            }    
            if(j+2>=k)
                System.out.println(-1);    
            }
        }            
     }    
 }
发表于 2019-07-26 19:53:44 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] str = new String[n];
        int[] index = new int[n];
        for(int i = 0; i < n; i++){
            str[i] = sc.next();
        }
        for(int i = 0; i < n; i++){
            index[i] = getNumber(str[i]);
        }
        for(int i = 0; i < n; i++){
            System.out.println(index[i]);
        }
        
    }
    
    //判断字符串是否回文
    public static boolean isHuiwen(String str){
        int len = str.length();
        String str1 = "";
        boolean flag = false;
        for(int i = 0; i < len; i++){
            str1 = str1 + str.charAt(len - 1 - i);
        }
        if(str1.equals(str))flag = true;
        return flag;
    }
    
    //删除一个字母后回文,返回删除字母的位置
    public static int getNumber(String s){
        int index = -1;
        int len = s.length();
        boolean flag = isHuiwen(s);
        if(flag == true){
            index = -1;
        }else{
            for(int i = 0; i < len; i++){
                String str = delete(s, i);
                boolean f = isHuiwen(str);
                if(f == true){
                    index = i;
                    break;
                }
            }
        }
        return index;
    }
    //删除位置n上的字母
    public static String delete(String str, int n){
        int len = str.length();
        String str1 = "";
        for(int i = 0; i < len; i++){
            if(i == n){
                continue;
            }else{
                str1 = str1 + str.charAt(i);
            }
        }
        return str1;
    }
}
发表于 2019-07-26 15:45:32 回复(0)
好像可以不用动态规划啊,两头走就可以了
#include <iostream>
#include<string>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<ctime>
#include<fstream>
#include<string.h>
#define N 1005
using namespace std;
int main()
{
 string s;
 int n,i,j,k;
 bool flag;
 cin>>n;
 for(k=0;k<n;k++)
 {
  flag=false;
  cin>>s;
  for(i=0,j=s.length()-1;i<j;i++,j--)
  {
   if(s[i]!=s[j])
   {
    flag=true;
    if(s[i]==s[j-1])
     cout<<j<<endl;
    else
     cout<<i<<endl;
    break;
   }
  }
  if(!flag)
   cout<<"-1"<<endl;
 }
 return 0;
}

发表于 2019-07-20 15:34:42 回复(0)
#include“iostream”#include“cstring”#include“string”#include“algorithm”#include“cmath”#include“set” using namespace std;bool judge(int size,const string&s){for(int i = 0; i <size / 2; i ++){    if(s [i]!= s [s.size() -  1-i])返回true ; //需要删除 } return false; }int main(){int size;string str;cin>>size; while(size  - > 0){cin >> str;if(judge(str.size(),str)== false)cout <<  -  1 << endl;else {int f = 0;for(int i = 0; i <str.size(); i ++){if(f == 1)break;string copy = str;                                             for(int j = 0; j <str.size() -  1; j ++){            if(judge(tmp.size(),tmp)== false){                cout << i << endl; f = 1; break ;            }        }    }}} }               

发表于 2019-07-20 14:16:12 回复(0)
N = int(input())
for _ in range(N):
    s = input()
    ls = len(s)
    if ls <= 0:
        print(-1)
    p = -1
    for i in range(ls//2+1):
        if s[i] != s[-i-1]:
            if s[i+1] == s[-i-1]:
                p = i
            else:
                p = ls - i - 1
            break
    print(p)

编辑于 2019-07-17 20:06:37 回复(0)
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int desthw(string str, int min, int max)
{     while (min < max)     {         if (str[min] == str[max])         {             min++;             max--;         }         else             return 0;     }     return -1;
}

int find(string &str, int min, int max)
{     int back;     back = desthw(str, 0, max);     if (back == -1)         return back;     while (min < max)     {         if (str[min] == str[max])         {             min++;             max--;         }         else         {             if (str[min + 1] == str[max])                 return min;             else                 return max;         }     }     return 0;
}

int main()
{     int num = 0;     string str;     cin >> num;     vector<int> arr;     while (num--)     {         cin >> str;         arr.push_back(find(str, 0, str.size()-1));     }     for (auto &x : arr)         cout << x << endl;     return 0;
}

编辑于 2019-07-17 17:53:19 回复(0)

暴力解法

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int cnt = 0;
        while(cnt < N) {
            StringBuilder sb = new StringBuilder(sc.next());
            if(helper(sb.toString().toCharArray())) {
                System.out.println(-1);
            }              
            else {
                for(int i = 0;i < sb.length();i++) {
                    char ch = sb.charAt(i);
                    if(helper(sb.deleteCharAt(i).toString().toCharArray())){
                        System.out.println(i);
                        break;
                    }
                    sb.insert(i, ch);
                }  
            }  
            cnt++;
        }                      
    }

    public static boolean helper(char[] chs) {
        int s = 0, end = chs.length-1;
        while (s < end) {
            if(chs[s] != chs[end])
                return false;
            s++;
            end--;
        }
        return true;
    }
}
编辑于 2019-07-15 22:32:23 回复(0)
#include <iostream>
#include <string.h>
#include<stdlib.h>
using namespace std;
int method(char * src, int length)
{     char *p = src;     int flag = 0;     for (int i = 0; i<length / 2; i++)     {         if (p[i] == p[length - i - 1])             continue;         else         {             flag = 1;             break;         }     }     if (flag == 0)         return 1;//是回文     else         return 0;//不是回文 }
int M(char *src, int num, int length)
{     char *s = src;     char *p = (char *)malloc(sizeof(char)*length - 1);     //bzero(p, 0, sizeof(p));     memset(p, 0, sizeof(p));     int j = 0;     for (int i = 0; i<length; i++)     {     //    j = i;         if (i != num)         {                        p[j]=src[i];             j++;         }     }     if (method(p, strlen(p)) == 1)         return num;     else         return -1; }
int main()
{     int n;     cin >>n;     while (n--)     {         char *s = (char *)malloc(sizeof(char) * 100);         cin >> s;         int length = strlen(s);         int ret = method(s, length);         int i;         if (ret == 1)             cout << -1<<endl;         else {             for (i = 0; i < length; i++)             {                 //删除元素,返回值指向已删除元素的下一个位置                 if (M(s, i, length) != -1)                     break;                 //指向下一个位置             }             cout << i<<endl;         }     } }

编辑于 2019-07-08 15:16:34 回复(0)
t=int(input())
while True:
    try:
        s=input()
        if s==s[::-1]:
            print(-1)
        else:
            for i in range(len(s)):
                a=s[:i]+s[i+1:]
                if a==a[::-1]:
                    print(i)
    except:
        break

发表于 2019-07-07 20:14:32 回复(0)
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        
        for (int i = 0; i < len; i++) {
            String str = sc.next();
            findIndex(str);
        }
    }
    
    private static void findIndex(String str) {
        char[] strCharArr = str.toCharArray();

        int len = strCharArr.length;
        int left = 0;
        int right = len - 1;
        
        while(left <= right && strCharArr[left] == strCharArr[right]) {
            left++;
            right--;
       }
       
        int index = -1;
        if (left > right) {
            index = -1;
        } else if (strCharArr[left+1] == strCharArr[right]) {
            index = left;
        }else if (strCharArr[left] == strCharArr[right-1]) {
            index = right;
        }
        
        System.out.println(index);
    }
}

发表于 2019-07-06 17:56:38 回复(0)
#include<iostream>
#include<string>
usingnamespacestd;
inthuiwen(string &str){
    intn=str.size();
    inti=0,j;
    j=n-1;
    for(i=0;i<=n/2;i++)
    {
        if(str[i]==str[j])
        {
             
            j--;
        }
        else
        {
            i++;
            if(str[i]==str[j])
            {
                returni-1;
            }
            else{
                returnj;
                 
            }
        }
    }
    return-1;
     
}
intmain(){
    intT;
    cin>>T;
    string S[T];
    for(inti=0;i<T;i++)
    {
        cin>>S[i];
    }
    intn;
    for(inti=0;i<T;i++)
    {
        n=huiwen(S[i]);
        cout<<n<<endl;
    }
    return0;
     
发表于 2019-06-29 21:19:24 回复(0)
#include <iostream>
#include <string>
usingnamespacestd;
 
//判断回文
boolisHW(string str,intloc)
{
    if(loc!= -1)
        str = str.erase(loc,1);
    intlen = str.length();
    for(inti = 0; i <len / 2; i ++)
        if(str [i]!= str [len-1-i])
            returnfalse;
 
    returntrue;
}
 
inttest(string str)
{
    if(isHW(str,-1))
        返回-1;
 
    intlen = str.length();
    for(inti = 0; i <len; i ++)
    {
        if(isHW(str,i))
        {
            RETURNI;
        }
             
    }
     
    返回-1;
}
 
intmain(intargc,char ** argv)
{
    INTT;
    而(cin >> T)
    {
        string str;
        而(T--)
        {
            cin >> str;
            intres = test(str);
            cout << res << endl;
        }
    }
     
    return0;
}

发表于 2019-06-27 17:41:12 回复(0)