「算法刷题」牛客华为题库（二）

[TOC]

​ 华为机试题库共103道题目，其中入门级5道，简单级46道，中等级36道，较难级13道，困难级3道。计划在7天内共完成入门级，简单级，中等级的共计87道题目，则每天应当完成13道左右。计划每天完成：

​ 入门级：1道 简单级：7道 中等级：6道

一、入门级

HJ58 输入n个整数，输出其中最小的k个

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
    // 获取输入
    int n,k;
    cin>>n>>k;
    int temp;
    vector<int> arr;
    while(n--){
        cin>>temp;
        arr.push_back(temp);
    }
    // 返回结果
    sort(arr.begin(),arr.end());
    for(int i=0;i<k;++i){
         cout<<arr[i]<<" ";
    }
    return 0;
}

二、简单级

1、HJ12 字符串反转

#include<iostream>
#include<string>
using namespace std;

int main(){
    // 获取输入
    string s;
    getline(cin,s);
    // 计算结果
    int i=0;
    // 从最后一个字符向前走
    int j=s.length()-1;
    while(i<j){
        swap(s[i++],s[j--]);
    }
    cout<<s;
    return 0;
}

2、HJ13 句子逆序

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void reverseStr(string &str,int start,int end){
    int left=start;
    int right=end;
    while(left<right) swap(str[left++],str[right--]);
}

void split(string &str){
    int left=0;
    int len=str.length();
    while(left<len){
        while(left<len&&str[left]==' ') left++;
        int right=left;
        while(right<len&&str[right]!=' ')right++;
        reverseStr(str,left,right-1);
        left=right;
    }
}

int main(){
    // 获取输入
    string s;
    while(getline(cin, s)){
        split(s);
        reverse(s.begin(), s.end());
        cout <<s;
    }
}

3、HJ106 字符逆序

#include <iostream>
#include <string>
using namespace std;

void reverseStr(string &str,int start,int end){
    int left=start;
    int right=end;
    while(left<right) swap(str[left++],str[right--]);
}


int main(){
    // 获取输入
    string s;
    getline(cin, s);
    reverseStr(s,0,s.length()-1);
    cout<<s;
}

4、HJ14 字符串排序

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


int main(){
    // 获取输入
    string s;
    int k;
    cin>>k;
    vector<string> arr;
    while(k--){
        cin>>s;
        arr.push_back(s);
    }
    sort(arr.begin(),arr.end());
    for(int i=0;i<arr.size();i++){
        cout<<arr[i]<<endl;
    }
    return 0;
}

5、HJ31 单词倒排

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void reverseStr(string &str,int start,int end){
    int left=start;
    int right=end;
    while(left<right) swap(str[left++],str[right--]);
}

bool is_A(char c){
    if(c>='A'&&c<='Z') return true;
    return false;
}
bool is_a(char c){
    if(c>='a'&&c<='z') return true;
    return false;
}

void split(string &str){
   int left=0;
    int len=str.length();
    while(left<len){
        while(left<len&&str[left]==' ') left++;
        int right=left;
        while(right<len&&str[right]!=' ')right++;
        reverseStr(str,left,right-1);
        left=right;
    }
}
// 将所有的非字母字符替换为空格
void update(string &str){
    for(int i=0;i<str.size();i++){
        if(!is_A(str[i])&&!is_a(str[i])) str[i]=' ';
    }
}
int main(){
    // 获取输入
    string s;
    while(getline(cin, s)){
        update(s);
        split(s);
        reverse(s.begin(), s.end());
        cout <<s;
    }
    return 0;
}

6、HJ34 图片整理

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    // 获取输入
    string s;
    getline(cin, s);
    // 排序
    sort(s.begin(), s.end());
    cout <<s;
    return 0;
}

7、HJ40 统计字符

#include <iostream>
#include <string>
using namespace std;

int main(){
    // 获取输入
    string s;
    getline(cin, s);
    // 排序
    int a=0;
    int A=0;
    int space=0;
    int num=0;
    int other=0;
    for(char c:s){
        if(c>='A'&&c<='Z') A++;
        else if(c>='a'&&c<='z') a++;
        else if(c==' ') space++;
        else if(c>='0'&&c<='9') num++;
        else other++;
    }
    cout <<A+a<<endl;
    cout <<space<<endl;
    cout <<num<<endl;
    cout <<other<<endl;
    return 0;
}

三、中等级

1、HJ41 称砝码

#include<iostream>
#include<string>
#include<vector>
#include<set>
using namespace std;
/*
    思路：将所有的砝码按照数量加入一个数组v中
    初始化一个set，其中只有一个0
    遍历数组v中的所有砝码，每取出一个砝码v[i]，就向set插入原先set中的所有元素+v[i]
*/
int main(){
    // 读取输入
    int n;
    cin>>n;
    int a[10];
    for(int i = 0; i < n; i++) cin >> a[i];//记录数量
    int tmp;
    vector<int> v;
    for(int i = 0; i < n; i++)
    {
        cin >> tmp;
        for(int j = 0; j < tmp; j++) v.push_back(a[i]);//将所有的砝码按数量加入
    }
    
    set<int> s;
    s.insert(0);
    for(int i = 0; i < v.size(); i++)
    {
        set<int> t(s);
        // 遍历集合
        for(auto it = t.begin(); it != t.end(); it ++)
        {
            s.insert(*it + v[i]);
        }
    }
    cout << s.size() << endl;
    return 0;
}

2、HJ59 找出字符串中第一个只出现一次的字符

#include<iostream>
#include<string>
#include <unordered_map> 
using namespace std;

int main(){
    // 读取输入
    string s;
    getline(cin,s);
    // 统计所有字符的频率
    unordered_map<char,int> dict;
    for(char c:s){
        dict[c]++;
    }
    // 遍历s，查找第一个只出现一次的字符
    char res='1';
    for(char c:s){
        if(dict[c]==1){
            res=c;
            break;
        }
    }
    if(res=='1') cout<<"-1";
    else cout<<res;
    return 0;
}

3、HJ77 火车进站

#include<bits/stdc++.h>
using namespace std;

// in表示已经处理的火车数组，index表示火车序号，stk表示车站
void dfs(const vector<int>& in, int index, stack<int>& stk,vector<int> &path,vector<vector<int>> &res)
{
    // 当所有火车已经出站
    if (path.size() == in.size()) {
        res.push_back(path);// 添加结果
        return;
    }
    // 当前火车数组中面临的2种选择：当前火车进站或者上一个火车出站
    // 当前火车进站，继续递归处理下一个火车（如果index序号合法）
    if (index < in.size()) {
        stk.push(in[index]);//index的火车进站
        // 处理下一辆火车
        dfs(in, index + 1, stk,path,res);// index+1的火车进站
        // 回溯
        stk.pop();
    }
    
    // 上一个火车出栈，继续递归处理当前火车（如果站中存在火车）
    if (!stk.empty()) {
        // 上一个火车出栈
        int ans=stk.top();
        stk.pop();
        path.push_back(ans);//加入答案
        // 递归处理当前火车
        dfs(in, index, stk,path,res);
        // 回溯
        stk.push(path.back());
        path.pop_back();
    }
}

int main(){
    // 获取输入
    int N;
    cin>>N;
    int tmp;
    vector<int> nums;
    while(N--){
        cin>>tmp;
        nums.push_back(tmp);
    }
    // 深度搜索
    stack<int> stk;
    vector<int> path;
    vector<vector<int>> res;
    dfs(nums, 0, stk,path,res);//nums个火车进出站的结果
    sort(res.begin(), res.end());//按照字典序进行排序
    // 输出结果
    for (auto p : res) {
        for (int a : p) { cout << a << " "; }
        cout << endl;
    }
    return 0;
}

4、HJ33 整数与IP地址间的转换

#include<iostream>
using namespace std;

int main(){
    long long int a,b,c,d;
    long long int num;
    // 格式化输入
    while(scanf("%lld.%lld.%lld.%lld",&a,&b,&c,&d)!=EOF){
        cin>>num;// 获取数字，左移24位，乘
        cout<<(a<<24)+(b<<16)+(c<<8)+d<<endl;//输出IP地址
        //获取A，
        a = num>>24;
        //获取B
        num = num-(a<<24);
        b = num>>16;
        //获取C
        num = num-(b<<16);
        c = num>>8;
         //获取D
        d = num-(c<<8);
        printf("%lld.%lld.%lld.%lld",a,b,c,d);
    }
    return 0;
}

5、HJ48 从单向链表中删除指定值的节点

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;

int main(){
    // 读取输入
    int n;
    int root;
    cin>>n>>root;
    // 创建lst
    list<int> lst;
    lst.push_back(root);
    int a,b;
    list<int>::iterator it;
    n--;
    while(n--){
        cin>>a>>b;//读取每组插入的数据
        it=find(lst.begin(),lst.end(),b);//查找b所在的索引
        it++;
        lst.insert(it,a);//在b索引之后添加a
    }
    int key;
    cin>>key;//读取要删除的节点值
    it=find(lst.begin(),lst.end(),key);//查找key所在的索引
    lst.erase(it);//删除key
    // 输出key
    for(auto it=lst.begin();it!=lst.end();++it){
        cout<<*it<<" ";
    }
    return 0;
}

6、HJ90 合法IP

#include<iostream>
#include<arpa/inet.h>
using namespace std;

int main(){
     string s;
    while(getline(cin,s)){
        struct sockaddr_in sa;
        printf("%s\n",inet_pton(AF_INET, s.c_str(), &(sa.sin_addr))?"YES":"NO");
    }
    return 0;
}