回文数索引

[编程题]回文数索引

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

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

输入描述:

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

输出描述:

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

bcc

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

示例1

输入

3
aaab
baa
aaa

输出

3
0
-1

算法知识视频讲解

Java

lmz9509

/*
思路：回文数函数，每次去掉一个数后进行判断
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i = 0;i<N;i++){
            String str = br.readLine();
            if(isHui(str)){
                System.out.println(-1);
                continue;
            }else{
                for(int j = 0;j<str.length();j++){
                    if(j==0){
                        String newstr = str.substring(1);
                        if(isHui(newstr)){
                            System.out.println(j);
                            break;
                        }
                    }else if(j== str.length()-1){
                        String newstr = str.substring(0,j);
                        if(isHui(newstr)){
                            System.out.println(j);
                            break;
                        }
                    }else{
                        String newstr = str.substring(0,j) + str.substring(j+1);
                        if(isHui(newstr)){
                            System.out.println(j);
                            break;
                        }
                    }
                }
            }
        }
    }
    
    public static boolean isHui(String str){
        if(str.length()<=1)return true;
        int left = 0,right = str.length()-1;
        while(left<right){
            if(str.charAt(left) == str.charAt(right)){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }
}

发表于 2020-05-20 16:27:22 回复(0)

Java

你的offer对我打了烊

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        for(int k = 0;k < n;k++){
            findIndex(sc.nextLine());
        }
    }
    
    public static void findIndex(String str){
        int i = 0;
        int j = str.length() - 1;
        while(i < j){
            if(str.charAt(i) != str.charAt(j)){
                if(str.charAt(i) != str.charAt(i+1) && str.charAt(j) == str.charAt(i+1)){
                    System.out.println(i);
                    return;
                }else{
                    System.out.println(j);
                    return;
                }
            }
            i++;j--;
        }
        System.out.println(-1);
    }
}

脑子笨，就只能暴力法玩玩了

发表于 2020-03-21 20:27:30 回复(2)

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)