【机试题】2019华为优招机试题（附超详细解答）

墨蓝 2022-05-16 00:49 241阅读 0赞

华为优招机试题还是老样子的三道大题，分值为100、200、300。理论上是答对一道即可过关，但这是理论上的。下面是2018年8月1日批次的华为优招机试题详解。

## 重复字符排序 ##

题目描述：找出输入字符串中的重复字符，再根据ASCII码把重复的字符从小到大排序。

例如：输入ABCABCdd，输出ABCd。

解答：计数排序，没有什么难度（计数排序是华为机试题出现次数最多的排序方法，没有之一）：

#include <iostream>
    using namespace std;
    #include <string>
    
    int main()
    {
    	string s;
    	getline(cin, s);
    	int count[200] = { 0 };
    	for (int i = 0; i < s.length(); i++)
    		count[s.at(i)]++;
    	for (int i = 0; i < 127; i++) {
    		if (count[i] > 1)
    			cout << (char)i;
    	}
    
    	return 0;
    }

## 重复字符最长串 ##

题目描述：给定一串字符，里面有些字符有连续出现的特点，请寻找这些连续出现字符中最长的串，如果最长的串有多个，请输出字符ASCII码最小的那一串。

例如：输入aaabbbbbcccccccczzzzzzzz，输出cccccccc。

解答：利用两个长度为2的数组，一个存放当前字符及其连续重复长度，另一个存放历史最长重复的字符及其长度值。只要做好逻辑思路就应该能轻松做完：

#include <iostream>
    using namespace std;
    #include <string>
    
    int main()
    {
    	string s;
    	getline(cin, s);
    	char c[2] = { s.at(0) };
    	int num[2] = { 1 };
    	for (int i = 1; i < s.length(); i++) {
    		if (s.at(i) == c[0])
    			num[0]++;
    		else {
    			if (num[0] > num[1] || (num[0] == num[1] && c[0] < c[1])) {
    				c[1] = c[0];
    				num[1] = num[0];
    			}
    			c[0] = s.at(i);
    			num[0] = 1;
    			
    		}
    	}
    	if (num[0] > num[1] || (num[0] == num[1] && c[0] < c[1])) {
    		c[1] = c[0];
    		num[1] = num[0];
    	}
    	for (int i = 0; i < num[1]; i++)
    		cout << c[1];
    
    	return 0;
    }

## 小镇广告牌 ##

题目描述：已知某小镇的房子沿直线分布，给定一个有序整数数组arr，里面的每个镇代表小镇每栋房子的一维坐标点。现在需要建N个广告牌，广告牌只能建立在这些坐标点上，使得每个坐标点离广告牌的总距离最短，求这个最短的总距离。

输入描述：输入最后一个为N值，其余的为arr值，需要考生自行处理。

例如：输入1 2 3 4 5 1000 2，输出6。

解答：这是一条经典的动态规划的题目：

设置一个数组dis\[i\]\[j\]

#include <iostream>
    using namespace std;
    
    int main()
    {
    	int arr[100] = { 0 };
    	int m = 0, n;		//m：小镇个数；n：广告牌个数
    	int x, dis[100][100] = { 0 };
    	int total[100][100] = { 0 };
    
    	while (cin >> x)
    		arr[m++] = x;
    	n = arr[--m];
    
    	for (int i = 0; i < m; i++) {
    		for (int j = i; j < m; j++) {
    			for (int k = i; k <= j; k++)
    				dis[i][j] += abs(arr[(i + j) / 2] - arr[k]);
    		}
    	}
    
    	for (int i = 0; i < m; i++)
    		total[i][1] = dis[i][m - 1];
    	for (int i = 2; i <= n; i++) {
    		for (int j = 0; j < m; j++) {
    			for (int k = j; k <= m-i; k++)
    				total[j][i] = dis[j][k] + total[k + 1][i - 1];
    		}
    	}
    
    	cout << total[0][n] << endl;
    
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDEwNzMw_size_16_color_FFFFFF_t_70]: /images/20220516/26834bcd53d44be9ab140fa935db75c9.png