【牛客网】华为机试题（00、C++版本）_牛客网华为编程题答案 c+++

华为机试题，本来以为对一些基础的程序还是有点信心的；不过不练不知道，一练吓一跳。平时虽然也都码程序，但是一到机试题就各种乱七八的不适应。还是要加强一下练习。

 

1、字符串最后一个单词的长度

题目描述：计算字符串最后一个单词的长度，单词以空格隔开。

例如：输入Hello World，输出5。

解答：这道题主要是练习一下字符串的输入和指定字符的查找。

#include <iostream>
using namespace std;
#include <string>
 
int main(){
    string s;
    getline(cin,s);
    int j=0;
    for(int i=s.length()-1; i>=0; i--){
        if(s[i]!=' '){
            j++;
        }else{
            break;
        }
    }
    cout<<j;
    return 0;
}

如果熟悉C++的各种函数的话，可以使用String的rfind()函数（寻找某个字符最后一次出现的序号）、find()函数（寻找某个字符第一次出现的序号）。

#include <iostream>
using namespace std;
#include <string>
 
int main() {
	string s;
	getline(cin, s);
	int j;
	j = s.length() - 1 - s.rfind(' ');
	cout << j;
	return 0;
}

 

2、计算字符个数

题目描述：写出一个程序，接受一个有字母和数字以及空格组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。

例如：输入ABCDEF A，输出1。

解答：这道题主要是练习一下大小写的改写。

#include <iostream>
using namespace std;
#include <string>
 
int main()
{
	string s;
	getline(cin, s);
	char c;
	cin >> c;
	int count = 0;
	for (int i = 0; i<s.length(); i++) {
		if (s.at(i)== toupper(c)|| s.at(i) == tolower(c))
			count++;
	}
	cout << count;
	return 0;
}

或者，也可以使用C语言来编写：

#include <stdio.h>
#include <string.h>
  
int main()
{
   char str[10000];
   char ch;
   int len = 0;
   gets(str); 
   ch = getchar();              //scanf("%c",&ch); 
   for(int i = 0; i < strlen(str); i++)
   {
            if(str[i] == ch || str[i] == ch -32 || str[i] == ch + 32)
                len++;
   }
   printf("%d\n",len);
   return 0;
}

注意一点：在C++中字符串长度可以用.size()、.length()方法；而strlen(char *)，若放入一个字符串常量是可以求长度的，但是若放入一个字符串变量则不行。这三个方法都不计算字符串最后的结束符'\0'，甚至可以说是，遇到第一个字符串结束符'\0'就停止计算个数了。

注意：如果使用sizeof()来计算字符串变量的长度是不正确的！C++标准库中的string类的对象在创建时会保留额外的内存空间，以便于用户调用append成员函数或者给string对象重新赋值时不会发生越界行为。所以，最小默认为28。

sizeof 操作函数类型：

int f1(){return 0;};
double f2(){return 0.0;}
void f3(){}
 
cout<<sizeof(f1())<<endl;     // f1()返回值为int，因此被认为是int
cout<<sizeof(f2())<<endl;     // f2()返回值为double，因此被认为是double
cout<<sizeof(f3())<<endl;     // 错误！无法对void类型使用sizeof
cout<<sizeof(f1)<<endl;       // 错误！无法对函数指针使用sizeof   
cout<<sizeof*f2<<endl;        // *f2，和f2()等价，被认为是double

 

3、明明的随机数

题目描述：明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

例如：输入11 10 20 40 32 67 40 20 89 300 400 15，输出10 15 20 32 40 67 89 300 400。

解答：原本做这道题就是很机械地排序来做：

#include <iostream>
using namespace std;
 
int main()
{
	int count;
	while (cin >> count) {
		int temp, flag = 0;
		int num[1000];
		for (int i = 0; i < count; i++) {
			cin >> num[i];
		}
		for (int i = 0; i < count - 1; i++) {
			for (int j = i + 1; j < count - flag; j++) {
				if (num[i] > num[j]) {
					temp = num[i];
					num[i] = num[j];
					num[j] = temp;
				}
				if (num[i] == num[j]) {
					flag++;
					for (int k = j; k < count - 1; k++) {
						num[k] = num[k + 1];
					}
					j--;
				}
			}
		}
		for (int i = 0; i < count - flag; i++) {
			cout << num[i] << endl;
		}
	}
	return 0;
}

看得出来，算法复杂度很高。后来发现了一个很巧妙的方法，通过计数排序来完成：

#include <iostream>
using namespace std;
 
int main() {
    int N, n;
    while (cin >> N) {
        int a[1001] = { 0 };
        while (N--) {
            cin >> n;
            a[n] = 1;
        }
        for (int i = 0; i < 1001; i++)
            if (a[i])
                cout << i << endl;
    }
    return 0;
}

这个方法在之前大疆的笔试题中也遇到了：【嵌入式基础】2014大疆嵌入式笔试题（附超详细解答，上篇）。

 

4、字符串分隔

题目描述：连续输入两个字符串，请按长度为8拆分每个字符串后输出到新的字符串数组； 长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。 

例如：输入abc 123456789，输出abc00000 12345678 90000000。

解答：拆分字符串，很传统的方法是：

#include <iostream>
using namespace std;
#include <string>
 
void fun(string s) 
{
	char str[13][8];
	int num = 0, count = 0;
	for (int j = 0; j < s.length(); j++) {
		if (count == 8) {
			count = 0;
			num++;
		}
		str[num][count] = s.at(j);
		count++;
	}
	while (count != 8) {
		str[num][count] = '0';
		count++;
	}
	for (int i = 0; i < num + 1; i++) {
		for (int j = 0; j < 8; j++) {
			cout << str[i][j];
		}
		cout << endl;
	}
}
 
int main() 
{
	string s1, s2;
	getline(cin, s1);
	getline(cin, s2);
	fun(s1);
	fun(s2);
 
	return 0;
}

这样做虽然也能获得答案，但是很明显，还是有点绕的。其实可以利用string的substr()方法来解决：

#include <iostream>
using namespace std;
#include <string>
 
void fun(string s) 
{
	while (s.size() > 8) {
		cout << s.substr(0, 8) << endl;
		s = s.substr(8);
	}
	cout << s.append(8 - s.size(), '0') << endl;
}
int main() {
	string s1, s2;
	getline(cin, s1);
	getline(cin, s2);
	fun(s1);
	fun(s2);
 
	return 0;
}

瞬间感觉整个程序都清晰了许多！下面分析一下string的substr()和substring()的区别：

 

• stringvar.substr(start , [length])：索引，长度
• strVariable.substring(start, end)：索引，索引

说明：

 

• 如果substr()函数的length为0或负数，将返回一个空字符串。如果没有指定该参数，则子字符串将延续到 stringvar 的最后；
• substring()方法将返回一个包含从start 到最后（不包含end）的子字符串的字符串；
• substring()方法使用start和end两者中的较小值作为子字符串的起始点。

 

5、进制转换

题目描述：写出一个程序，接受一个十六进制的数值字符串，输出该数值的十进制字符串。（多组同时输入 ）

例如：输入0xA，输出10。

解答：采取进制转换的计算方法，但是需要注意的是这里的方法不是那种死板的计算方法：

#include <iostream>
using namespace std;
#include <string>
 
int main() {
	string str;
	while (getline(cin, str)) {
		long num = 0; 
		for (int i = 2; i < str.length(); ++i) {
			if (str[i] >= '0' && str[i] <= '9')
				num = num * 16 + (str[i] - '0');
			else
				num = num * 16 + (str[i] - 'A' + 10);
		}
		cout << num << endl;
	}
 
	return 0;
}

但是这样的做法，不能够对输入的数值进行十六进制的判断。当然，本题还有一个非常投巧的方法，利用输入的办法来进行数制转换，而且可以完成十六进制的判断（hex：十六进制、oct：八进制、dev：十进制）：

#include <iostream>
using namespace std;
 
int main()
{
    int a;
    while(cin>>hex>>a){
        cout<<a<<endl;
    }
}

利用C语言也可以实现：

#include <stdio.h>
 
int main() 
{
	int a;
	while (scanf_s("%X", &a)) {
		printf("%d\n", a);
	}
}

 

6、质数因子

题目描述：输入一个正整数，按照从小到大的顺序输出它的所有质数的因子，最后一个数后面也要有空格。

例如：输入180，输出2 2 3 3 5 。

解答：这道看似很简单的题目，原来也是有坑的！刚开始的思路就是按部就班地循环--判断是否为质数--判断是否是因子：

#include <iostream>
using namespace std;
 
int main()
{
	long num;
	cin >> num;
	for (int i = 2; i <= num; i++) {
		bool flag = true;
		for (int j = 2; j < i; j++) {
			if (i%j == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			if (num%i == 0) {
				num = num / i;
				cout << i << ' ';
				i--;
			}
		}
	}
 
	return 0;
}

后来看了别人写的程序，突然发现自己智商可能真的不够用：

#include <iostream>
using namespace std;
 
int main(void)
{
	long input;
	while (cin >> input)
	{
		while (input != 1)
		{
			for (int i = 2; i <= input; i++)
			{
				if (input % i == 0)
				{
					input /= i;
					cout << i << ' ';
					break;
				}
			}
		}
 
	}
 
	return 0;
}

这个程序算不上完美，每次更新完input之后又都从2开始循环，在这一点上明显复杂度比我的代码高了不少。但是，这个程序让我突然发现，这道题目其实和是不是质数没有关系！从2开始循环，如果都有一个非质数因子，那么在这个因子的前面，该非质数的质数因子又是怎么能“幸免于难”的呢？

也就是说，这道题的程序只要如下就行了：

#include <iostream>
using namespace std;
 
int main()
{
	long num;
	cin >> num;
	for (int i = 2; i <= num; i++) {
		if (num%i == 0) {
			num = num / i;
			cout << i << ' ';
			i--;
		}
	}
 
	return 0;
}

 

7、取近似值

题目描述：写出一个程序，接受一个正浮点数值，输出该数值的近似整数值。如果小数点后数值大于等于5,向上取整；小于5，则向下取整。

例如：输入5.5，输出6。

解答：float强制转换成int为截取。

#include <iostream>
using namespace std;
 
int main()
{
	float f;
	cin >> f;
	if ((f - (int)f) >= 0.5)
		cout << (int)f + 1;
	else
		cout << (int)f;
 
	return 0;
}

后来看见网友的一个答案，瞬间觉得很赞，算是开拓一下：

#include <iostream>
using namespace std;
 
int main()
{
	float a;
	cin >> a;
	cout << int(a + 0.5);
 
	return 0;
}

 

8、合并表记录

题目描述：数据表记录包含表索引和数值，请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。

例如：输入4 0 1 0 2 1 2 3 4，输出0 3 1 2 3 4。

解答：用数组来装数据表记录进行解答。

#include <iostream>
using namespace std;
 
int main()
{
	int a[1000][2];
	int num;
	int temp;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> a[i][0] >> a[i][1];
	}
	for (int i = 0; i < num - 1; i++) {
		for (int j = i + 1; j < num ; j++) {
			if (a[i][0] > a[j][0]) {
				temp = a[i][0];
				a[i][0] = a[j][0];
				a[j][0] = temp;
				temp = a[i][1];
				a[i][1] = a[j][1];
				a[j][1] = temp;
			}
			if (a[i][0] == a[j][0]) {
				a[i][1] = a[i][1] + a[j][1];
				for (int k = j; k < num-1 ; k++) {
					a[k][0] = a[k + 1][0];
					a[k][1] = a[k + 1][1];
				}
				num--;
				j--;
			}
		}
	}
	for (int i = 0; i < num ; i++) {
		cout << a[i][0] << ' ' << a[i][1] << endl;
	}
 
	return 0;
}

我看网友其他人的答案，发现很多还是用第三题的计数排序的方法来解答的，也通过了测试。其实，这道题并没有规定索引值一定是整数啊！要是有小数，计数排序就没办法了。算是题目的锅吧，同样也附上代码：

#include<iostream>
using namespace std;
 
int  main()
{
	int Key_Value[10000] = { 0 }, Key, Value, Number, i;
	cin >> Number;
	for (i = 0; i<Number; i++)
	{
		cin >> Key >> Value;
		Key_Value[Key] += Value;
	}
	for (i = 0; i<10000; i++)
	{
		if (Key_Value[i] != 0)
			cout << i << ' ' << Key_Value[i] << endl;
	}
 
	return 0;
}

 

9、提取不重复的整数

题目描述：输入一个int型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。

例如：输入9876673，输出37689。

解答：很容易就想到用计数的方法来进行解决这道题：

#include<iostream>
using namespace std;
 
int  main()
{
	int num;
	cin >> num;
	int result;
	result = num;
	int a[10][2] = { 0 };
	while (num) {
		a[num % 10][0]++;
		num = num / 10;
	}
	while (result) {
		if (a[result % 10][0] == 1|| (a[result % 10][0] > 1&& a[result % 10][1]==0)) {
			cout << result % 10;
			a[result % 10][1] = 1;
		}
		result = result / 10;
	}
 
	return 0;
}

但是发现自己是一个很按部就班的人，总是把问题分成很多小目标，然后分别一一解决。但是缺少把几个目标相互关联的本事，就像这道题，可以将两个循环合并来解决：

#include<iostream>
using namespace std;
 
int main()
{
	int n;
	int a[10] = { 0 };
	int num = 0;
	cin >> n;
	while (n)
	{
		if (a[n % 10] == 0)
		{
			a[n % 10]++;            //这一步是更新，遇到下次相同的数会跳过
			num = num * 10 + n % 10;
		}
		n /= 10;
	}
	cout << num << endl;
 
	return 0;
}

 

10、字符个数统计

题目描述：编写一个函数，计算字符串中含有的不同字符的个数。字符在ACSII码范围内(0~127)。不在范围内的不作统计。

例如：输入abc，输出3。

解答：很简单的一个程序，计数法（华为机试题好像很喜欢这个方法，一定要注意）：

#include <iostream>
using namespace std;
#include <string>
 
int main()
{
	string s;
	getline(cin, s);
	int a[128] = { 0 }, num = 0;
	for (int i = 0; i<s.size(); i++) {
		a[(int)s.at(i)]++;
	}
	for (int i = 0; i < 128; i++) {
		if (a[i] != 0)
			num++;
	}
	cout << num;
 
	return 0;
}

 

11、数字颠倒

题目描述：输入一个整数，将这个整数以字符串的形式逆序输出。程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001。

例如：输入123，输出321。

解答：很简单的一个程序，只不过注意一下用do...while，而不是while：

#include <iostream>
using namespace std;
#include <string>
 
int main()
{
	int i;
	cin >> i;
	do {
		cout<<(char) (i % 10 + 48);
		i = i / 10;
	} while (i);
 
	return 0;
}

将数字转化为char的方法：

(char) (i % 10 + 48);
(char) (i % 10 + '0');

常见的ASCII码还是有点印象比较好：

0-9：48-57；A-Z：65-90；a-z：97-122。

 

12、句子逆序

题目描述：将一个英文语句以单词为单位逆序。所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符。

例如：输入“I am a boy”，输出“boy a am I”。

解答：单词逆序，但仍然要保持单词。通过substr()函数来进行截取：

#include <iostream>
using namespace std;
#include <string>
 
int main()
{
	string s, s1, s2;
	int flag = 0, i = 0;
	getline(cin, s);
	for (int j = 0; j < s.size(); j++) {
		if (s.at(j) == ' ') {
			s1 = s.substr(flag, j - flag);
			if (i == 0) {
				s2 = s1;
				i++;
			}
			else
				s2 = s1 + " " + s2;
			flag = j + 1;
		}
		if (j == s.size() - 1) {
			s1 = s.substr(flag, j - flag + 1);
			s2 = s1 + " " + s2;
		}
	}
	cout << s2;
 
	return 0;
}

参考网上的一些程序，发现一个很巧妙的方法！通过stack“先进后出”的特性：

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main()
{
	stack<string> ss;
	string s;
	while (cin >> s)
	{
		ss.push(s);
	}
	while (!ss.empty())
	{
		cout << ss.top();
		ss.pop();
		if (!ss.empty())
			cout << ' ';
	}
	cout << endl;
 
        return 0;
}

 

13、字串的连接最长路径查找

题目描述：给定n个字符串，请对n个字符串按照字典序排列。

例如：输入9 cap to cat card two too up boat boot，输出boat boot cap card cat to too two up。

解答：直接排序就行了。对于字符串“>、<、==、+”这些运算符都被重载了，可以直接用：

#include <iostream>
using namespace std;
#include <string>
 
int main()
{
	int num;
	cin >> num;
	string s[1000], temp;
	for (int i = 0; i < num; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < num-1; i++) {
		for (int j = 0; j < num-i-1; j++) {
			if (s[j] > s[j+1]) {
				temp = s[j];
				s[j] = s[j+1];
				s[j+1] = temp;
			}
		}
	}
	for (int i = 0; i < num; i++)
		cout << s[i] << endl;
 
	return 0;
}

参考其他人的程序，发现一堆使用STL封装的数据结构和函数的……总感觉脱离了出题人的本意了，原本考验算法的，直接一个函数就解决……（可能是因为自己不太熟悉这些函数就酸吧）：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
	int input;
	while (cin >> input)
	{
		string str;
		vector<string> vs;
		while (input--)
		{
			cin >> str;
			vs.push_back(str);
		}
		sort(vs.begin(), vs.end());
		vector<string>::iterator vit;
		for (vit = vs.begin(); vit != vs.end(); vit++)
		{
			cout << *vit << endl;
		}
	}
 
	return 0;
}

 

14、求int型正整数在内存总存储时1的个数

题目描述：输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。

例如：输入5，输出2。

解答：这道题可以使用i&(i-1)的方式来求1的个数：

#include <iostream>
using namespace std;
 
int main()
{
	int i,j=0;
	cin >> i;
	while (i) {
		i=i & (i - 1);
		j++;
	}
	cout << j;
 
	return 0;
}

当然，看了其他网友的程序，也有其他的方法：

#include<iostream>
using namespace std;
 
int main()
{
	int a, count;
	cin >> a;
 
	count = 0;
	while (a>0)
	{
		if (a & 1)
			count++;
		a >>= 1;
	}
	cout << count << endl;
 
	return 0;
}

或者：

#include<iostream>
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	int count = 0;
	while (t>0)
	{
		if (t % 2)   count++;
		t = t / 2;
	}
	cout << count << endl;
 
	return 0;
}

 

15、坐标移动

题目描述：开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。输入：合法坐标为A(或者D或者W或者S) + 数字（两位以内），坐标之间以“;”分隔。非法坐标点需要进行丢弃。如AA10;  A1A;  $%$;  YAD; 等。

例如：输入A10;S20;W10;D30;X;A1A;B10A11;;A10;，输出10,-10。

解答：这道题还是在华为机试题里第一次遇到的比较复杂的题目。想了蛮久，用了一堆的标志位：

#include <iostream>
using namespace std;
#include <string>
 
int main()
{
	string s;
	while (getline(cin, s)) {
		int x = 0, y = 0;
		int m = 0, n = -1, k = 0;
		bool flag = false, flag1 = false;
		for (int i = 0; i < s.size(); i++) {
			if (s.at(i) == 'W' || s.at(i) == 'A' || s.at(i) == 'S' || s.at(i) == 'D') {
				if (n != -1) flag1 = true;
				if (s.at(i) == 'W') n = 0;
				if (s.at(i) == 'A') n = 1;
				if (s.at(i) == 'S') n = 2;
				if (s.at(i) == 'D') n = 3;
				if (k == 0) flag = true;
			}
			k++;
			if (flag) {
				if (s.at(i) <= '9'&&s.at(i) >= '0') {
					m = m * 10 + s.at(i) - '0';
				}
			}
			if (s.at(i) == ';') {
				if (flag1) m = 0;
				if (n == 0) y = y + m;
				if (n == 1) x = x - m;
				if (n == 2) y = y - m;
				if (n == 3) x = x + m;
				n = -1;
				m = 0;
				k = 0;
				flag = false;
				flag1 = false;
			}
		}
		cout << x << ',' << y << endl;
	}
 
	return 0;
}

需要注意的是：我这边采用循环输入的方式：

 

while (getline(cin, s)) {
        ...
}

如果不采用这种方式的话，会报错，通过不了测试……具体什么时候需要循环输入，什么时候不需要循环输入……不知道……

参考网上的解答，发现了一个不错的程序：

#include<iostream>
#include<string>
#include<cstddef>   //std::size_t
using namespace std;
 
int main()
{
	string str;
	while (cin >> str) {
		pair<int, int> point(0, 0);               //point.first point.second
		size_t found = str.find_first_of(';');  //找到第一个';'的位置
		int start = 0;
 
		while (found != string::npos) {
			string s1 = str.substr(start, found - start);
			start = found + 1;
			found = str.find_first_of(';', found + 1);
 
			if (s1.size()>1 && s1.size() <= 3) {    //合法的字符个数：2或3
				char c = s1[0];
				int n = 0;
				int invalid = 0;    //数字为是否非法
				for (int i = 1; i<s1.size(); ++i) { //数字位判断与提取，A1A
					if (s1[i] >= '0'&&s1[i] <= '9')
						n = n * 10 + (s1[i] - '0');
					else {
						invalid = 1;
						break;
					}
				}
				if (invalid == 0) {
					switch (c)
					{
					case 'A': {point.first -= n; break; }
					case 'D': {point.first += n; break; }
					case 'W': {point.second += n; break; }
					case 'S': {point.second -= n; break; }
					}
				}
 
			}
		}
		cout << point.first << ',' << point.second << endl;
	}
 
	return 0;
}

这段程序采用substr()函数来截取字符串的一部分，同时使用find_first_of()函数来寻找字符串当中的字符。需要注意的是，find_first_of()函数的第二个参数为：查找的起始索引位置。

注意：find()函数和find_first_of()函数两者的意义大体相同，它们之间最大的区别就是如果在一个字符串str1中使用find_first_of()来查找另一个字符串str2，如果str1中含有str2中的任何字符，则就会查找成功；而find则不同。