[编程题]回文数索引

热度指数：2262 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int T;
    cin>>T;
    while(T--){
        cin>>s;
        int l = s.length(), p=-1;
        string t(s.rbegin(), s.rend());
        for(int i=0;i<l;i++)
            if(s[i]!=t[i]){
                p = (s[i]==t[i+1])?l-i-1:i;
                break;
            }
        cout<<p<<endl;
    }
    return 0;
}

发表于 2019-11-03 01:22:21 回复(0)

小蝌蚪666

#include <iostream>
using namespace std;
int main(void){
    string s;
    int T;
    cin>>T;
    while(T--){
        cin>>s;
        string r(s.rbegin(), s.rend());
        int i, len = s.length(), res = -1;
        for(i = 0; i < len; ++i){
            if(s[i] != r[i]){
                res = (s[i] == r[i+1]) ? len-i-1 : i;
                break;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

回文字符串的特点是正向反向输出都是一样的，利用这个特点，每次读取一个字符串s，将其反转得到新的字符串r，再从下标0开始逐个比较s，r，如果遇到s[i]不等于r[i]，说明在这个位置上出现了那个唯一的干扰字符，但是注意，这个并不是最终的答案！！！

以abb为例，反转之后得到bba，进行比较得到i=0时s[i]='a'不等于r[i]='b'，这个时候把abb中0位置的a去掉得到bb是回文没问题，但如果一开始的字符串是bba呢？比较的结果还是i=0，但是答案应该是2！出现这个问题的原因在于不能确定插入的干扰字符是在原来回文字串的左边部分还是右边部分，这个时候要看s[i]和r[i+1]的关系，如果s[i]不等于s[i+1]，说明插入干扰字符在回文串的左边，也就是正确答案就是i，否则的话正确答案应该是i在以字符串中心对称的位置len-i-1

编辑于 2019-08-23 17:20:53 回复(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)

张小公爷

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

天启ddd


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

fulanda1

#include<iostream>

#include<string>

#include<vector>

usingnamespacestd;

boolIsHuiwen(string s) {

intnum = s.length();

inti = 0;

intj = num - 1;

while(i < j) {

if(s[i] != s[j]) {

returnfalse;

}

i++;

j--;

}

returntrue;

}

intDelNum(string s) {

if(IsHuiwen(s)) { return-1; }

string temp1 = s;

for(inti = 0; i < s.length(); i++) {

string temp1 = s;

temp1.erase(i,1);

if(IsHuiwen(temp1)) {

returni;

}

intmain() {

intn;

cin >> n;

vector<string>input;

string temp;

for(inti = 0; i < n; i++) {

cin >> temp;

input.push_back(temp);

}

for(inti = 0; i < n; i++) {

cout << DelNum(input[i]) << endl;

}

return0;

}

发表于 2019-11-17 18:40:30 回复(0)

乌托邦的难民

import java.util.*;
public class 回文数索引 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		String s = null;
		for(int i = 1; i <= n; i++) {
			s = sc.nextLine();
			System.out.println(getHuiwen(s));
		}
	}
	//善于使用方法模块化解决问题
	//判断一个字符串是否为回文字符串的方法
	public static boolean isHuiwen(String s) {
		if(s.length() == 0) return false;
		int i = 0;
		for(; i < s.length()/2; i++)
			if(s.charAt(i) != s.charAt(s.length()-1-i))
				break;
		if(i >= s.length()/2) return true;
		else return false;
	}
	
	//得到合适的删除位置所生成的回文字符串
	public static int getHuiwen(String s) {
		if(isHuiwen(s)) return -1;
		for(int i = 0; i < s.length(); i++) {
			String temp = null;
            //String类两个方法进行字符串的截取和连接形成新的字符串
			temp = s.substring(0, i);
			temp = temp.concat(s.substring(i+1, s.length()));
			if(isHuiwen(temp)) return i;
		}
		return -1;
	}

}

发表于 2019-10-28 21:20:35 回复(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)

lzher0

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