算法|牛客网华为机试11-20C++

牛客网华为机试

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

HJ11 数字颠倒

题目描述：

解题思路：
如果为0直接输出，使用余数和除数自动省略小数点后特性，反向获取字符串并赋值给string。
解法：

#include <iostream>
#include <string>
using namespace std;int main() {int num;cin>>num;if (num == 0) {cout<<'0';return 0;}string output;while (num%10>0) {int one_num = num%10;num /= 10;output+=to_string(one_num);}cout<<output;return 0;
}

HJ12 字符串反转

题目描述：

解题思路：
直接用string索引值反向输出。
解法：

#include <iostream>
using namespace std;int main() {string str;cin>>str;for(int i=str.size()-1;i>=0;--i){cout<<str.at(i);}return 0;
}

HJ13 句子逆序

题目描述：

解题思路：
C++|string字符串操作(切割,是否包含某个子串)
获取一行数据；按空格将单个单词存入vector容器；字符串切割；将最后剩下的单词存入；反向输出；

解法：

#include <iostream>
#include <vector>
using namespace std;int main() {string line;getline(cin,line);  // 获取一行数据vector<string> str_vec; // 按空格将单个单词存入vector容器// 字符串切割string::size_type comper = line.find(' ');while (comper<line.size()) {string a = line.substr(0,comper);str_vec.push_back(a);line = line.substr(comper+1,line.size());comper = line.find(' ');}// 将最后剩下的单词存入str_vec.push_back(line);// 反向输出for(int i=str_vec.size()-1;i>=0;--i){cout<<str_vec.at(i)<<' ';}return 0;
}

HJ14 字符串排序

题目描述：

解题思路：
C++|sort函数
直接使用sort函数排序；
或者使用冒泡法；
解法：
sort

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n;cin>>n;vector<string> str_vec;string str;for(int i=0;i<n;++i){cin>>str;str_vec.push_back(str);}sort(str_vec.begin(),str_vec.end());for (auto out:str_vec) {cout<<out<<endl;}return 0;
}

冒泡法：

#include <any>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n;cin>>n;vector<string> str_vec;string str;for(int i=0;i<n;++i){cin>>str;str_vec.push_back(str);}for(int i=0;i<str_vec.size();++i){for(int j=1;j<str_vec.size();++j){if (str_vec[j-1]>str_vec[j]) {swap(str_vec[j-1],str_vec[j]);}}}for (auto out:str_vec) {cout<<out<<endl;}return 0;
}

HJ15 求int型正整数在内存中存储时1的个数

题目描述：

解题思路：
C++|bitset模板类
直接利用C++的bitset模板类，详见上方链接；
解法：

#include <iostream>
#include <bitset>
using namespace std;int main() {int n;cin>>n;bitset<32> b(n);cout<<b.count();
}

HJ16 购物单

题目描述：

解题思路：
尽力了实在不擅长动态规划问题；
解法：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;int main() {// N总钱数<32000，m可购买的物品数量<60int N,m;cin>>N>>m;// 由于价格是10的整数倍，处理一下以降低空间/时间复杂度N/=10;// 二维表格存储全部初始化为价格0vector<vector<int>> prices(61,vector<int>(3,0));    // 价格// 二维表格存储全部初始化为价值0vector<vector<int>> pricesMultiplyPriority(61,vector<int>(3,0));// 价值 重要程度// 最多可购买m个物品for(int i = 1;i <= m; ++i){int a,b,c;cin>>a>>b>>c; // 价格 价值 附属谁a/=10;b*=a;   // 单个物品价格同样除以10 计算价值if(c == 0){ // 如果是主件prices[i][0] = a;   // 赋值价格pricesMultiplyPriority[i][0] = b; // 赋值价值}else{// c 和 i 为相对的 如果是第一个附属物if (prices[c][1] == 0) {prices[c][1] = a;pricesMultiplyPriority[c][1] = b;}else{ // c 和 i 为相对的 如果是第二个附属物prices[c][2] = a;pricesMultiplyPriority[c][2] = b;} }}// 使用分组背包 m可购买物品数量 N总钱数 全部初始化为0vector<vector<int>> dp(m+1,vector<int>(N+1,0));// 最多可购买m个物品for(int i=1;i<=m;++i){// 钱没花完一直循环for(int j=1;j<=N;++j){// 主件 价钱 价值int a = prices[i][0],b = pricesMultiplyPriority[i][0];// 附件1 价钱 价值int c = prices[i][1],d = pricesMultiplyPriority[i][1];// 附件2 价钱 价值int e = prices[i][2],f = pricesMultiplyPriority[i][2];dp[i][j] = j >= a ? max(dp[i-1][j-a]+b, dp[i-1][j]) : dp[i-1][j];dp[i][j] = j >= (a+c) ? max(dp[i-1][j-a-c]+b+d,dp[i][j]):dp[i][j];dp[i][j] = j >= (a+e) ? max(dp[i-1][j-a-e]+b+f,dp[i][j]):dp[i][j];dp[i][j] = j >= (a+c+e) ? max(dp[i-1][j-a-c-e]+b+d+f,dp[i][j]):dp[i][j];}}cout<<dp[m][N]*10<<endl;
}

HJ17 坐标移动

题目描述：

解题思路：
C++|string字符串操作(切割,是否包含某个子串)

解法：

#include <iostream>
#include <string>
#include <cctype> // for std::isdigit
using namespace std;
// 判断是否为正整数
bool isPositiveInteger(const std::string& str) {if (str.empty() || (!std::isdigit(str[0]) && str[0] != '-')) {return false;}// 遍历字符串中的每个字符for (char c : str) {if (!std::isdigit(c)) {// 如果遇到非数字字符，则不是正整数return false;}}// 如果字符串不为空，并且所有字符都是数字，则可能是正整数// 但是，我们还需要确保它不是负数int startIndex = 0;if (str[0] == '-') {// 如果字符串以负号开头，则不是正整数return false;}// 如果通过了上述所有检查，那么这个字符串是一个正整数return true;
}int main() {string str;cin>>str;int x = 0,y = 0;while (str.size()>0) {// 切割字符串string::size_type comper = str.find(";");string one = str.substr(0, comper);str = str.substr(comper+1, str.size());// 如果小于1肯定不是合法字段if(comper<=1)continue;// 切割方向string direction = one.substr(0,1);// 切割距离one = one.substr(1, one.size());// 如果方向正确if(direction == "A"||direction == "D"||direction == "W"||direction == "S"){// 判断距离是否为正整数if(isPositiveInteger(one)){// 移动if(direction == "A")x -= stoi(one);else if(direction == "D")x += stoi(one);else if(direction == "W")y += stoi(one);else if(direction == "S")y -= stoi(one);}}}cout<<x<<","<<y;
}

HJ18 识别有效的IP地址和掩码并进行分类统计

题目描述：

解题思路：
题解 | #识别有效的IP地址和掩码并进行分类统计#

解法：

#include<iostream>
#include<string>
#include<vector>
using namespace std;int main(){vector<int> arr(7, 0); //分别对应题目的7个类别string s;while(getline(cin, s)){int n = s.length();vector<int> ips; //记录ip地址的数字bool bad = false;bool isnum = false;int num = 0;for(int i = 0; i < n; i++){ //遍历该ip字符串if(s[i] == '.' || s[i] == '~'){ //以.或者~分割if(isnum){if(num > 255){bad = true; //错误ip，数字不能超过255break;}ips.push_back(num);isnum = false;num = 0;}else{arr[5]++; //错误地址bad = true;break;}}else if(s[i] >= '0' && s[i] <= '9'){isnum = true;num = num * 10 + s[i] - '0'; //计算数字}else{arr[5]++;isnum = false; //错误地址，数字部分还有非数字bad = true;break;}}if(isnum)ips.push_back(num); //最后一个数字if(ips[0] == 0 || ips[0] == 127 || bad) continue; //忽略0或者127开头的地址，错误ip已经统计了过了，可以忽略int mask = 4; //查看掩码的数字while(mask < 8 && ips[mask] == 255)mask++;  //找到掩码第一个不全为1的数if(mask == 8){ //掩码全1也是不合法arr[5]++;continue; }else if(ips[mask] == 254 || ips[mask] == 252 || ips[mask] == 248 || ips[mask] == 240 || ips[mask] == 224 || ips[mask] == 191 || ips[mask] == 128)mask++; //各类掩码含1的最后一位while(mask < 8 && ips[mask] == 0)mask++;if(mask != 8){ //掩码后半部分不能有1arr[5]++;continue;}if(ips[0] >= 1 && ips[0] <= 126)arr[0]++; //A类地址else if(ips[0] >= 128 && ips[0] <= 191) arr[1]++; //B类地址else if(ips[0] >= 192 && ips[0] <= 223) arr[2]++; //C类地址else if(ips[0] >= 224 && ips[0] <= 239) arr[3]++; //D类地址else if(ips[0] >= 240 && ips[0] <= 255) arr[4]++; //E类地址if(ips[0] == 10) arr[6]++; //私有地址10开头的else if(ips[0] == 172 && (ips[1] >= 16 && ips[1] <= 31)) arr[6]++; //私有地址172.16.0.0-172.31.255.255else if(ips[0] == 192 && ips[1] == 168) arr[6]++; //私有地址192.168.0.0-192.168.255.255}for(int i = 0; i < 7; i++){ //输出cout << arr[i];if(i != 6)cout << " ";}cout << endl;return 0;
}

HJ19 简单错误记录

题目描述：


解题思路：
用map加deque
解法：

#include <iostream>
#include <string>
#include <deque>
#include <map>
using namespace std;
int main() {string str;map<string, int> result;deque<string> deq;while (getline(cin, str)) {str = str.substr(str.find_last_of('\\') + 1);int pos = str.find_last_of(' ');if ( pos > 16) {str = str.substr(pos - 16);}if (result.find(str) == result.end()) deq.push_back(str);++result[str];if (deq.size() > 8) deq.pop_front();}for (auto x : deq) {cout << x << " " << result[x] << endl;}return 0;
}

HJ20 密码验证合格程序

题目描述：

解题思路：
HJ20.密码验证合格程序
解法：

#include <iostream>
#include <string>
#include <unordered_set>const std::string OK = "OK";
const std::string NG = "NG";bool check1(const std::string& s) {return s.length() > 8;
}bool check2(const std::string& s) {int type[4] = {0, 0, 0, 0};for (auto& i : s) {if (i == ' ' || i == '\n') {return false;}if (i >= 'A' && i <= 'Z') {type[0] = 1;}else if (i >= 'a' && i <= 'z') {type[1] = 1;}else if (i >= '0' && i <= '9') {type[2] = 1;}else {type[3] = 1;}}if (type[0] + type[1] + type[2] + type[3] < 3) {return false;}return true;
}bool check3(const std::string& s) {std::unordered_set<std::string> sets;std::string tmp;for (int i = 0; i < s.length() - 2; ++i) {tmp = s.substr(i, 3);if (sets.find(tmp) == sets.end()) {sets.insert(tmp);}else {return false;}}return true;
}int main() {std::string in;while (getline(std::cin, in)) {if (check1(in) && check2(in) && check3(in)) {std::cout << OK << '\n';}else {std::cout << NG << '\n';}}return 0;
}