进制转换 & 回文判断进制转换 & 回文判断

进制转换 & 回文判断

最近刷的一道题，总结一下其中的知识点。

回文平方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/ ↩︎