[2014亚马逊amazon] 在线笔试题 大于非负整数N的第一个回文数 Symmetric Number解析

你猜 阅读:389 2020-10-19 15:34:54 评论:0

1.题目

  如标题,求大于整数N(N>=0)的第一个回文数的字符串表示形式。

  这个题目也是当时笔试第一次见到,花了一个小时才做出了。慢慢总结还是挺简单的。

2.分析

  分析如下:

  (1)一位数N(9除外)。

    第一个大于N回文数等于N+1,如大于3的第一个回文数是4。

   

  (2)奇数位(一位数除外)

    需要看“左边反转数字”是否大于"右边数字"

     1)如果小于等于,则“左边+中间字母”组成的数字+1,再对称就可以。

     2)如果大于,则左边数字直接对称到右边就可以啦。

    

  (3)偶数位

    需要看“左边反转数字”是否大于"右边数字"

     1)如果小于等于,则左边组成的数字+1,再对称就可以。

     2)如果大于,则左边数字直接对称到右边就可以啦。

    

  (4)特殊情况(其实就一种)

    1)N=9,大于N的下一个回文数是11,即N+2

    2)奇数情况(位数!=1)。

      N1=99900,右边数字小于“左边,翻转数字”,直接对称,所以大于N1的第一个回文数是99999。(满足上面的讨论规则)

      N2=99999,右边数组大于等于“左边,翻转数字”,使用上面的讨论规则结果为1000 001 ,不正确。结果应该是N2+2

    3)偶数情况。

      N1=9900,右边数字小于“左边翻转数字”,直接对称,所以大于N1的第一个回文数是9999。(满足上面的讨论规则)

      N2=9999,右边数组大于等于“左边翻转数字”,使用上面的讨论规则结果为100 001 ,不正确。结果应该是N2+2

  所以,可以将特殊情况归结为一种,当整数N满足正则表达式"9+"时,大于N的第一个回文数是N+2。(9,99,999,9999,.....)

3.生成代码+测试代码

 1 /** 
 2  * 生成函数: 
 3  *         firstBiggerPalindrome(String n) 
 4  *         isLeftReverseBiggerRight(String left, String right) 
 5  * 后期使用for循环校验N in [0,1000000)时的情况函数: 
 6  *         nextPalindromeUseFor(int num, boolean[] Palindrome) 
 7  *         isPalindrome(int num) 
 8  *  
 9  * 在main函数内进行算法生成 与 for循环暴力生成的校验 
10  * */ 
11  
12 public class Solution { 
13     static String firstBiggerPalindrome(String n) { // 生成大于整数N(字符串表示)的第一个回文整数 
14         n = String.valueOf(Integer.parseInt(n)); // 避免前导符"0",如n="009" 
15         if (n.matches("9+")) // 特殊情况直接处理 
16             return String.valueOf(Integer.parseInt(n) + 2); 
17  
18         int len = n.length(); 
19         if (len == 1) // 长度为1 
20             return String.valueOf(Integer.parseInt(n) + 1); 
21         StringBuilder left = new StringBuilder(); // 左边 
22         StringBuilder right = new StringBuilder(); // 右边 
23         StringBuilder res = new StringBuilder(); // 结果 
24         if ((len & 0x1) == 1) { // 奇数位 
25             left.append(n.substring(0, len >> 1)); 
26             right.append(n.substring((len >> 1) + 1)); 
27             if (isLeftReverseBiggerRight(left.toString(), right.toString())) { // 如果左边翻转数字大于右边,直接翻转 
28                 res.append(left); 
29                 res.append(n.charAt(len >> 1)); 
30                 res.append(left.reverse().toString()); 
31             } else { // 否则,“左边+中间”数字加1,再翻转 
32                 left.append(n.charAt(len >> 1)); 
33                 int num = Integer.parseInt(left.toString()) + 1; 
34                 left.setLength(0); 
35                 left.append(num); 
36  
37                 res.append(num); 
38                 res.append(left.deleteCharAt(left.length() - 1).reverse() 
39                         .toString()); 
40             } 
41         } else { // 偶数为 
42             left.append(n.substring(0, len >> 1)); 
43             right.append(n.substring(len >> 1)); 
44             if (!isLeftReverseBiggerRight(left.toString(), right.toString())) { 
45                 int num = Integer.parseInt(left.toString()) + 1; 
46                 left.setLength(0); 
47                 left.append(num); 
48             } 
49             res.append(left.toString()); 
50             res.append(left.reverse().toString()); 
51         } 
52         return res.toString(); 
53     } 
54  
55     static boolean isLeftReverseBiggerRight(String left, String right) { // 比较左边翻转后数字与右边数字的大小关系 
56         StringBuilder sb = new StringBuilder(left); 
57         if (sb.reverse().toString().compareTo(right) > 0) 
58             return true; 
59         return false; 
60     } 
61  
62     static String nextPalindromeUseFor(int num, boolean[] Palindrome) { // 求大于num的第一个回文数(最后的测试代码使用) 
63         for (int i = num + 1; i < Palindrome.length; i++) { 
64             if (Palindrome[i] == true) 
65                 return String.valueOf(i); 
66         } 
67         return null; 
68     } 
69  
70     static boolean isPalindrome(int num) { // 判断一个数字是不是回文数字(最后的测试代码使用) 
71         String str = String.valueOf(num); 
72         int i = 0; 
73         int j = str.length() - 1; 
74         while (i < j) { 
75             if (str.charAt(i) != str.charAt(j)) 
76                 return false; 
77             i++; 
78             j--; 
79         } 
80         return true; 
81     } 
82  
83     public static void main(String[] args) throws IOException { 
84         int n = 1000000; // 只测试[0,1000000)以内的结果 
85         boolean[] Palindrome = new boolean[n];    //默认为false 
86         for (int i = 0; i < n; i++) { 
87             if (isPalindrome(i)) 
88                 Palindrome[i] = true;    //如果是回文数字,标记为true。编译下一步校验,大于N的第一个回文数字 
89         } 
90  
91         for (int i = 0; i < n; i++) { 
92             String val = firstBiggerPalindrome(String.valueOf(i));    //程序生成 
93             if (Integer.parseInt(val) < n) {    //如果在[0,1000000)内,进行校验 
94                 if (!val.equals(nextPalindromeUseFor(i, Palindrome))) 
95                     System.out.println("BAD\t" + i); 
96             } 
97         } 
98     } 
99 }
View Code

通过代码中的验证程序,可以验证算法的正确性,呵呵,nice!!!

 

Java编程小细节:

  这个题目是字符串处理的,所以用了StringBuilder的reverse();注意一下

 1 import java.io.*; 
 2  
 3 public class Solution { 
 4     public static void main(String[] args) throws IOException { 
 5         StringBuilder sb = new StringBuilder(); 
 6         sb.append("liuliuliu"); 
 7         System.out.println(sb.toString()); 
 8         sb.reverse();    //不需要返回值,也能翻转,记住啊!!! 
 9         System.out.println(sb.toString()); 
10     } 
11 }

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
KIKK导航

KIKK导航

关注我们