蓝桥杯 基础练习 十六进制转八进制
这道坑爹题真是让人绞尽脑汁,实际上我觉得大家应该也能感受到,很多看似不难的算法题实际上难度在于——如何处理大数的情况,这道题也是一样。
这题是一道非常好的题,因为我不熟悉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)