蓝桥杯 基础练习 十六进制转八进制
这道坑爹题真是让人绞尽脑汁，实际上我觉得大家应该也能感受到，很多看似不难的算法题实际上难度在于——如何处理大数的情况，这道题也是一样。
这题是一道非常好的题，因为我不熟悉Java，对于各种类都不太清楚，也没什么感觉，但这题让我了解到了很多类/方法的差别，很具有学习价值。
给定n个十六进制正整数，输出它们对应的八进制数。 输入的第一行为一个正整数n （1<=n<=10）。 接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。 输入的十六进制数不会有前导0，比如012A。 输出的八进制数也不能有前导0。
很明显的进制转换，刚开始我们想到的肯定是：既然是Java，大概会有进制转换的函数——一查，当然是有的：
1Integer.toOctalString(Integer.valueOf(x, 16))
2
这个方法的连用也就是将16转成转成10进制再转成八进制。
问题如果那么简单就能解决，它就不叫坑了。
我们会发现，无论是Integer还是Long，他总是存在范围的局限性的，一超过范围就会悲剧，没有办法，自己写吧。
一开始想到的，当然是我们的基本转换方法，也就是转换原理：十六进制转成二进制，二进制转成八进制。
当然，实际操作上，当然不会再用他给的函数了，因为没有办法从根源上消灭这个问题嘛。
换言之，我们想到的是，怎么样通过十六进制转二进制：是把一个数分为四位二进制，不足的部分补0，二进制怎么转成八进制：是由二进制每三个转换为八进制。
当然我们还是想到了，切割成一块块之后能不能满足范围，然后字符串照样拼接，我们就用它的自带函数呢？
1String[] Hex = new String[] {"0000", "0001", "0010", "0011",
2 "0100", "0101", "0110", "0111",
3 "1000", "1001", "1010", "1011",
4 "1100", "1101", "1110", "1111"};
5
于是我们使用了String数组，转换为十进制（自带函数），然后找到对应的二进制，拼接，再转换为八进制。
遗憾的是，效率还是太慢了（如果你看到坑爹的测试数据，一定会发现太坑了）。
在此之上，想到了天下武功，哈希表很快——徒手构建哈希表吧：
1HashMap<String, String> Hex = new HashMap<String, String>();
2Hex.put("0", "0000");
3Hex.put("1", "0001");
4Hex.put("2", "0010");
5Hex.put("3", "0011");
6Hex.put("4", "0100");
7Hex.put("5", "0101");
8Hex.put("6", "0110");
9Hex.put("7", "0111");
10Hex.put("8", "1000");
11Hex.put("9", "1001");
12Hex.put("A", "1010");
13Hex.put("B", "1011");
14Hex.put("C", "1100");
15Hex.put("D", "1101");
16Hex.put("E", "1110");
17Hex.put("F", "1111");
18
19HashMap<String, String> Oct = new HashMap<String, String>();
20Oct.put("000", "0");
21Oct.put("001", "1");
22Oct.put("010", "2");
23Oct.put("011", "3");
24Oct.put("100", "4");
25Oct.put("101", "5");
26Oct.put("110", "6");
27Oct.put("111", "7");
28
就这样，性能总算提升了一些，用哈希表去找结果值。
接下来的问题在于切割和拼接，在这题中，很好地向我们展现了String和StringBuffer类的差别。
对于频繁的拼接，String类显得非常无力，这是由于String其实是不变的，它相当于重新拿了一块内存出来，而StringBuffer才是真正意义的拼接。
在切割上，我们使用了substring方法，在Java中还是第一次使用，所以查了一下参数规则：
substring的用法是begin（能取到）, end（取不到）
这个函数的使用没有任何疑问了，接下来是拼接，拼接的话我们有很多可以用，但是这里我们使用了append和insert，一个直接在最后插入，一个选择位置，我们把它作为需要在最前面插入的方法（前导0）。
但是在拼接时，由于我们截取是从后开始，也就是最后一位先出来，拼接时需要一点点往前插入，这对于性能是个考验，我们从中也可以看出来，append和insert的性能完全不同。
好了，还是想了个办法，我不能插入，我可以直接反转字符串输出呀。
先用append，再用reverse，性能特别高！
最后，还有一点，是发现了输入时好像也有点满，似乎听说使用缓冲区输入会稍微快一点
1BufferedReader in = new BufferedReader(
2 new InputStreamReader(System.in));
3 int n = Integer.parseInt(in.readLine());
4
这个类在java.io.*中，使用前需要引入。
终于得解了，不得不说尝试了好多次。
完整代码（包括了已经让我崩溃的注释们）：
1import java.util.*;
2import java.io.*;
3
4/**
5 * 历经千难万险！终于做出来了！
6 * 注释的除了上古遗迹的代码外还有为什么使用该方法的理由
7 * 这道题对于理解Java不同方法以及其性能差异非常有帮助，虽然花了好久才做出来
8 */
9public class HexToOct {
10 public static void main(String[] args) throws IOException{
11 // Scanner in = new Scanner(System.in);
12 // 因为用Scanner一次性读数据要爆炸 所以我们用BufferReader缓冲一下，需要引入java.io.*
13 BufferedReader in = new BufferedReader(
14 new InputStreamReader(System.in));
15 int n = Integer.parseInt(in.readLine());
16 String a[] = new String[n];
17 for (int i = 0; i < n; i++) {
18 a[i] = in.readLine();
19 }
20 // 本来用的String数组，然后用内置方法转换为十进制，但是效率太低，手写HashMap键值对匹配
21 HashMap<String, String> Hex = new HashMap<String, String>();
22 Hex.put("0", "0000");
23 Hex.put("1", "0001");
24 Hex.put("2", "0010");
25 Hex.put("3", "0011");
26 Hex.put("4", "0100");
27 Hex.put("5", "0101");
28 Hex.put("6", "0110");
29 Hex.put("7", "0111");
30 Hex.put("8", "1000");
31 Hex.put("9", "1001");
32 Hex.put("A", "1010");
33 Hex.put("B", "1011");
34 Hex.put("C", "1100");
35 Hex.put("D", "1101");
36 Hex.put("E", "1110");
37 Hex.put("F", "1111");
38 // String[] Hex = new String[] {"0000", "0001", "0010", "0011",
39 // "0100", "0101", "0110", "0111",
40 // "1000", "1001", "1010", "1011",
41 // "1100", "1101", "1110", "1111"};
42 HashMap<String, String> Oct = new HashMap<String, String>();
43 Oct.put("000", "0");
44 Oct.put("001", "1");
45 Oct.put("010", "2");
46 Oct.put("011", "3");
47 Oct.put("100", "4");
48 Oct.put("101", "5");
49 Oct.put("110", "6");
50 Oct.put("111", "7");
51
52 // int n = in.nextInt();
53 String x;
54 // String temp;
55 // String temp2;
56 // String oct;
57 // int n = in.nextInt();
58 int length = 0;
59 // StringBuffer temp2 = new StringBuffer();
60
61 // in.nextLine();
62
63 for (int i = 0; i < n; i++) {
64 // x = in.nextLine();
65 // 本来String的字符串拼接，性能不够，StringBuffer的性能提高了许多
66 StringBuffer temp = new StringBuffer();
67 StringBuffer oct = new StringBuffer();
68 // String xArr[] = a[i].split("");
69 // System.out.println(Integer.toOctalString(Integer.valueOf(x, 16)));
70 for (int j = 0; j < a[i].length(); j++) {
71 temp.append( Hex.get(a[i].substring(j, j+1)) );
72 }
73 length = temp.length();
74 if (length % 3 == 1) {
75 // insert用于在最前面插入不足的前导零
76 temp.insert(0, "00");
77 length += 2;
78 } else if (length % 3 == 2) {
79 temp.insert(0, "0");
80 length ++;
81 }
82 // System.out.println(length);
83 for (int j = 0; j < length; j+=3) {
84 int begin = length - j - 3;
85 // System.out.println("长度: " + length + "位置:" + begin + " - " + (length - j - 1));
86 // substring的用法是begin（能取到）, end（取不到）
87 String temp2 = temp.substring(begin, length - j);
88 // temp2.replace(0, 2, temp.substring(begin, length - j) );
89 // System.out.println(temp2);
90
91 if (!temp2.equals("") && ( begin != 0 || !temp2.equals("000") ))
92 // 本来用insert 性能和append相比差了太多，所以之后用reverse方法倒过来
93 oct.append(Oct.get(temp2));
94 }
95 System.out.println(oct.reverse().toString());
96 }
97 }
98}
99
评论 (0)