回文数 第N个回文数

时间:2021-02-13 23:43:18

判断回文数还是不难,如果能转为字符串就更简单了。

如果是求第N个回文数呢。

12321是一个回文数,这里先考虑一半的情况。

回文数的个数其实是有规律的。如:

1位回文数: 9个

2位回文数: 9个

3位回文数: 90个

4位回文数: 90个

5位回文数: 900个

6位回文数: 900个

我们看到9、90、900,是不是很有规律,那是什么原因?很简单,我们把回文数拆开两半

[]来看。两半的变化一样的,那我们只算其中一半就行了。首位不能是0,所以左半最小为

100,最大为999,共有999-100=900个,如此类推。

所以我们可以基于以下原则:

1、 回文数的数位每增长2,回文数的个数为原来的10倍。如从个位回文数到百位回文数,个数

从9个变为90个。

2、 个位回文数的个数是9,1、2、3、…、9。

static long find(int index) {
int count = 0;
int number = 9; //记录数位上的回文数,如个位回文数为9
int w = 0; //记录数位 long half; //保存回文数的左半边的结果
long h = 1; //回文数的左半边的起始基数
long res; //结果 while(true) {
if(w > 0 && w%2 == 0) { //每进两个数位,回文数乘以10
number *= 10;
}
w++; //数位加一
if(count + number > index) //回文数大于查找的回数,跳出
break; count += number; //回文数加上当前数位上的回文数
} index -= count; //在当前数位上的位置。如w=5,index=50,则万位上的第50个回文数是我们所求 for(int i = 0; i < (w-1) / 2; i++) { //求回文数的左半边的基数,如回文数在万位上,则为100
h *= 10;
} half = h + index; //回文数的左半边,如100 + 50 = 150 res = half; if(w%2 != 0) //如果为奇数,则中间那个数不必算入右半边了!
half /=10; while(half != 0) { //拼接回文数
res = res *10 + half % 10;
half /= 10;
} return res;
}