Java在线笔试编程（3）---计算回文序列

Dear 丶 2022-09-25 15:25 138阅读 0赞

这篇文章和上篇一样，都是关于统计回文的，本篇有2个题目，第1个是搜狗的，第2个是网易的。

搜狗题目如下：

输入描述

一个文本文件，至少包含一个字节，每个字节都是一个字符。最大长度可能有几十万字节。

输出：

最大回文前缀的长度

**样例输入：**

sogou

**样例输出：**

参考代码如下：

import java.util.Scanner;
    
    public class Main{
    
    	public static void main(String[] args) {
    		Scanner mScanner=new Scanner(System.in);
    		String input=mScanner.next();
    		int result=0;
    		while (input.length()>=2) {
    			   int len=input.length();
    			   for (int i = 0; i < len/2; i++) {
    				   if (input.charAt(i)!=input.charAt(len-1-i)) {
    					   break;
    				   }else if(i==len/2-1){
    					   result++;
    				   }
    			  }
    			   input=input.substring(1, len-1);
    		}
    		System.out.println(result);
    	}
      
    }

网易题目如下：

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。  
例如：  
A = “aba”，B = “b”。这里有4种把B插入A的办法：  
\* 在A的第一个字母之前: “baba” 不是回文  
\* 在第一个字母‘a’之后: “abba” 是回文  
\* 在字母‘b’之后: “abba” 是回文  
\* 在第二个字母’a’之后 “abab” 不是回文  
所以满足条件的答案为2

**输入描述：**

每组输入数据共两行。 
    第一行为字符串A 
    第二行为字符串B 
    字符串长度均小于100且只包含小写字母

**输出描述：**

输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数

**输入样例：**

aba
    b

**输出样例：**

import java.util.Scanner;
    
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner mScanner = new Scanner(System.in);
    		String str1 = mScanner.next();
    		String str2 = mScanner.next();
    		int count = 0;
    		int len = str1.length();
    		StringBuilder sBuilder=new StringBuilder();
    		for (int i = 0; i < len + 1; i++) {
    			sBuilder.delete(0, sBuilder.length());
    			sBuilder.append(str1.substring(0, i)).append(str2).append(str1.substring(i)) ;
    			if (checkHuiWen(sBuilder.toString())) {
    				count++;
    			}
    		}
    		System.out.println(count);
    	}
    
    	private static boolean checkHuiWen(String str) {
    		boolean flag = true;
    		int len = str.length();
    		for (int i = 0; i < len; i++) {
    			if (str.charAt(i) != str.charAt(len - 1 - i)) {
    				flag = false;
    				break;
    			}
    		}
    		return flag;
    	}
    
    }