当前位置： 首页 > article >正文

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

article 2024/10/27 20:28:20

牛客网华为机试

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

文章目录

  • HJ11 数字颠倒
  • HJ12 字符串反转
  • HJ13 句子逆序
  • HJ14 字符串排序
  • HJ15 求int型正整数在内存中存储时1的个数
  • HJ16 购物单
  • HJ17 坐标移动
  • HJ18 识别有效的IP地址和掩码并进行分类统计
  • HJ19 简单错误记录
  • HJ20 密码验证合格程序

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可购买的物品数量<60
    int N,m;
    cin>>N>>m;
    // 由于价格是10的整数倍，处理一下以降低空间/时间复杂度
    N/=10;
    // 二维表格存储全部初始化为价格0
    vector<vector<int>> prices(61,vector<int>(3,0));    // 价格
    // 二维表格存储全部初始化为价值0
    vector<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总钱数 全部初始化为0
    vector<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，数字不能超过255
                        break;
                    }
                    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){ //掩码后半部分不能有1
            arr[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.255
        else 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;
}

http://www.kler.cn/news/367734.html

相关文章：

  • unity项目导出安卓工程后，在AndroidStudio打包报错：unityLibrary:BuildIl2CppTask‘.
  • 如何在 Linux 中对 USB 驱动器进行分区
  • 以 6502 为例讲讲怎么阅读 CPU 电路图
  • 算法与竞赛(第15章) - 矩阵高级运算
  • 图层之间的加减法
  • 比例数据可视化（Python实现板块层级图绘制）——Instacart Market Basket Analysis
  • 学点高数-数学上的集合①-集合的基本概念
  • 学成在线实战
  • 机器学习 - 树结构1 - 随机森林
  • Spring Cloud --- Sentinel 规则持久化
  • YOLO11改进 | 卷积模块 | 卷积模块替换为选择性内核SKConv【附完整代码一键运行】
  • 设计模式概览
  • 手机拍证件照，换正装有领衣服及底色的方法
  • jenkins配置邮件通知
  • Flutter控制台提示setState() or markNeedsBuild() called during build错误
  • Linux中DNS搭建
  • GenAI 生态系统现状：不止大语言模型和向量数据库
  • Day 8 UE5c++
  • React实现购物车功能
  • 川渝地区软件工程考研择校分析
  • Pulsar mq 设置延迟消息模式 pulsar mq 发送延迟消息 pulsar如何发送消费延时消息
  • Django+MySQL接口开发完全指南
  • 深入解析 MySQL 数据库：数据库备份机制
  • list补充
  • ESP32C3的 USB 串行/JTAG 控制器
  • AListFlutter（手机alist）——一键安装，可在手机/电视上运行并挂载各个网盘