進制轉換 & 回文判斷進制轉換 & 回文判斷

進制轉換 & 回文判斷

最近刷的一道題，總結一下其中的知識點。

回文平方1

回文數是指數字從前往後讀和從後往前讀都相同的數字。

例如數字 12321 就是典型的回文數字。

現在給定你一個整數 B，請你判斷 1∼300 之間的所有整數中，有哪些整數的平方轉化為 B 進制後，其 B 進制表示是回文數字。

輸入格式

一個整數 B。

輸出格式

每行包含兩個在 B 進制下表示的數字。

第一個表示滿足平方值轉化為 B 進制後是回文數字那個數，第二個數表示第一個數的平方。

所有滿足條件的數字按從小到大順序依次輸出。

資料範圍

2 ≤ B ≤ 20,

對于大于 9 的數字，用 A 表示 10，用 B 表示 11，以此類推。

輸入樣例：	輸出樣例：
10	1 1 2 4 3 9 11 121 22 484 26 676 101 10201 111 12321 121 14641 202 40804 212 44944 264 69696

1. 進制轉換

(1) 十進制轉任意進制

十進制轉任何進制都可以使用**短除法**來轉換。

Tips: 對于大于 9 的數字，用 A 表示 10，用 B 表示 11，以此類推。

代碼：

//短除法的基本實作
public static String base(int num, int b) {
    StringBuilder str = new StringBuilder();
    do {
        str.insert(0, change(num % b)); 
        num /= b;
    } while (num > 0);
    return str.toString();
}
//将大于10的數字轉換成字母
public static char change(int n) {
    if (n < 10)
        return (char) (n + '0');
    else
        return (char) (n - 10 + 'A');
}
           

(2) 任意進制轉十進制

基本原理是将此數的每一位乘以對應的B的n次方。

如16進制下的 0x245 轉成10進制

( 245 ) 16 = 2 × 1 6 2 + 4 × 1 6 1 + 5 × 1 6 0 = ( 581 ) 10 (245)_{16} = 2\times16^2+4\times16^1+5\times16^0 = (581)_{10} (245)16​=2×162+4×161+5×160=(581)10​

2進制 0b101011 轉成10進制

( 101011 ) 2 = 1 × 2 5 + 0 × 2 4 + 1 × 2 3 + 0 × 2 2 + 1 × 2 1 + 1 × 2 0 = ( 43 ) 10 (101011)_2 = 1\times2^5+0\times2^4+1\times2^3+0\times2^2+1\times2^1+1\times2^0 = (43)_{10} (101011)2​=1×25+0×24+1×23+0×22+1×21+1×20=(43)10​

public static int base102(String str, int b) {
    char[] chs = str.toCharArray();
    int res = 0;
    for (int i = 0; i < chs.length; i++) {
        res += pow(b,i) * to10(chs[chs.length-1-i]); //直接使用原理
    }
    return res;
}
//n次方的計算
private static int pow(int num, int idx) {
    for (int i = 1 ; i < idx ; i++)
        num *= num;
    return idx == 0?1:num;
}
//将字母轉換為數字
public static int to10(char ch) {
    if (ch >= 'A')
        return ch - 'A' + 10;
    else
        return ch - '0';
}
           

秦九韶算法，簡單來說就是簡化多項式的一種運算

上述的 0x245轉換可以變成 ( ( ( 2 × 16 ) + 4 ) × 16 ) + 5 (((2\times16)+4)\times16)+5 (((2×16)+4)×16)+5

這樣不用重複計算常數指數部分

public static int base10(String str, int b) {
    char[] chs = str.toCharArray();
    int res = 0;
    for (int i = 0; i < chs.length; i++) 
        res = res * b + to10(chs[i]);//秦九韶算法，不用求指數
    return res;
}
//将字母轉換為數字
public static int to10(char ch) {
    if (ch >= 'A')
        return ch - 'A' + 10;
    else
        return ch - '0';
}
           

(3) 某一進制轉另一進制

待填坑

2. 回文判斷

以前我判斷回文時都是用棧，最近學習了雙指針算法，發現完全不需要那麼麻煩。。

(1) 棧實作

static Stack<Character> stack = new Stack<>(); //定義全局棧

//如果傳入int、long等數值類型，需String.valueOf(num)轉化為字元串
public static boolean isHuiWen(String str){
    char[] chs = str.toCharArray();
    int len = chs.length;
    int mid = len / 2;
    
    for (int i = mid; i > 0; i-- )
        stack.push(ch[len-i]);//後半部分入棧
    
    for (int i = 0; i < mid ; i++ )
        if (ch[i] != stack.pop())//出棧并與前半部分一一比對
            return false;
    
    return true;
}
           

(2) 雙指針實作

//如果傳入int、long等數值類型，需String.valueOf(num)轉化為字元串
public static boolean isHuiWen(String str) {
    char[] chs = str.toCharArray();
    int len = chs.length;
    
    //定義指針i、j，前者從0開始向後掃描，後者從末尾開始向前掃描，掃描到中心（len/2）為止
    for (int i = 0, j = len - 1; i < len/2 ; i++,j--) 
        if (chs[i] != chs[j]) //一一比對
            return false;
    return true;
}
           

對這兩種方式簡單測試了下，雙指針實作比棧實作要快數倍。

3.開頭題目的解

import java.util.Scanner;

public class Main {
    static int n;
    public static void main(String[] args) {
        n = new Scanner(System.in).nextInt();
        for (int i = 1 ; i <= 300 ; i++)
            if (isHW(base(i*i))){
                System.out.println(base(i) +" " + base(i*i));
    }
        
	//上述的10進制轉任意進制
    public static String base(int num) {
        StringBuilder str = new StringBuilder();
        do {
            str.insert(0, change(num % n));
            num /= n;
        } while (num > 0);
        return str.toString();
    }
    public static char change(int n) {
        if (n < 10)
            return (char) (n + '0');
        else
            return (char) (n - 10 + 'A');
    }
    //上述的回文判斷
    public static boolean isHW(String str) {
        char[] chs = str.toCharArray();
        int len = chs.length;
        for (int i = 0, j = len - 1; i < len/2 ; i++,j--)
            if (chs[i] != chs[j])
                return false;
        return true;
    }
}
           

1. 題目來源-Acwing-寒假每日一題-https://www.acwing.com/problem/content/1348/ ↩︎