牛客网华为机试
上篇：算法|牛客网华为机试10-20C++

HJ21 简单密码

题目描述：

解题思路：
使用switch case加ASCII码大小写字母差32来解答，33为向后移动一位。
解法：

#include <iostream>using namespace std;int main() {string str;cin >> str;for (int i=0; i<str.size(); i++) {switch(str[i]) {case 'A' ... 'Y': str[i] += 33; break;case 'Z': str[i] = 'a'; break;case 'a' ... 'c': str[i] = '2'; break;case 'd' ... 'f': str[i] = '3'; break;case 'g' ... 'i': str[i] = '4'; break;case 'j' ... 'l': str[i] = '5'; break;case 'm' ... 'o': str[i] = '6'; break;case 'p' ... 's': str[i] = '7'; break;case 't' ... 'v': str[i] = '8'; break;case 'w' ... 'z': str[i] = '9'; break;default: break;}}cout << str << endl;
}

HJ22 汽水瓶

题目描述：

解题思路：
可以接空瓶子，相当于每有两个空瓶就可以喝一瓶，结果直接除以2即可。
解法：

#include <iostream>
using namespace std;int main() {int a;while (cin >> a) { // 注意 while 处理多个 caseif(a == 0)break;cout<< a/2 <<endl;}
}

HJ23 删除字符串中出现次数最少的字符

题目描述：

解题思路：
首先使用map将所有字母出现次数记录；第二步找出出现次数最少的次数，如果为1就是最少的；第三步找出所有出现次数最少的字母；最后排除所有出现次数最少的字母输出结果。
解法：

#include <iostream>
#include <map>
#include <vector>
#include <algorithm> // 包含 std::find
using namespace std;int main() {string str;cin>>str;map<char,int> all_char; // key:字母 value:出现的次数for(auto a:str){// 如果只出现过一次if(all_char.find(a) == all_char.end()){all_char[a] = 1;continue;}else{all_char[a]++;}}// 找出出现最少的次数int min_int = 0;for(auto one_char:all_char){if(min_int == 0)min_int = one_char.second;if(min_int>one_char.second){min_int = one_char.second;if(min_int == 1)break;}}vector<char> min_char;// 使用迭代器遍历map 找出所有出现次数最少的字母for (auto it = all_char.begin(); it != all_char.end(); ) {if (it->second == min_int) {min_char.push_back(it->first);} ++it;}// 如果字母不是最少出现的字母之一 输出for(auto c:str){if(std::find(min_char.begin(), min_char.end(), c) == min_char.end())cout<<c;}
}

HJ24 合唱队

题目描述：

解题思路：
使用动态规划，找到最长递增子序列+最长递减子序列；
解法：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;int main() {int n;while (cin>>n) {// 输入的数组int tmp;vector<int> vec;for(int i=0;i<n;++i){cin>>tmp;vec.push_back(tmp);}// 最长递增子序列长度if(vec.empty()) return 0;vector<int> dp1(n,0);	for(int i=0;i<n;++i){dp1[i] = 1;for(int j=0;j<i;++j){if(vec[i]>vec[j])dp1[i] = max(dp1[i],dp1[j]+1);}}// 最长递减子序列长度vector<int> dp2(n,0);for(int i = n-1; i >= 0;--i){dp2[i] = 1;for(int j=n-1;j>i;--j){if(vec[i] > vec[j])dp2[i] = max(dp2[i], dp2[j]+1);}}int maxLength = 0;for(int i=0;i<n;++i){// i是中点if(maxLength<dp1[i]+dp2[i]-1){maxLength = dp1[i]+dp2[i]-1;}}cout<< n-maxLength<<endl;}return 0;
}

HJ25 数据分类处理

题目描述：

解题思路：
就是找I里是否包含R的子串，输出索引和值。

解法：

// 就是找I里是否包含R的子串，输出索引和值
#include <bits/stdc++.h>using namespace std;int main() {// 这个是把我们的I数组输入进去int n;cin >> n;vector<string> I(n);for (auto &it : I) cin >> it;// 这个实现了我们R数组的去重和排序int m;cin >> m;set<int> st;for (int i = 1; i <= m; i++) {int tmp;cin >> tmp;st.insert(tmp);}vector<int> res;for (auto &it : st) {// cnt是有多少个// okk是我们是否找到int cnt = 0;bool okk = false;for (auto &it1 : I) {// 如果找到了存入数组if (it1.find(to_string(it)) != string::npos) {cnt += 1;if (okk == false) {res.emplace_back(it);okk = true;}}}// !=0说明有找到if (cnt != 0) {// 我们每一次把我们的下标和我们的值存入res.emplace_back(cnt);for (int i = 0; i < n; i++) {if (I[i].find(to_string(it)) != string::npos) {res.emplace_back(i);res.emplace_back(stoi(I[i]));}}}}cout << res.size() << " ";for (auto &it : res) {cout << it << " ";}cout << "\n";return 0;
}

HJ26 字符串排序

题目描述：

解题思路：
首先利用和大小写字母A的差值，对应0-26，来将所有字母按顺序排好；再找出原始字符串里所有字母进行替换。
解法：

#include <iostream>
#include <vector>
using namespace std;
string String_Sorting(string str)
{int len = str.size(); //获取字符串长度vector <char> vec; //用一个 char 型的向量存储按规则排序后的字符串中的字母字符//规则一：英文字母从 A 到 Z 排列，不区分大小写。//规则二：同一个英文字母的大小写同时存在时，按照输入顺序排列。for (int j = 0; j < 26; j++){for (int i = 0; i < len; i++){// 如果是大写字母或者小写字母 按照a-z顺序放入 对应0-26if ((str[i] - 'a' == j) || (str[i] - 'A' == j)){vec.push_back(str[i]); //将符合规则的字母字符先后写入向量}}}//规则三：非英文字母的其它字符保持原来的位置。for(int i = 0,k = 0;(i < len) && (k < vec.size()); i++){// 如果str当前的值是大写或者小写字母 替换为vec里排好顺序的值if((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')){str[i] = vec[k++];}}return str; //返回按规则排序好后的字符串
}
//主函数
int main()
{string str;while (getline(cin, str)){cout << String_Sorting(str) << endl;}return 0;
}

HJ27 查找兄弟单词

题目描述：

解题思路：
见注释。
解法：

#include <iostream>
#include <stdexcept>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
// 判断两个字符串是否为兄弟单词
bool is_brother(string str1,string str2){if(str1 == str2 || str1.size()!=str2.size())return false;else {// 将str1所有字母出现统计map<char,int> str1_map;for(auto one:str1){if(str1_map.find(one) == str1_map.end()){str1_map[one] = 1;}else{str1_map[one]++;}}// 如果str2发现一个删除一个for(auto one:str2){// 如果有字母str1没有直接退出if(str1_map.find(one) == str1_map.end()){return false;}else{str1_map[one]--;if(str1_map[one] == 0)str1_map.erase(one);}}if (str1_map.size() == 0) {return true;}else {return false;}}
}int main() {// 输入字典中单词的个数nint size;cin>>size;// 再输入n个单词作为字典单词vector<string> str_vec;for (int i=0; i<size; ++i) {string str;cin>>str;str_vec.push_back(str);}// 输入一个单词xstring com_str;cin>>com_str;// 最后后输入一个整数kint index;cin>>index;// 输出字符串 如果是兄弟单词放入容器vector<string> output_vec;for(int i=0;i<str_vec.size();++i){if(is_brother(str_vec[i],com_str)){output_vec.push_back(str_vec[i]);}}// 字典序排序sort(output_vec.begin(), output_vec.end());  cout<<output_vec.size()<<endl;// 如果索引合法输出if(index <= output_vec.size()+1 && output_vec.size() > 0)cout<<output_vec.at(index-1);
}

HJ28 素数伴侣

题目描述：

解题思路：
题解 | #素数伴侣#
将问题分解，首先整理出奇数数组和偶数数组，再查找每个偶数匹配哪个奇数，判断两数和是否是素数，使用find迭代获取匹配结果。
解法：

#include <iostream>
#include <vector>
using namespace std;
// 判断一个数是否是素数
bool isprime(int num){for(int i=2;i*i<=num;++i){  // 判断一个数是否为素数if(num % i == 0)    // 检查有无余数return false;}return true;
}// 参数：待匹配的奇数；偶数数组；是否被使用过了；匹配数组索引是偶数数组size，值为匹配的奇数值
bool find(int num,vector<int>& evens,vector<bool>& used,vector<int>& match){// 遍历每个偶数与奇数比较for(int i=0;i<evens.size();++i){ if(isprime(num+evens[i]) && !used[i]){used[i] = true;// 如果第i个偶数还未配对，或者跟它配对的奇数还有别的选择if(match[i] == 0 || find(match[i],evens,used,match)){//则配对该数match[i] = num;return true;}}}return false;
}int main() {//  输入一个正偶数 nint n;while (cin>>n) {// 输入 n 个整数vector<int> odds,evens,nums(n);for(int i=0;i<n;++i){cin>>nums[i];if(nums[i]%2) // 奇数odds.push_back(nums[i]);else // 偶数evens.push_back(nums[i]);}int count = 0;// 缺少奇数或者偶数无法构成素数if(odds.size() == 0 || evens.size() == 0){cout<<count<<endl;continue;}// 统计每个偶数的配对是哪个奇数vector<int> match(evens.size(),0);  //遍历每个奇数for(int i=0;i<odds.size();++i){//每一轮偶数都没用过vector<bool> used(evens.size(),false);//能否找到配对的偶数，且要最优if(find(odds[i],evens,used,match))count++;}cout<<count<<endl;}return 0;
}
// 64 位输出请用 printf("%lld")

HJ29 字符串加解密

题目描述：

解题思路：
暴力解。
解法：

#include <iostream>
#include <string>using namespace std;int main() {// 加密，解密string str1,str2;cin>>str1>>str2;// 加密for(auto& str:str1){if (str>='a'&&str<'z') {str -=32-1;}else if(str == 'z'){str = 'A';}else if(str>='A'&&str<'Z'){str +=32+1;}else if (str == 'Z') {str = 'a';}else if(str>='0' && str<'9'){str += 1;}else if(str == '9')str = '0';}// 解密for(auto& str:str2){if (str>'a'&&str<='z') {str -=32+1;}else if(str == 'a'){str = 'Z';}else if(str>'A'&&str<='Z'){str +=32-1;}else if (str == 'A') {str = 'z';}else if(str>'0' && str<='9'){str -= 1;}else if(str == '0')str = '9';}cout<<str1<<endl<<str2;
}

HJ30 字符串合并处理

题目描述：

解题思路：
华为机试在线训练_字符串合并处理（字符串、排序）
解法：

#include <iostream>
#include <algorithm>
using namespace std;
//字符串合并处理的函数接口
void Process_String(string str1, string str2, string strOutput)
{//字典法：只考虑 '0' 到 '9' ，'a' 到 'f'，'A' 到 'F' 的字符即可，其余字符不做改变，照原输出char Intput[] = {"0123456789abcdefABCDEF"}; //输入参照字典（数字 + 大小写字母）
//    int Output[] = "084c2a6e195d3b7f5d3b7f"; //输出参照字典（小写）char Output[] = {"084C2A6E195D3B7F5D3B7F"}; //输出参照字典（数字 + 大写字母）strOutput = str1 + str2; //合并两个字符串string odd_str; //下标为奇数的字符组成的字符串，奇数位字符串string even_str; //下标为偶数的字符串组成的字符串，偶数位字符串//根据字符在合并字符串中的次序，按字典序分奇数位、偶数位独立来排，但次序的奇偶性不变，即原来是奇数位，排序后还是奇数位for (int i = 0; i < strOutput.size(); i++){if (i % 2 == 0){odd_str += strOutput[i];}else if (i % 2 == 1){even_str += strOutput[i];}}sort(odd_str.begin(), odd_str.end()); //奇排序sort(even_str.begin(), even_str.end()); //偶排序//将按奇数位、偶数位排序后的字符再填回合并字符串 strOutputint j = 0; //奇数位字符串的下标int k = 0; //偶数位字符串的下标for (int i = 0; i < strOutput.size(); i++){if (i % 2 == 0){strOutput[i] = odd_str[j];j++;}else if (i % 2 == 1){strOutput[i] = even_str[k];k++;}}//对字符（符合字典 Input[]）所代表的 16 进制的数进行 BIT 倒序的操作，并转换为相应的大写字符for (int i = 0; i < strOutput.size(); i++){if ((strOutput[i] >= '0') && (strOutput[i] <= '9')){strOutput[i] = Output[strOutput[i] - '0'];}else if ((strOutput[i] >= 'a') && (strOutput[i] <= 'f')){strOutput[i] = Output[strOutput[i] - 'a' + 10];}else if ((strOutput[i] >= 'A') && (strOutput[i] <= 'F')){strOutput[i] = Output[strOutput[i] - 'A' + 16];}}cout << strOutput << endl;return;
}
//主函数
int main()
{string str1, str2, strOutput;while (cin >> str1 >>str2){Process_String(str1, str2, strOutput);}return 0;
}