首页 > 代码库 > 回文数 第N个回文数

回文数 第N个回文数

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

 

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

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

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

    1位回文数: 9个

    2位回文数: 9个

    3位回文数: 90个

    4位回文数: 90个

    5位回文数: 900个

    6位回文数: 900个

    …

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

[123321]来看。两半的变化一样的,那我们只算其中一半就行了。首位不能是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;    }

 

  

 

回文数 第N个回文数