[编程题]回文数索引

热度指数：1277 时间限制：1秒空间限制：262144K
算法知识视频讲解

给定一个仅由小写字母组成的字符串。现在请找出一个位置，删掉那个字母之后，字符串变成回文。请放心总会有一个合法的解。如果给定的字符串已经是一个回文串，那么输出-1。

输入描述:

第一行包含T，测试数据的组数。后面跟有T行，每行包含一个字符串。

输出描述:

如果可以删去一个字母使它变成回文串，则输出任意一个满足条件的删去字母的位置（下标从0开始）。例如：

bcc

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

示例1

输入

3
aaab
baa
aaa

输出

3
0
-1

算法知识视频讲解

Bostonpigeons

#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)

天启_dummkopf


	#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)

赵康201810220933360

#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)

Polestar_a

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)

LongXiaJun

"""
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)

zehong

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)

C/C++

为月未央


	// 本题的关键是找那个不匹配的点，跳出就可



	#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)

Java

梦想永恒

每个字符串从两头开始找，两边不相等，就是两种情况，要么左边往右下，要么右边往左下！

这个题给的比较死，字符串去掉一个肯定就是回文，所以就不用判断了，直接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)

laoqin

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)

浅滩qaq

#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)

C/C++

leishall

#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)

生日愿望求offer

#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)

您201810161418815

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)

longyin

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)

monsterlxf

#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)

zkfopen


	#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;



	}