首页 > 剑指offer > 2014届华为校园招聘机试题
2014
07-06

2014届华为校园招聘机试题

一、题目描述(60分):
通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序,若字符串中出现多个相同的字符,将非首次出现的字符过滤掉。
比如字符串“abacacde”过滤结果为“abcde”。

要求实现函数:void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr);

【输入】 pInputStr:  输入字符串
lInputLen:  输入字符串长度
【输出】 pOutputStr: 输出字符串,空间已经开辟好,与输入字符串等长;

【注意】只需要完成该函数功能算法,中间不需要有任何IO的输入输出

示例
输入:“deefd”        输出:“def”
输入:“afafafaf”     输出:“af”
输入:“pppppppp”     输出:“p”

main函数已经隐藏,这里保留给用户的测试入口,在这里测试你的实现函数,可以调用printf打印输出
当前你可以使用其他方法测试,只要保证最终程序能正确执行即可,该函数实现可以任意修改,但是不要改变函数原型。一定要保证编译运行不受影响。

解答

题目很简单,简单的hash统计即可。

 

void stringFilter(const char* pInputStr , long lInputLen , char* pOutputStr)  
{  
    bool hash[26] = {0};    //统计字符是否出现  
    int i , j;  
    for(i = 0 , j = 0 ; i < lInputLen; ++i)  
    {  
        if(false == hash[pInputStr[i] - 'a'])     //该字符还木有出现过  
        {  
            hash[pInputStr[i] - 'a'] = true;  
            pOutputStr[j++] = pInputStr[i];  
        }  
    }  
    pOutputStr[j] = '\0';  
}

二、题目描述(40分):
通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串。
压缩规则:
1、仅压缩连续重复出现的字符。比如字符串”abcbc”由于无连续重复字符,压缩后的字符串还是”abcbc”。
2、压缩字段的格式为”字符重复的次数+字符”。例如:字符串”xxxyyyyyyz”压缩后就成为”3x6yz”。

要求实现函数:
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);

【输入】 pInputStr:  输入字符串
lInputLen:  输入字符串长度
【输出】 pOutputStr: 输出字符串,空间已经开辟好,与输入字符串等长;

【注意】只需要完成该函数功能算法,中间不需要有任何IO的输入输出

示例
输入:“cccddecc”   输出:“3c2de2c”
输入:“adef”     输出:“adef”
输入:“pppppppp” 输出:“8p”

解答

这个也不难,注意统计的是相邻的个数,遍历一边即可。很快写出了下面的代码:

void stringZip2(const char *pInputStr, long lInputLen, char *pOutputStr) {
	int cnt = 0;
	long j = 0;//输出字符串的下标
	for (long i = 0; i < lInputLen; i++) {
		if (pInputStr[i] == pInputStr[i + 1])
			cnt++;
		else {
			if (cnt > 0)
				pOutputStr[j++] = '1' + cnt;
			pOutputStr[j++] = pInputStr[i];
			cnt = 0;
		}
	}
	pOutputStr[j] = 0;
}

输入上面的几个测试,运行完美。但是,这个是有bug的,当一个字符连续出现的次数超过9,就会出错。

pOutputStr[j++] = ’1′ + cnt; 只考虑到了cnt < 9时的情况!一定要注意注意这类低级错误。修改后的代码:

void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr) {
	int cnt = 0;
	long j = 0;//输出字符串的下标
	for (long i = 0; i < lInputLen; i++) {
		if (pInputStr[i] == pInputStr[i + 1])
			cnt++;
		else {
			if (cnt > 0){
				int pow = 1; //pow 表示 10^n, n为cnt的位数
				int tmp = cnt;
				while(tmp > 0){
					tmp /= 10;
					pow *= 10;
				}
				pow /= 10;
				//从最高位开始
				while(pow > 0){
					int c = cnt / pow;
					pOutputStr[j++] = '0' + c;
					cnt = cnt % pow;
					pow /= 10;
				}
			}
			pOutputStr[j++] = pInputStr[i];
			cnt = 0;
		}
	}
	pOutputStr[j] = 0;
}

三、题目描述(50分):
通过键盘输入100以内正整数的加、减运算式,请编写一个程序输出运算结果字符串。
输入字符串的格式为:“操作数1 运算符 操作数2”,“操作数”与“运算符”之间以一个空格隔开。

补充说明:
1、操作数为正整数,不需要考虑计算结果溢出的情况。
2、若输入算式格式错误,输出结果为“0”。

要求实现函数:
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr);

【输入】 pInputStr:  输入字符串
lInputLen:  输入字符串长度
【输出】 pOutputStr: 输出字符串,空间已经开辟好,与输入字符串等长;

【注意】只需要完成该函数功能算法,中间不需要有任何IO的输入输出

示例
输入:“4 + 7”  输出:“11”
输入:“4 – 7”  输出:“-3”
输入:“9 ++ 7”  输出:“0” 注:格式错误

解答

模拟,就是有些繁琐,需要判断的比较多。

void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr){
	char buffer[200];
	int num1,num2;
	int i = 0;
	int j = 0;
	while( pInputStr[i] >= '0' && pInputStr[i] <= '9'){
		buffer[j++] = pInputStr[i];
		i++;
	}

	//检测输入格式是否合法, i应该指向第一个空格
	if(i == 0 || pInputStr[i] != ' '){
		pOutputStr[0] = '0';
		pOutputStr[1] = 0;
		return;
	}
	i++;//i指向操作符
	char tmp;
	if(pInputStr[i] == '+' || pInputStr[i] == '-'
			|| pInputStr[i] == '*' || pInputStr[i] == '/'){
		tmp = pInputStr[i];
		i++; //i应该指向运算符之后的空格
	}else{
		pOutputStr[0] = '0';
		pOutputStr[1] = 0;
		return;
	}
	if(pInputStr[i] != ' '){
		pOutputStr[0] = '0';
		pOutputStr[1] = 0;
		return;
	}
	i++;//i指向第二个操作数
	buffer[j] = 0;
	num1 = atoi(buffer);
	//开始获得第二个操作数
	j=0;
	while( pInputStr[i] >= '0' && pInputStr[i] <= '9'){
		buffer[j++] = pInputStr[i];
		i++;
	}
	//判断结尾处,是否是合法的
	if(pInputStr[i] != 0){
		pOutputStr[0] = '0';
		pOutputStr[1] = 0;
		return;
	}
	num2 = atoi(buffer);
	//计算结果
	if(tmp == '+') itoa(num1 + num2, pOutputStr, 10);
	else if(tmp == '-') itoa(num1 - num2, pOutputStr, 10);
	else if(tmp == '*') itoa(num1 * num2, pOutputStr, 10);
	else itoa(num1 / num2, pOutputStr, 10);
}

参考:http://blog.csdn.net/hackbuteer1/article/details/11132567