2020/4/22 华为暑期实习笔试三道编程题

楼主ac前两道题，最后一道题自己注意力不是很集中，没做完。。。笔试结束后用回溯法+暴力解法写完了，但是发现一些小问题过不了测试用例，也就不再折腾了，希望评论区能有大佬朋友给出第三题的答案和思路

---------------------------------------------------------------------------

第一题比较简单

#include<queue>
#include<vector>
#include<iostream>
#include<stdio.h>
#include<numeric>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<functional>
#include<iterator>
#include<sstream>
#include<string>
#include <math.h>
#include<stdlib.h>
using namespace std;

int main() {
	string s;
	getline(cin, s);
	string tmp;
	for (auto& ch : s) {
		if (ch >= '0' && ch <= '9') {
			tmp += ch;
		}
	}
	sort(tmp.begin(), tmp.end());
	cout << tmp << endl;
	return 0;
}

---------------------------------------------------------------------------

第二题题目很繁琐，但其实并不难，只需要按图上的流程，反过来检验一遍就行了

1.找出各个分段

2.处理每一个分段的转义字符

3.检验每一个分段的长度

4.输出结果

int main() {
	string s;
	getline(cin, s);
	stringstream ss(s);
	vector<string> vec;
	string tool;
	while (ss >> tool) {
		vec.push_back(tool);
	}
	// 1.找分段
	vector<vector<string> > allPart;
	for (auto iter = vec.begin(); iter != vec.end();) {
		if (*iter == "5a") {
			while (iter != vec.end() && *iter == "5a") { ++iter; }
		}
		if (iter != vec.end()) {
			vector<string> aPart;
			while (iter != vec.end() && *iter != "5a") {
				aPart.push_back(*iter);
				++iter;
			}
			allPart.push_back(aPart);
		}
	}
	// 2.处理每一分段的转义字符
	for (auto pIter = allPart.begin(); pIter != allPart.end();) {
		bool isBadPart = false;
		for (auto iter = (*pIter).begin(); iter < (*pIter).end()-1;) {
			if (*iter == "5b" && (*(iter+1) == "bb" || *(iter + 1) == "ba")) {
				// 5b
				if (*iter == "5b" && *(iter + 1) == "bb") {
					iter = (*pIter).erase(iter + 1);
				}
				// 5a
				else if (*iter == "5b" && *(iter + 1) == "ba") {
					*iter = "5a";
					iter = (*pIter).erase(iter + 1);
				}
			}
			else if (*iter == "5b" && (*(iter + 1) != "bb" && *(iter + 1) != "ba")) {
				isBadPart = true;
				break;
			}
			else {
				++iter;
			}
		}
		if (isBadPart == true) {
			pIter = allPart.erase(pIter);
			continue;
		}
		++pIter;
	}
	// 3.检验长度
	for (auto pIter = allPart.begin(); pIter != allPart.end();) {
		string lenStr = (*pIter).back();
		int len = strtoll(lenStr.c_str(), NULL, 16);
		if (len != (*pIter).size()-1) {
			pIter = allPart.erase(pIter);
		}
		else {
			++pIter;
		}
	}

	// 输出正确报文
	for (auto &eachPart : allPart) {
		cout << "5a ";
		for (auto &e : eachPart) {
			if (e == "5a") {
				cout << "5b ba ";
			}
			else if (e == "5b") {
				cout << "5b bb ";
			}
			else {
				cout << e << ' ';
			}
		}
	}
	cout << "5a " << endl;
	return 0;
}

---------------------------------------------------------------------------

第三题，我觉得是有点难度的，目前还没做出来，下面是我的实现，暂未通过用例

思路是

1.先用回溯法（DFS）找出所有划分的方案

2.根据每一种划分方案找到其对应的最小分段值

3.找出最大的最小分段值，把对应的划分方案加上符号'/'打印出去

void DFS(vector<vector<int> >& allDivide, vector<int> tmp, int start, int limit, int m) {
	if (tmp.size() == limit) {
		allDivide.push_back(tmp);
		return;
	}
	for (int i = start; i < m; ++i) {
		tmp.push_back(i);
		DFS(allDivide, tmp, i + 1, limit, m);
		tmp.pop_back();
	}
}


int main() {
	int m, k;
	cin >> m >> k;
	vector<int> arr(m);
	int tmp;
	for (int i = 0; i < arr.size(); ++i) {
		cin >> tmp;
		arr[i] = tmp;
	}
	vector<vector<int> > allDivide;
	vector<int> temp;
	DFS(allDivide, temp, 1, k - 1, m);
	vector<int> minValues;
	for (auto &divide : allDivide) {
		vector<int> values;
		values.push_back(accumulate(arr.begin(), arr.begin() + divide.front(), 0));
		for (int i = 1; i < divide.size()-1; ++i) {
			values.push_back(accumulate(arr.begin()+divide[i], arr.begin() + divide[i+1], 0));
		}
		values.push_back(accumulate(arr.begin() + divide.back(), arr.end(), 0));
		minValues.push_back(*min_element(values.begin(), values.end()));
	}
	int maxIndex = 0;
	for (int i = 1; i < minValues.size(); ++i) {
		if (minValues[i] > minValues[maxIndex]) {
			maxIndex = i;
		}
	}
	// 输出
	vector<int> ans = allDivide[maxIndex];
	cout << minValues[maxIndex] << endl;
	output(ans);
	cout << "---" << endl;
	int countCout = 0, countIndex = 0;
	for (int i = 0; i < arr.size(); ++i) {
		cout << arr[i] << ' ';
		++countCout;
		if (countIndex < ans.size() && countCout == ans[countIndex]) {
			cout << "/ ";
			++countIndex;
		}
	}
	system("pause");
	return 0;
}

欢迎交流！！！！