Go语言视频零基础入门到精通

javalearner

问题：     将所有回文数从小到大排列，求第N个回文数。     一个正数如果顺着和反过来都是一样的（如13431，反过来也是13431），就称为回文数。约束：     回文数不能以0开头。     最小回文数是1。 思路：     许多朋友（包括我自己）一开始就思考使用循环：从1开始，判断该数是否是回文数，然后用一 个计数器记下回文数，一直到计数器得到N，返回第N个回文数。比较常用的是以下这种方法来判断是 否回文数：  
   
     
    static
     
    boolean
     isPN(
    int
     num) {
     
    int
     o
    =
     num;
     
    int
     tmp
    =
     
    0
    ;
     
    //
    使用循环把数字顺序反转
   

        
    while
    (num
    !=
     
    0
    ) {
         tmp
    *=
     
    10
    ;
         tmp
    +=
     num
    %
     
    10
    ;
         num
    /=
     
    10
    ;
     }
     
    //
    如果原始数与反转后的数相等则返回true
   

        
    if
    (tmp
    ==
     o)
         
    return
     
    true
    ;
     
    return
     
    false
    ;
}

         这种思路的确可得到正确结果，但随着用来测试的N的增大，效率的问题就浮现了。因为是一重 循环，效率是O（n）。所以当N非常大时，所花的时间还是十分大的。    另一种思路：     回文数的个数其实是有规律的。如：     1位回文数： 9个     2位回文数： 9个     3位回文数： 90个     4位回文数： 90个     5位回文数： 900个     6位回文数： 900个     …     我们看到9、90、900，是不是很有规律，那是什么原因？很简单，我们把回文数拆开两半 [123321]来看。两半的变化一样的，那我们只算其中一半就行了。首位不能是0，所以左半最小为 100，最大为999，共有999-100+1=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;
     }
    全部代码：

1. public class PalindromicNumber {
   
2.     public static void main(String[] args) {
   
3.         int input = Integer.parseInt(args[0]);
   
4.         long res = find(input);
   
5.         System.out.println("res:" + res);
   
6.         
   
7.     }
   
8.    
   
9.     static long find(int index) {
   
10.         int count = 0;            
    
11.         int number = 9;   //记录数位上的回文数，如个位回文数为9
    
12.         int w = 0;     //记录数位
    
13.         
    
14.         long half;    //保存回文数的左半边的结果
    
15.         long h = 1;    //回文数的左半边的起始基数
    
16.         long res;       //结果
    
17.         
    
18.         while(true) {
    
19.             if(w > 0 && w%2 == 0) {   //每进两个数位，回文数乘以10
    
20.                 number *= 10;
    
21.             }
    
22.             w++;      //数位加一
    
23.             if(count + number > index)    //回文数大于查找的回数,跳出
    
24.                 break;
    
25.             count += number;       //回文数加上当前数位上的回文数
    
26.         }
    
27.         
    
28.         index -= count;      //在当前数位上的位置。如w=5,index=50,则万位上的第50个回文数是我们所求
    
29.         for(int i = 0; i < (w-1) / 2; i++) {  //求回文数的左半边的基数，如回文数在万位上，则为100
    
30.             h *= 10;
    
31.         }
    
32.         
    
33.         half = h + index;      //回文数的左半边，如100 + 50 = 150
    
34.         res = half;
    
35.         
    
36.         if(w%2 != 0)      //如果为奇数，则中间那个数不必算入右半边了！
    
37.             half /=10;
    
38.             
    
39.         while(half != 0) {   //拼接回文数
    
40.             res = res *10 + half % 10;
    
41.             half /= 10;
    
42.         }
    
43.         
    
44.         return res;
    
45.     }
    
46. }
    

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://www.java3z.com/cwbwebhome/dir1/dir5/PalindromicNumber.zi