蓝桥杯 基础练习 十六进制转八进制
这道坑爹题真是让人绞尽脑汁,实际上我觉得大家应该也能感受到,很多看似不难的算法题实际上难度在于——如何处理大数的情况,这道题也是一样。
这题是一道非常好的题,因为我不熟悉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());
}
}
}
植入部分
如果您觉得文章不错,可以通过赞助支持我。
如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作。