CodeSky 代码之空

随手记录自己的学习过程

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

2015-12-27 23:29分类: Java评论: 0

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

这题是一道非常好的题,因为我不熟悉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)