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

[TOC]

​ 华为机试题库共103道题目，其中入门级5道，简单级46道，中等级36道，较难级13道，困难级3道。

相关的API

//将一个字符串中的字符全部转换为小写：
for (int i = 0; i < str.length(); i++)
{
    if ('A' <= str[i] && str[i] <= 'Z')
    	str[i] += 32;
}
// 将一个字符转换为小写：
char c=tolower(ch);
// 在字符串末尾添加n个字符
str.append(n, '0');
// 根据索引获取字符串的子串
int len = str.size();
for (int i = 0; i < len; i += 8){
    cout << str.substr(i, 8) << endl;
}
// 分割字符串
char s[]= "Golden~Global_View,disk*desk";//待分割的字符数组
const char *d = "~ ,*";// 分割字符集合
char *p;
p = strtok(s,d);//s必须是char[] 类型
while(p)
{
    printf("%s\n",p);
    p=strtok(NULL,d);
}

// 将n进制的字符串转换为十进制
#include <string>
int stoi（str，x，n）//将 n 进制的str从索引x开始转化为十进制的整数
    
// 字符串转换为char []
char ch[20];
string s="123456";
strcpy(ch,s.c_str());

一、入门级

HJ46 截取字符串

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

int main(){
    // 获取输入
    string s;
    getline(cin,s);
    int k;
    cin>> k;
    // 返回结果
    cout<<s.substr(0,k);
    return 0;
}

HJ 58 输入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;
}

HJ101 输入整型数组和排序标识，对其元素按照升序或降序进行排序

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

bool cmp(int a,int b){
    return a>b;
}
int main(){
    int n;
    cin>>n;
    vector<int> arr;
    int i;
    while(n--){
        cin>>i;
        arr.push_back(i);
    }
    int b;
    cin>>b;
    if(b==0){
        sort(arr.begin(),arr.end());
    }
    else if(b==1){
        sort(arr.begin(),arr.end(),cmp);
    }
    
    for(int i=0;i<arr.size();i++){
        cout<<arr[i]<<' ';
    }
    return 0;
}

二、简单级

1、HJ1 字符串最后一个单词的长度

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

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

2、HJ2 计算某字符出现次数

题目要求不区分字母大小写

方法一：将目标字符和字符串中的每个字符都转换为小写后遍历

#include <iostream>
#include <string>
 
using namespace std;
int main(){
    // 获取输入
    string s;
    getline(cin, s);//不用cin，因为cin默认截断符是空格，tab，enter等空白字符。有个用例的字符串中包含空格
    char c;
    cin>>c;
    // 计算结果
 	c=tolower(c);
    int res = 0;
    for (char i : s) {
        if (tolower(i) == c) {
            ++res;
        }
    }
    cout <<res;
}

方法二：转换为小写加入哈希表

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

int main()
{
    // 获取输入
    string s;
    getline(cin, s);
    char c;
    cin>>c;
    // 计算结果
 	c=tolower(c);
    //在声明诸如字符数或者数组索引这样的长度变量时用size_t 是好的做法。size_t 类型表示C/C++中任何对象所能达到的最大长度，它是无符号整数。
    unordered_map<char, size_t> dict;
    for (auto i : s) {
        ++dict[tolower(i)];
    }
    cout << dict[tolower(c)] << endl;
}

3、HJ4 字符串分隔

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

int main(){
    string str;
    getline(cin,str);
    
    int len=str.size();
    
    if(len%8!=0){
        int count=8-len%8;
        str.append(count,'0');
    }
    //此时字符串长度是8的倍数，每8个字符输出即可
    int newLen=str.size();
    for(int i=0;i<newLen;i+=8){
        cout<<str.substr(i,8)<<endl;
    }
    return 0;
}

4、HJ5 进制转换

#include<iostream>
#include<math.h>
#include<string>
using namespace std;

int main(){
    string s; //0xAA
    cin>>s;
    // 方法一：cout<<stoi(s,0,16)<<endl;
    int n=s.size();
    int res=0;
    // 从后向前遍历，0x不用转换，忽略即可
    for(int i=n-1;i>1;i--)
    {
        int cur=0;
        // 如果当前数是0-9，则res+=n^(n-i-1)
        if(s[i]>='0'&&s[i]<='9'){
            cur=s[i]-'0';
        }
        // 如果当前数是A-F,则res+=n^(n-i-1)
        if(s[i]>='A'&&s[i]<='F'){
            cur=s[i]-'A'+10;
        }
        res+=cur*pow(16,n-i-1);
    }
    cout<<res<<endl;
    return 0;
}

5、HJ10 字符个数统计

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
int main(){
    string s;
    cin>>s;
    unordered_map<int,int> dict;
    for(char c:s){
        dict[c]++;
    }
    cout<<dict.size()<<endl;
    return 0;
}

6、HJ8 合并表记录

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

int main(){
    int n;
    cin>>n;
    map<int,int>dict;
    while(n--){
        int key,value;
        cin>>key>>value;
        dict[key]+=value;
    }
    for(auto kv:dict){
        cout<<kv.first<<" "<<kv.second<<endl;
    }
    return 0;
}

7、HJ12 字符串反转

直接用函数进行字符串反转

#include<algorithm>
reverse(s.begin(),s.end());

考察自己写字符串反转

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

int main(){
    string s;
    getline(cin,s);
    
    int i=0,j=s.length()-1;
    while(i<j){
        swap(s[i],s[j]);
        i++;
        j--;
    }
    cout<<s;
    return 0;
}

8、 HJ13 句子逆序

#include<iostream>
#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;
    }
    return 0;
}

9、 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;
    return 0;
}

10、HJ14 字符串排序

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

int main(){
    string s;
    int k;
    cin>>k;
    vector<string> arr;
    while(k--){
        cin>>s;
        arr.push_back(s);
    }
    //按照字典序排列的字符串。sort需要头文件#include<algorithm>
    sort(arr.begin(),arr.end());
    for(int i=0;i<arr.size();i++){
        cout<<arr[i]<<endl;
    }
    return 0;
}

11、 HJ31 单词倒排

#include<iostream>
#include<algorithm>
#include<vector>
#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--]);
    }
}

void split(string &str,vector<string> &arr){
    int left=0;
    int len=str.length();
    while(left<len){
        // left找到了第一个英文字符
        while(str[left]==' '&&left<len)left++;
        int right=left;
        // right找到单词后的第一个空格
        while(str[right]!=' '&&right<len)right++;
        //[left,right-1]
        arr.push_back(str.substr(left,right-left));
        //reverseStr(str,left,right-1);
        left=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 update(string &str){
    for(int i=0;i<str.size();i++){
        if(!isalpha(str[i])) str[i]=' ';
        //if(!is_A(str[i])&&!is_a(str[i]))str[i]=' ';
    }
}
int main(){
    // 获取输入
    string s;
    getline(cin,s);
    // 将所有的间隔符统一替换为空格
    update(s);
    // 分割
    vector<string> arr;
    split(s,arr);
    reverse(arr.begin(),arr.end());
    for(string s:arr){
        cout<<s<<" ";
    }
    return 0;
}

12、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;
}

13、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;
}

14、HJ23 删除字符串中出现次数最少的字符

#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]++;
    }
    int min_q=20;
    for(auto it:dict){
        if(it.second<min_q) min_q=it.second;
    }
    // 从最后一个字符向前走
    int left=0;
    int right=0;
    int n=s.length();
    while(right<n){
        if(dict[s[right]]==min_q){
            right++;
        }
        else{
           s[left++]=s[right++]; 
        }
    }
    cout<<s.substr(0,left);
    return 0;
}

15、HJ81 字符串字符匹配

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

int main(){
    // 获取输入
    string s1;
    string s2;
    unordered_map<char,int> dict;
    while(getline(cin, s1)){
        getline(cin, s2);
        bool flag=true;
        for(char c:s2) dict[c]++;//统计长字符串中的所有字符频率
        // 遍历短字符串
        for(char c:s1){
            // 如果有一个字符在字典中不存在则结果为false
            if(dict.count(c)==0){
                flag=false;
                break;
            }
        }
        if(flag) cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }
}

16、 HJ56 完全数计算

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。

它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。

例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28

#include<iostream>
using namespace std;

int main(void){
    int n;
    cin>>n;
    int count=0;
    for(int i=6;i<=n;i++){
        int temp=0;
        for(int j=1;j<i;j++){//j<n，因为求和时不算这个数的自身
            if(i%j==0)
                temp+=j;
        }
        if(temp==i){
            count++;
        }
    }
    cout<<count<<endl;
    return 0;
}

17、HJ99 自守数

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int ans=0;
        for(int i=1;i<=n;i++){
            if(i%10==1||i%10==5||i%10==6){ //找到可能成为自守数的数
                int temp1=i, temp2=i*i;
                while(temp1){//验证后几位
                    if(temp2%10!=temp1%10) break;
                    temp1/=10;
                    temp2/=10;
                }
                if(temp1==0) ans++;//保证是满足条件才跳出的循环
            }
        }
        cout<<ans+1<<endl;//带上0
    }
    return 0;
}

18、HJ6 质数因子

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long m;
    while(cin>>m)
    {
        for(long i=2;i*i<=m;i++)
        {
            while(m%i==0)
            {
                cout<<i<<" ";
                m/=i;
            }
        }
        if(m>=2) cout<<m<<" ";//如果m=1,则while循环中刚好被质数分解完，如果大于1，说明没有被分解完，m就是那最后一个质数
                              //同时，这句也可以应对输入为质数的特殊情况
        cout<<endl;
    }
}

19 HJ60 查找组成一个偶数最接近的两个素数

质数(也叫素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

查找组成偶数的最近两个素数

1.从偶数的一半开始查找；
2.判断两个数是否为素数；
3.如果是素数，则即为所求。

#include <iostream>
using namespace std;

bool isPrime(int n)
{
    int i=0;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0) return false;
    }
    return true;
}

int main()
{
    int n;
    while(cin>>n)
    {
        int left=n/2;
        int right=n/2;
        while(left>=2)
        {
            if(isPrime(left)&&isPrime(right))
            {
                cout<<left<<endl;
                cout<<right<<endl;
                break;
            }
            else
            {
                left--;
                right++;
            }
        }
    }
    return 0;
}

20、 HJ94 记票统计

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

int main(void){
    int n;
    cin>>n;
    string s;
    vector<string>people;
    unordered_map<string,int> mp;
    for(int i=0;i<n;i++){
        cin>>s;
        people.push_back(s);
        mp[s]=0; 
    }
    int n2;
    cin>>n2;
    int Invalid=0;
    for(int i=0;i<n2;i++){
        cin>>s;
        if(mp.count(s)!=0){
            mp[s]++;
        }
        else{
            Invalid++;
        }
    }
    for(int i=0;i<n;i++){
        cout<<people[i]<<" : "<<mp[people[i]]<<endl;
    }
    cout<<"Invalid"<<" : "<<Invalid<<endl;
    return 0;
}