牛客网华为机试
上篇：算法|牛客网华为机试21-30C++
文章目录
- HJ31 单词倒排
- HJ32 密码截取
- HJ33 整数与IP地址间的转换
- HJ34 图片整理
- HJ35 蛇形矩阵
- HJ36 字符串加密
- HJ37 统计每个月兔子的总数
- HJ38 求小球落地5次后所经历的路程和第5次反弹的高度
- HJ39 判断两个IP是否属于同一子网
- HJ40 统计字符
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; // 初始为1
for(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]);
else
dp[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){
//起始元素为1
int k = 1;
//遍历每一行
for(int i = 1; i <= n; i++){
//输出每行首
cout << k << " ";
int temp = k;
//遍历本行的数 从加2开始每个数相加多1
for(int j = i + 1; j <= n; j++){
//每个数相差为j
temp += 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++){ //遍历字符串key
key[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遍历到Z
auto 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; //需要在转出来的大写字母基础上加32
else
output += 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;
}
// 减去第一次落地的*2
lenght -= 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;
}
