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

 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 }