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 ÷ : 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;
} 欢迎交流！！！！
得物app公司福利 401人发布
