学步园

　　给定n个十六进制正整数，输出它们对应的八进制数。

　　输入的第一行为一个正整数n （1<=n<=10）。

　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。

　　输出n行，每行为输入对应的八进制正整数。

　　输入的十六进制数不会有前导0，比如012A。

　　输出的八进制数也不能有前导0。

　　先将十六进制数转换成某进制数，再由某进制数转换成八进制。

代码：

先贴c++的代码：

#include<iostream>
#include<string>
using namespace std;

void toOx(string s)
{
	int t = s.length() % 3;
	if (t != 0)
	{
		for (int i = 0; i < 3 - t; ++i)
		{
			s = '0' + s;
		}
	}
	int sum = 0;
	bool notZ = false;
	for (int i = 0; i < s.length(); i += 3)
	{
		sum = 0;
		for (int j = 0; j < 2; ++j)
		{
			sum += (s[i + j] == '0') ? 0 : 2 * (2 - j);
		}
		sum += (s[i + 2] == '0') ? 0 : 1;
		if (sum == 0 && !notZ)
		{
			notZ = true;
		}
		else
		{
			notZ = true;
			cout << sum;
		}

	}
	cout << endl;
}
string toBin(string s)
{
	string st = "";
	for (int i = 0; i < s.length(); ++i) {
		switch (s[i]) {
		case '0':
			st += "0000";
			break;
		case '1':
			st += "0001";
			break;
		case '2':
			st += "0010";
			break;
		case '3':
			st += "0011";
			break;
		case '4':
			st += "0100";
			break;
		case '5':
			st += "0101";
			break;
		case '6':
			st += "0110";
			break;
		case '7':
			st += "0111";
			break;
		case '8':
			st += "1000";
			break;
		case '9':
			st += "1001";
			break;
		case 'A':
			st += "1010";
			break;
		case 'B':
			st += "1011";
			break;
		case 'C':
			st += "1100";
			break;
		case 'D':
			st += "1101";
			break;
		case 'E':
			st += "1110";
			break;
		case 'F':
			st += "1111";
			break;
		}
	}
	return st;
}

int main()
{
	int n;
	cin >> n;
	string *s = new string[n];
	for (int i = 0; i < n; ++i)
	{
		cin >> s[i];
	}
	for (int j = 0; j < n; ++j)
	{
		toOx(toBin(s[j]));
	}
	delete[]s;
	string st;
	return 0;
}

后是java的代码（和c++逻辑是一样的）：

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s[] = new String[n];
		for (int i = 0; i < n; ++i) {
			s[i] = in.next();
		}
		in.close();
		for (int i = 0; i < s.length; ++i) {
			toOx(toBin(s[i]));
		}
	}

	public static String toBin(String s) {
		char[] a = s.toCharArray();
		String st = "";
		for (int i = 0; i < s.length(); ++i) {
			switch (a[i]) {
			case '0':
				st += "0000";
				break;
			case '1':
				st += "0001";
				break;
			case '2':
				st += "0010";
				break;
			case '3':
				st += "0011";
				break;
			case '4':
				st += "0100";
				break;
			case '5':
				st += "0101";
				break;
			case '6':
				st += "0110";
				break;
			case '7':
				st += "0111";
				break;
			case '8':
				st += "1000";
				break;
			case '9':
				st += "1001";
				break;
			case 'A':
				st += "1010";
				break;
			case 'B':
				st += "1011";
				break;
			case 'C':
				st += "1100";
				break;
			case 'D':
				st += "1101";
				break;
			case 'E':
				st += "1110";
				break;
			case 'F':
				st += "1111";
				break;
			}
		}
		return st;
	}

	public static void toOx(String s) {
		int t = s.length() % 3;
		if (t != 0) {
			for (int i = 0; i < 3 - t; ++i) {
				s = 0 + s;
			}
		}
		int sum = 0;
		boolean notZ = false;
		char[] a = s.toCharArray();
		for (int i = 0; i < s.length(); i += 3) {
			sum = 0;
			for (int j = 0; j < 2; ++j) {
				sum += (a[i + j] == '0') ? 0 : 2 * (2 - j);
			}
			sum += (a[i + 2] == '0') ? 0 : 1;
			if (sum == 0 && !notZ) {
				notZ = true;
			} else {
				notZ = true;
				System.out.print(sum);
			}
		}
		System.out.println();
	}
}

这里说下这个题，我总共提交了16次，开始我只提交了java版本，但是一直是运行超时，后来我又开始提交c++版本，试了几次之后，最终提交成功，100分，109ms，就是上面的代码，然后我紧接着改写成java代码，然后再提交，但还是运行超时，最后只好放弃java版本。

因为我提交了16次，所以这里多说些，关于这个算法，最初我想的是十六进制先转换成十进制，在转换成八进制，因为前面有一道题是十六进制转十进制的，这样的话可以偷下懒，但是提交了几次总是出错，后来仔细看题发现“每个十六进制数长度不超过100000”，那就说明测试数据会有至少一个长度是100000的十六进制数，所以转换成十进制的想法是不对的，应该转化成二进制，一位十六进制数是四位二进制，三位二进制数是一位八进制，应该按这个思路进行。

这里最简单的方法就是把十六进制转换成一个二进制字符串，然后使用switch把三位二进制转化成一位八进制，我用java这样试过几次，但是还是超时，最终放弃，后来想到可以用算数的方法计算八进制（我也不清楚到底哪种方法更快，我没在c++里使用过前面说的switch方法），就像代码里写的那样。最终几次尝试，终于成功。还有因为对速度要求比较高，所以尽量在原串上进行操作，能不提取字符串就不提取，我也试过使用类似substring的方法在长串里提取三个字符，但是超时了。还有几次都是因为自己的疏忽而导致运行错误，下次更细心些，引以为戒好了。

（最后更新下，java代码，在toBin方法里，把String对象st改成StringBuffer，把+=改成append().超时问题就解决了）