蓝桥杯 算法提高 回文串 Java实现

时间限制：1.0s 内存限制：256.0MB

　　一个正整数N被称为回文数，当且仅当N在十进制下，正着读和反着读是一样的。
　　如12321是回文的，而12320不是。
　　现在让你求出第K小的回文数。(第0小的是 1，第1小的是 2)

　　输入一个数K。

　　一个数字N，为第K小的回文数。

19

111

　　对于30% 的数据 K≤10000；
　　对于100% 的数据 K≤。

这道题要我们找出第k小的回文数，同时k的数据范围较大，一个一个去找显然不现实，这样就需要去找规律，我找到的规律如下

可以看到，基数为9，每增加两位，就要往上乘10，那么我就让k去减两次9，再去减两次90...以此类推，直到k<0，然后让k加上最后一次减去的数，就找到了第k小的数是回文数为n位时的第i小的数，这样就好赋值了。

​
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//题目序号从0开始，这里进行+1，方便理解
		Long n=scanner.nextLong()+1;
		//后面程序会计算回文数的位数
		int weishu=0;
		//用来当10的次方数
		Long m=1L;
		//计算第n个数有几位
		while (n>0){
			for (Long i = 0L; i < 2; i++) {
				if (n<0){
					break;
				}
				n-=9*m;
				weishu++;
			}
			m*=10;
		}
		//算出这第n个数是该位的第几个数，例：第19个数（n=19输入为18）算出来weishu=2，则它是回文数是2位数时的第1个
		n+=9*m/10;
		//创建一个装回文数的数组
		Long[] huiwen=new Long[weishu];
		//转成字符方便取各位上的数
		String s= String.valueOf(n);
		//回文数长度，不过好像不要也行(○´･д･)ﾉ
		Long len= (long) weishu;
		if (len%2!=0){
			len=len+1;
		}
		//循环长度的一半，从数组两边往中间填值
		for (int i = 0; i < len/2; i++) {
			//判断是否除了最高位其他都是0
			if (n%(m/10)!=0&&i==0){
				//其他位有数字，那么回文数最高位与最低位则是为n的最高位加1
				huiwen[0]=huiwen[weishu-1]=Long.parseLong(String.valueOf(s.charAt(i)))+1;
				continue;
			}
			//判断是否到最后一位
			if (i==(len/2)-1){
				//如果n最后一位即个位数是0，那么该回文数最中间的数是9，同时它的前一位与后一位要减1
				if (Long.parseLong(String.valueOf(s.charAt(i)))==0){
					huiwen[i-1]=huiwen[weishu-i]=Long.parseLong(String.valueOf(s.charAt(i-1)))-1;
					huiwen[i]=huiwen[weishu-i-1]=9L;
				}else {
					//如果是1位或2位数就不用减1
					if (weishu==1||weishu==2){
						huiwen[i]=huiwen[weishu-i-1]=Long.parseLong(String.valueOf(s.charAt(i)));
					}else {
						huiwen[i]=huiwen[weishu-i-1]=Long.parseLong(String.valueOf(s.charAt(i)))-1;
					}
				}
			}else {
				//除了最高位与中间位数有不同，中间的数就是n对应的数
				huiwen[i]=huiwen[weishu-i-1]=Long.parseLong(String.valueOf(s.charAt(i)));
			}

		}
		for (Long i : huiwen) {
			System.out.print(i);
		}
	}
}

​