算法|牛客网华为机试31-40C++

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

HJ31 单词倒排

题目描述：

解题思路：
for循环遍历一次，从后往前，如果是字符组成单词等遇到空格或者非字母输出。
解法：

#include <iostream>
#include <string>
using namespace std;int main() {string str;getline(cin, str);string s = "";for(int i = str.size()-1;i>=0;--i){ // 如果是字母组单词if((str.at(i)>='a' && str.at(i) <= 'z')|| (str.at(i)>='A' && str.at(i) <= 'Z'))s = str.at(i)+s;// 如果不是字母加空格else{cout<<s<<" ";s = "";}}// 输出最后一个单词cout<<s<<" ";return 0;
}

HJ32 密码截取

题目描述：

解题思路：
题解 | #密码截取#
解法：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;int main() {string s;while (cin>>s) {int n = s.length();vector<vector<bool>> dp(n,vector<bool>(n,false)); // dp[j][i]=1表示从j到i是回文子串int maxlen = 1; // 初始为1for(int i=0;i<n;++i){for(int j=0;j<=i;++j){if(i == j) // 奇数长度子串dp[j][i] = true;else if (i-j == 1)  // 偶数长度子串dp[j][i] = (s[i] == s[j]);elsedp[j][i] = (s[i] == s[j] && dp[j+1][i-1]);  // 这两个字符相等 同事中间缩也要相等if(dp[j][i]&& i-j+1>maxlen) // 取最大maxlen = i-j+1;}}cout<<maxlen<<endl;}return 0;
}

HJ33 整数与IP地址间的转换

题目描述：

解题思路：
使用位运算符。
解法：

#include <iostream>
using namespace std;int main()
{long long int a,b,c,d;long long int num;// 使用scanf函数从标准输入读取四个整数，这些整数由点.分隔，代表IPv4地址的四个部分。// EOF是文件结束标志，当输入结束时返回EOF，循环结束。while(scanf("%lld.%lld.%lld.%lld",&a,&b,&c,&d)!=EOF){cin>>num;// 将a左移24位，b左移16位，c左移8位，然后将它们与d相加，得到IPv4地址的整数形式，并输出。// <<是位左移运算符，将一个数的二进制表示向左移动指定位数，右边补0。// 例如，a<<24将a的二进制表示向左移动24位，相当于将a乘以2^24。cout<<(a<<24)+(b<<16)+(c<<8)+d<<endl;// 将整数num右移24位，得到最左边的8位，即IPv4地址的第一个部分，并赋值给a。// >>是位右移运算符，将一个数的二进制表示向右移动指定位数，左边补符号位（正数补0，负数补1）。// 这里由于num是无符号整数，所以左边补0。a = num>>24;// 从num中减去a左移24位的结果，移除num中最高的8位，更新num的值。num = num-(a<<24);// 将更新后的num右移16位，得到接下来的8位，即IPv4地址的第二个部分，并赋值给b。b = num>>16;// 从num中减去b左移16位的结果，移除num中接下来的8位，更新num的值。num = num-(b<<16);// 将更新后的num右移8位，得到接下来的8位，即IPv4地址的第三个部分，并赋值给c。c = num>>8;// 从num中减去c左移8位的结果，移除num中接下来的8位，得到最低的8位，// 即IPv4地址的第四个部分，并赋值给d。d = num-(c<<8);// 输出转换后的IPv4地址。cout<<a<<"."<<b<<"."<<c<<"."<<d<<endl;}
}

HJ34 图片整理

题目描述：

解题思路：
C++|sort函数
直接用sort函数就是按着ASCII码从小到大排序的。

解法：

#include <algorithm>
#include <iostream>
using namespace std;int main() {string str;cin>>str;sort(str.begin(), str.end());cout<<str;return 0;
}

HJ35 蛇形矩阵

题目描述：

解题思路：
找每行每列的相加差1的数学规律，再每行输出。
解法：

#include<iostream>
#include<vector>
using namespace std;int main(){int n; while(cin >> n){//起始元素为1int k = 1;//遍历每一行for(int i = 1; i <= n; i++){ //输出每行首cout << k << " ";  int temp = k;//遍历本行的数 从加2开始每个数相加多1for(int j = i + 1; j <= n; j++){ //每个数相差为jtemp += j; cout << temp << " ";}cout << endl;//下一行的首为这行首加上这行行号每行行首也是从1开始多加1个k += i; }}return 0;
}

HJ36 字符串加密

题目描述：

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

#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;int main(){string key, words;while(cin >> key >> words){vector<char> v;for(int i = 0; i < key.length(); i++){ //遍历字符串keykey[i] = toupper(key[i]); //全部转大写auto it = find(v.begin(), v.end(), key[i]); //查找是否加入过了if(it == v.end()) //非重复加入v.push_back(key[i]);}for(char c = 'A'; c <= 'Z'; c++){ //从A遍历到Zauto it = find(v.begin(), v.end(), c); //没有出现过if(it == v.end()) v.push_back(c); //才加入}string output = "";for(int i = 0; i < words.length(); i++){ //遍历要加密的字符串if(islower(words[i])) //遇到小写字符output += v[words[i] - 'a'] + 32; //需要在转出来的大写字母基础上加32elseoutput += v[words[i] - 'A']; //大写字母直接替换}cout << output << endl;}return 0;
}

HJ37 统计每个月兔子的总数

题目描述：

解题思路：
C++|斐波那契数列
解法：

#include <iostream>
#include <vector>
using namespace std;int main() {int num;cin >> num;if (num < 3) {cout << 1;return 0;}// 初始化数组，存储每个月的兔子对数vector<int> rabbits(num + 1, 0);rabbits[1] = 1; // 第一个月有1对兔子rabbits[2] = 1; // 第二个月有1对兔子// 计算每个月的兔子对数for (int i = 3; i <= num; ++i) {// 每个月的兔子对数是前两个月兔子对数的和rabbits[i] = rabbits[i - 1] + rabbits[i - 2];}cout << rabbits[num];return 0;
}

HJ38 求小球落地5次后所经历的路程和第5次反弹的高度

题目描述：

解题思路：
计算第5次落地后球经过的距离，除了第一次只经过一次，所以距离最后在减去初始长度，高度每次减去一半。
解法：

#include <iostream>
using namespace std;int main() {double height;cin>>height;double lenght = 0,h = height;for (int i=0; i<5; ++i) {// 回弹上下路径一样lenght += h*2;h =  h/2;}// 减去第一次落地的*2lenght -= height;cout<<lenght<<endl<<h;return 0;
}

HJ39 判断两个IP是否属于同一子网

题目描述：

解题思路：
题解 | #判断两个IP是否属于同一子网#
解法：

#include <iostream>
#include <vector>using namespace std;int main()
{// 子网掩码vector<int> mask(4,0);// ip地址vector<int> ip1(4,0);vector<int> ip2(4,0);char c;while (cin>>mask[0]>>c>>mask[1]>>c>>mask[2]>>c>>mask[3])//输入掩码{int flag = -1;//结果cin>>ip1[0]>>c>>ip1[1]>>c>>ip1[2]>>c>>ip1[3];//第一个ip地址cin>>ip2[0]>>c>>ip2[1]>>c>>ip2[2]>>c>>ip2[3];//第二个ip地址for(int i=0;i<4;i++)//两个ip地址和掩码每一段都要在0-255之间{if(mask[i]<0 || mask[i]>255 || ip1[i]<0 || ip1[i]>255 ||ip2[i]<0 || ip2[i]>255){flag = 1;//格式非法break;}}for(int i=0;i<3;i++)//掩码的网络号全为1，主机号全为0{if(mask[i]<255 && mask[i+1]>0){flag = 1;break;}}if(flag==1)//格式非法，输出1{cout<<flag<<endl;}else{for(int i=0;i<4;i++){if((mask[i]&ip1[i])!=(mask[i]&ip2[i]))//两个ip地址和掩码做AND操作{flag = 2;break;}else{//AND操作结果不相同flag = 0;}}cout<<flag<<endl;}}return 0;
}

HJ40 统计字符

题目描述：

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

#include <iostream>
using namespace std;int main() {string str;getline(cin,str);int english_char = 0,space_char = 0,num = 0,others = 0;for(auto c:str){if(c>='a'&&c<='z'){english_char++;}else if(c == ' '){space_char++;}else if(c>='0'&&c<='9'){num++;}else{others++;}}cout<<english_char<<endl<<space_char<<endl<<num<<endl<<others<<endl;return 0;
}