第一行包含T,测试数据的组数。后面跟有T行,每行包含一个字符串。
如果可以删去一个字母使它变成回文串,则输出任意一个满足条件的删去字母的位置(下标从0开始)。例如:
bcc
我们可以删掉位置0的b字符。
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; } |
#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; }
""" 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))
#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;}
#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; }
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; } }
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)
// 本题的关键是找那个不匹配的点,跳出就可#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;}
好像可以不用动态规划啊,两头走就可以了 #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; }
#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 ; } } }}} }
#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; }
暴力解法
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; } }
#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; } } }