藍橋杯——十六進制轉八進制

• 0.前言
• 1.解題過程
• • 1.1原題
  • • 1.1.1問題描述
    • 1.1.2輸入格式
    • 1.1.3輸出格式
  • 1.2代碼
  • • 1.2.1正常做法
    • 1.2.2非正常做法（我自己的方法）
    • • 1.2.2.1方案概要
      • 1.2.2.2細節問題
      • 1.2.2.3代碼
      • 1.2.2.4說明
• 2.總結

0.前言

這道題乍一看不難，無非就是調用

Long.valueOf(n,16);

和

Integer.toString(n, 8)

，先轉成十進制再轉成八進制。但仔細看條件會發現數值非常大，這種方法是不行的。

1.解題過程

1.1原題

1.1.1問題描述

給定n個十六進制正整數，輸出它們對應的八進制數。

1.1.2輸入格式

輸入的第一行為一個正整數n （1<=n<=10）。

　　接下來n行，每行一個由09、大寫字母AF組成的字元串，表示要轉換的十六進制正整數，每個十六進制數長度不超過100000。

1.1.3輸出格式

輸出n行，每行為輸入對應的八進制正整數。

說明：輸入的十六進制數不會有前導0，比如012A，輸出的八進制數也不能有前導0。

1.2代碼

1.2.1正常做法

思路就是尋找一個能表示很大數值範圍的類來表示，

BigInteger

正好符合

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] agrs) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		String[] arr=new String[n];
		String[] brr=new String[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=sc.next();
			//調用自帶的BigInteger()類表示，需要熟練掌握Java的常用API
			brr[i]=new BigInteger(arr[i],16).toString(8);
		}
		for (int i = 0; i < brr.length; i++) {
			System.out.println(brr[i]);
		}
		sc.close();
	}
}
           

1.2.2非正常做法（我自己的方法）

最開始我的想法也是找一個能表示的類，但最後沒找到，而且看了那麼長的字元串之後，感覺就不是讓我們直接用，可能是找别的方法。

我的思路是這樣，在上課的時候，我們經常把16進制轉化為2進制，隻需要按位展開，而把2進制轉化為16進制隻需要每四位轉化為16進制拼接即可，那麼我就可以把這麼長的數字轉化為字元串，然後把字元串轉化為2進制，再把2進制的字元串每三位為一組轉化為8進制的字元串。

1.2.2.1方案概要

确定了思路之後，我們需要考慮幾個問題，第一個就是映射的問題，把16進制映射為四位的2進制數字，可以考慮用一個

HashMap

存儲，鍵為十六進制的0-F，值為二進制的0000-1111。把2進制映射為8進制也是一樣的思路，建立一個

HashMap

，鍵為二進制的000-111，值為八進制的0-7。遇到key時，直接替換為對應的value。

1.2.2.2細節問題

确定方案之後，還有幾個問題需要考慮，第一個就是前導0的問題，如果十六進制下第一位是1，轉化為二進制是0001，轉化為八進制是001，這樣的話，前面兩位0不應該存在。需要考慮去除前面多餘的0，第二個是，如果二進制的字元串總共有兩位，比如11，那麼按照建立的

HashMap

來看就找不到映射，需要考慮這種情況。

1.2.2.3代碼

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] agrs) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //存儲輸入的十六進制字元串
        String[] arrStrings = new String[n];
        //周遊指派
        for (int i = 0; i < n; i++) {
            arrStrings[i] = sc.next();
        }
        //十六進制轉二進制的映射表
        Map<String, String> x2bMap = new HashMap<>(16);
        //二進制轉八進制的映射表
        Map<String, String> b2oMap = new HashMap<>(8);
        //二進制字元串，StringBuilder做拼接的時候速度比較快
        StringBuilder binaryNumBuilder = new StringBuilder();
        //最終的八進制結果字元串
        StringBuilder resultBuilder = new StringBuilder();
        //鍵
        String key;
        //值
        String value;
        //局部結果的字元串
        String partString;
        //十六進制轉二進制映射表指派
        for (int i = 0; i < 16; i++) {
            key = String.format("%x", i).toUpperCase();
            value = String.format("%04d", Integer.parseInt(Integer.toBinaryString(i)));
            x2bMap.put(key, value);
        }
        //二進制轉八進制映射表指派
        for (int i = 0; i < 8; i++) {
            key = String.format("%03d", Integer.parseInt(Integer.toBinaryString(i)));
            value = String.valueOf(i);
            b2oMap.put(key, value);
        }
        for (String string : arrStrings) {
            //轉化為二進制字元串
            for (int i = 0; i < string.length(); i++) {
                key = String.valueOf(string.charAt(i));
                value = x2bMap.getOrDefault(key, "-1");
                binaryNumBuilder.append(value);
            }
            //考慮如果前面幾位為0時候，去除0
            if (binaryNumBuilder.charAt(0)=='0'){
                for (int i = 1; i < 4; i++) {
                    if (binaryNumBuilder.charAt(i) == '1') {
                        binaryNumBuilder = new StringBuilder(binaryNumBuilder.substring(i));
                        break;
                    }
                }
            }
            //二進制轉八進制，從後往前，每次-3
            for (int i = binaryNumBuilder.length(); i > 0; i -= 3) {
           		//如果最後字元串長度小于3，需要單獨處理
                if (i < 3) {
                    partString = binaryNumBuilder.substring(0, i);
                    partString = String.format("%o", Integer.valueOf(partString, 2));
                } else {
                    partString = binaryNumBuilder.substring(i - 3, i);
                    partString = b2oMap.get(partString);
                }
                resultBuilder.append(partString);
            }
            //此時拼接的字元串是正确結果的倒置，需要倒置後輸出
            System.out.println(resultBuilder.reverse().toString());
            //清空，重新指派
            binaryNumBuilder = new StringBuilder();
            resultBuilder = new StringBuilder();
        }
        sc.close();
    }
}
           

1.2.2.4說明

代碼如上，關鍵地方都有相應的注釋說明，這個方法相對于正常做法複雜了不少，但很鍛煉思維。這種模拟計算機進行計算的題目有很多，雖然一個兩個可以使用正常做法，但不絕對。掌握這種思想，對之後的練習也有好處。這種方法的時間複雜度和空間複雜度相對于正常做法要小不少，也算是一個成就吧。對比如下。

• 非正常做法：

  

• 正常做法：

  

2.總結

這道題，我做了很久，後來自己查了一下，發現還有那麼簡單的正常做法，後來我想明白了基礎練習的題目，大多都可以直接做，不需要考慮那麼複雜。但考慮複雜，對自己代碼能力和思維的嚴謹性有很大的提高。