題目要求

P1015題目鏈接

分析

開始的時候寫了這么一個代碼，應該是比較基礎的，是十進制的。

private static void low() {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();String str = Integer.toString(num);int i;for (i = 0 ; i < 30; i++) {StringBuilder reverse = new StringBuilder(str).reverse();//是回文數if (str.equals(reverse.toString())) {break;}//不是回文數，就增加數值num += Integer.parseInt(reverse.toString());str = Integer.toString(num);}if (i == 30) {System.out.println("Impossible!");} else {System.out.println("STEP=" + i);}scanner.close();}

但本題是N進制的，數據要求是 2 <= N <= 10 || N == 16 。

要將十六進制和N進制區分開來，分情況討論。

十六進制的話，在我們使用char的時候，由于大寫字母與阿拉伯數字在ASCII里是不連續的，所以我覺得可以建立一個Integer與Character之間的雙射關系。
雙射關系的“一一對應”不是很容易實現，那就可以建立兩個HashMap，一個從Integer到Character，另一個從Character到Integer，利用HashMap的高效性來快速的存取。

讀題的話，字符串反轉是要做的。
Java不像C，貌似沒有直接的reverse()，但可以使用StringBuilder實現：

/*** 字符串反轉* @param string 待翻轉字符串* @return 翻轉后的字符串*/private static String reverse(String string) {return new StringBuilder(string).reverse().toString();}

還要做回文判定，既然有了reverse，那就直接利用String的equals()即可。二者結合就可以判定是否是回文數啦：

/*** 判斷是否為回文數* @param num 待判數值* @return 是否為回文數*/private static boolean isPalindrome(String num) {if (num.equals(reverse(num))) {return true;} else {return false;}}

核心是如何操作至多100位的加法呢？（雖然洛谷里本題評測數據沒那么變態）
只能是純粹的利用串和字符進行加法，這也是核心的難點。

下面是十六進制的加法：

/*** 十六進制加法* @param num1 加數1* @param num2 加數2（位數與加數1相同）* @return 十六進制和*/private static String hexAdd(String num1, String num2) {//獲取char[]char[] chars1 = num1.toCharArray();char[] chars2 = num2.toCharArray();//長度int length = chars1.length;//結果的char[]char[] result = new char[length+1];for (int i = length-1; i >= 0; i--) {//實際上是intint temp = charMap.get(chars1[i]) + charMap.get(chars2[i]) + result[i+1];if (temp >= 16) {//本位溢出，進位result[i+1] = intMap.get(temp-16);result[i]++;} else {result[i+1] = intMap.get(temp);}}//最終溢出if (result[0] == 0) {return new String(result).substring(1);}result[0] += 48;return new String(result);}

因為是有A/B/C/D/E/F，但上面也說了原因，這是不好操作的，就利用Map的映射來獲取對應的“真值”。

原本想的是先判進位，但是后來發現不行，下面打個比方：
如果先判高位相加時候溢出，是不能滿足所有可能的，很多測試數據用上去都會WA掉。
十進制的599+499，明顯是會溢出進位的，但5+4不會達到10，如果這就認為不能滿足進位，顯然就錯了。

所以我會開一個長一位的數組，當高位是0的時候（不進位）就利用字符串的取得子串來消去第一位。

進位一定要處理好啊！！！

下面是2~10進制的加法：

/*** 2-10進制的加法* @param num1 加數1* @param num2 加數2（位數與加數1相同）* @param format 兩個數所屬進制* @return N進制和（2 <= N <= 10）*/private static String normallyAdd(String num1, String num2, int format) {//獲取char[]char[] chars1 = num1.toCharArray();char[] chars2 = num2.toCharArray();//長度int length = chars1.length;//結果的char[]char[] result = new char[length+1];for (int i = length-1; i >= 0; i--) {//實際上是charint temp = chars1[i] + chars2[i] + result[i+1];if (temp >= 96 + format) {//本位溢出，進位result[i+1] = (char)(temp - format - 48);result[i]++;} else {result[i+1] = (char)(temp - 48);}}//最終溢出if (result[0] == 0) {return new String(result).substring(1);}result[0] += 48;return new String(result);}

這里就可以不用Map啦，其實單純的操作char就可以啦！！

很多都是類似的，可以看看上面的。

評測數據集Share

我遇到了一些WA和RE問題。
一共有4份測試數據集，我這里有第一個、第二個、第四個。

數據1
in
2
10011
out
STEP=4

數據2
in
16
AC27
out
STEP=6

數據4
in
2
101111
out
Impossible!

AC代碼（Java語言描述）

import java.util.HashMap; import java.util.Map; import java.util.Scanner;public class Main {private static Map<Character, Integer> charMap;private static Map<Integer, Character> intMap;static {charMap = new HashMap<>();charMap.put('0', 0);charMap.put('1', 1);charMap.put('2', 2);charMap.put('3', 3);charMap.put('4', 4);charMap.put('5', 5);charMap.put('6', 6);charMap.put('7', 7);charMap.put('8', 8);charMap.put('9', 9);charMap.put('A', 10);charMap.put('B', 11);charMap.put('C', 12);charMap.put('D', 13);charMap.put('E', 14);charMap.put('F', 15);intMap = new HashMap<>();intMap.put(0, '0');intMap.put(1, '1');intMap.put(2, '2');intMap.put(3, '3');intMap.put(4, '4');intMap.put(5, '5');intMap.put(6, '6');intMap.put(7, '7');intMap.put(8, '8');intMap.put(9, '9');intMap.put(10, 'A');intMap.put(11, 'B');intMap.put(12, 'C');intMap.put(13, 'D');intMap.put(14, 'E');intMap.put(15, 'F');}/*** 字符串反轉* @param string 待翻轉字符串* @return 翻轉后的字符串*/private static String reverse(String string) {return new StringBuilder(string).reverse().toString();}/*** 十六進制加法* @param num1 加數1* @param num2 加數2（位數與加數1相同）* @return 十六進制和*/private static String hexAdd(String num1, String num2) {//獲取char[]char[] chars1 = num1.toCharArray();char[] chars2 = num2.toCharArray();//長度int length = chars1.length;//結果的char[]char[] result = new char[length+1];for (int i = length-1; i >= 0; i--) {//實際上是intint temp = charMap.get(chars1[i]) + charMap.get(chars2[i]) + result[i+1];if (temp >= 16) {//本位溢出，進位result[i+1] = intMap.get(temp-16);result[i]++;} else {result[i+1] = intMap.get(temp);}}//最終溢出if (result[0] == 0) {return new String(result).substring(1);}result[0] += 48;return new String(result);}/*** 2-10進制的加法* @param num1 加數1* @param num2 加數2（位數與加數1相同）* @param format 兩個數所屬進制* @return N進制和（2 <= N <= 10）*/private static String normallyAdd(String num1, String num2, int format) {//獲取char[]char[] chars1 = num1.toCharArray();char[] chars2 = num2.toCharArray();//長度int length = chars1.length;//結果的char[]char[] result = new char[length+1];for (int i = length-1; i >= 0; i--) {//實際上是charint temp = chars1[i] + chars2[i] + result[i+1];if (temp >= 96 + format) {//本位溢出，進位result[i+1] = (char)(temp - format - 48);result[i]++;} else {result[i+1] = (char)(temp - 48);}}//最終溢出if (result[0] == 0) {return new String(result).substring(1);}result[0] += 48;return new String(result);}/*** 判斷是否為回文數* @param num 待判數值* @return 是否為回文數*/private static boolean isPalindrome(String num) {if (num.equals(reverse(num))) {return true;} else {return false;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//進制（2-10、16）int format = Integer.parseInt(scanner.nextLine());String num = scanner.nextLine();int counter = 0;if (format == 16) {while (!isPalindrome(num) && counter <= 30) {num = hexAdd(num, reverse(num));counter++;}} else {while (!isPalindrome(num) && counter <= 30) {num = normallyAdd(num, reverse(num), format);counter++;}}if (counter > 30) {System.out.println("Impossible!");} else {System.out.println("STEP=" + counter);}scanner.close();}}

感悟

這個題的代碼基本寫了半天，充滿了各種失敗，是很大的挑戰。

但這次以后，我想我對利用串和字符處理進制有了很好的認識，這部分內容對我是重要的，以后希望能做得更好。

希望能對大家有所幫助！！
加油！！奧利給！！（晚安啦）

總結

以上是生活随笔為你收集整理的N进制正反累加判回文数（洛谷P1015题题解，Java语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。