首页 > 代码库 > 回文数 第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个回文数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。