蓝桥杯 基础练习 十六进制转八进制

这道坑爹题真是让人绞尽脑汁，实际上我觉得大家应该也能感受到，很多看似不难的算法题实际上难度在于——如何处理大数的情况，这道题也是一样。

这题是一道非常好的题，因为我不熟悉Java，对于各种类都不太清楚，也没什么感觉，但这题让我了解到了很多类/方法的差别，很具有学习价值。

给定n个十六进制正整数，输出它们对应的八进制数。
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。

很明显的进制转换，刚开始我们想到的肯定是：既然是Java，大概会有进制转换的函数——一查，当然是有的：

Integer.toOctalString(Integer.valueOf(x, 16))

这个方法的连用也就是将16转成转成10进制再转成八进制。

问题如果那么简单就能解决，它就不叫坑了。

我们会发现，无论是Integer还是Long，他总是存在范围的局限性的，一超过范围就会悲剧，没有办法，自己写吧。

一开始想到的，当然是我们的基本转换方法，也就是转换原理：十六进制转成二进制，二进制转成八进制。

当然，实际操作上，当然不会再用他给的函数了，因为没有办法从根源上消灭这个问题嘛。

换言之，我们想到的是，怎么样通过十六进制转二进制：是把一个数分为四位二进制，不足的部分补0，二进制怎么转成八进制：是由二进制每三个转换为八进制。

当然我们还是想到了，切割成一块块之后能不能满足范围，然后字符串照样拼接，我们就用它的自带函数呢？

String[] Hex = new String[] {"0000", "0001", "0010", "0011",
                      "0100", "0101", "0110", "0111",
                      "1000", "1001", "1010", "1011",
                      "1100", "1101", "1110", "1111"};

于是我们使用了String数组，转换为十进制（自带函数），然后找到对应的二进制，拼接，再转换为八进制。

遗憾的是，效率还是太慢了（如果你看到坑爹的测试数据，一定会发现太坑了）。

在此之上，想到了天下武功，哈希表很快——徒手构建哈希表吧：

HashMap<String, String> Hex = new HashMap<String, String>();
Hex.put("0", "0000");
Hex.put("1", "0001");
Hex.put("2", "0010");
Hex.put("3", "0011");
Hex.put("4", "0100");
Hex.put("5", "0101");
Hex.put("6", "0110");
Hex.put("7", "0111");
Hex.put("8", "1000");
Hex.put("9", "1001");
Hex.put("A", "1010");
Hex.put("B", "1011");
Hex.put("C", "1100");
Hex.put("D", "1101");
Hex.put("E", "1110");
Hex.put("F", "1111");

HashMap<String, String> Oct = new HashMap<String, String>();
Oct.put("000", "0");
Oct.put("001", "1");
Oct.put("010", "2");
Oct.put("011", "3");
Oct.put("100", "4");
Oct.put("101", "5");
Oct.put("110", "6");
Oct.put("111", "7");

就这样，性能总算提升了一些，用哈希表去找结果值。

接下来的问题在于切割和拼接，在这题中，很好地向我们展现了String和StringBuffer类的差别。

对于频繁的拼接，String类显得非常无力，这是由于String其实是不变的，它相当于重新拿了一块内存出来，而StringBuffer才是真正意义的拼接。

在切割上，我们使用了substring方法，在Java中还是第一次使用，所以查了一下参数规则：

substring的用法是begin（能取到）, end（取不到）

这个函数的使用没有任何疑问了，接下来是拼接，拼接的话我们有很多可以用，但是这里我们使用了append和insert，一个直接在最后插入，一个选择位置，我们把它作为需要在最前面插入的方法（前导0）。

但是在拼接时，由于我们截取是从后开始，也就是最后一位先出来，拼接时需要一点点往前插入，这对于性能是个考验，我们从中也可以看出来，append和insert的性能完全不同。

好了，还是想了个办法，我不能插入，我可以直接反转字符串输出呀。

先用append，再用reverse，性能特别高！

最后，还有一点，是发现了输入时好像也有点满，似乎听说使用缓冲区输入会稍微快一点

BufferedReader in = new BufferedReader(
                new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

这个类在java.io.*中，使用前需要引入。

终于得解了，不得不说尝试了好多次。

完整代码（包括了已经让我崩溃的注释们）：

import java.util.*;
import java.io.*;

/**
 * 历经千难万险！终于做出来了！
 * 注释的除了上古遗迹的代码外还有为什么使用该方法的理由
 * 这道题对于理解Java不同方法以及其性能差异非常有帮助，虽然花了好久才做出来
 */
public class HexToOct {
    public static void main(String[] args) throws IOException{
        // Scanner in = new Scanner(System.in);
        // 因为用Scanner一次性读数据要爆炸 所以我们用BufferReader缓冲一下，需要引入java.io.*
        BufferedReader in = new BufferedReader(
                new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        String a[] = new String[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.readLine();
        }
        // 本来用的String数组，然后用内置方法转换为十进制，但是效率太低，手写HashMap键值对匹配
        HashMap<String, String> Hex = new HashMap<String, String>();
        Hex.put("0", "0000");
        Hex.put("1", "0001");
        Hex.put("2", "0010");
        Hex.put("3", "0011");
        Hex.put("4", "0100");
        Hex.put("5", "0101");
        Hex.put("6", "0110");
        Hex.put("7", "0111");
        Hex.put("8", "1000");
        Hex.put("9", "1001");
        Hex.put("A", "1010");
        Hex.put("B", "1011");
        Hex.put("C", "1100");
        Hex.put("D", "1101");
        Hex.put("E", "1110");
        Hex.put("F", "1111");
        // String[] Hex = new String[] {"0000", "0001", "0010", "0011",
        //                       "0100", "0101", "0110", "0111",
        //                       "1000", "1001", "1010", "1011",
        //                       "1100", "1101", "1110", "1111"};
        HashMap<String, String> Oct = new HashMap<String, String>();
        Oct.put("000", "0");
        Oct.put("001", "1");
        Oct.put("010", "2");
        Oct.put("011", "3");
        Oct.put("100", "4");
        Oct.put("101", "5");
        Oct.put("110", "6");
        Oct.put("111", "7");

        // int n = in.nextInt();
        String x;
        // String temp;
        // String temp2;
        // String oct;
        // int n = in.nextInt();
        int length = 0;
        // StringBuffer temp2 = new StringBuffer();

        // in.nextLine();

        for (int i = 0; i < n; i++) {
            // x = in.nextLine();
            // 本来String的字符串拼接，性能不够，StringBuffer的性能提高了许多
            StringBuffer temp = new StringBuffer();
            StringBuffer oct = new StringBuffer();
            // String xArr[] = a[i].split("");
            // System.out.println(Integer.toOctalString(Integer.valueOf(x, 16)));
            for (int j = 0; j < a[i].length(); j++) {
                temp.append( Hex.get(a[i].substring(j, j+1)) );
            }
            length = temp.length();
            if (length % 3 == 1) {
                // insert用于在最前面插入不足的前导零
                temp.insert(0, "00");
                length += 2;
            } else if (length % 3 == 2) {
                temp.insert(0, "0");
                length ++;
            }
            // System.out.println(length);
            for (int j = 0; j < length; j+=3) {
                int begin = length - j - 3;
                // System.out.println("长度: " + length + "位置:" + begin + " - " + (length - j - 1));
                // substring的用法是begin（能取到）, end（取不到）
                String temp2 = temp.substring(begin, length - j);
                // temp2.replace(0, 2, temp.substring(begin, length - j) );
                // System.out.println(temp2);

                if (!temp2.equals("") && ( begin != 0 || !temp2.equals("000") ))
                    // 本来用insert 性能和append相比差了太多，所以之后用reverse方法倒过来
                    oct.append(Oct.get(temp2));
            }
            System.out.println(oct.reverse().toString());
        }
    }
}