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

[TOC]

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

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

相关的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;
}

二、简单级

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);
    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);
    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;
    while(cin >> str){
        int len = str.size();
        // 如果字符串不是8的倍数，在字符串后添加count个'0'
        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<string>
#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、HJ11 数字颠倒

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    string s=to_string(n);// 转换为数字
    reverse(s.begin(),s.end());
    cout<<s<<endl;
    return 0;
}

三、中等级

1、HJ17 坐标移动

#include<iostream>
#include<string>
#include <sstream>// 字符串流
#include <regex> // 正则表达式
using namespace std;

int main(){
    // 读取输入
    string s;
    getline(cin,s);
    // 处理字符串
    pair<int,int> res(0,0);// 二维坐标
    string t;
    stringstream ss(s);//将字符串转换为字符串流
    while(getline(ss,t,';')) {
        if(t.empty()) continue;
        string subStr = t.substr(1);//获取第一个字符之后的子串
        // 如果子串是数字形式
        if(regex_match(subStr,regex("[0-9]{0,}"))) {
            switch(t[0]) {
                case 'A': res.first -= stoi(subStr); break; //左移
                case 'D': res.first += stoi(subStr); break; //右移
                case 'W': res.second += stoi(subStr); break; //上移
                case 'S': res.second -= stoi(subStr); break; //下移
                default: break; //无效
            }          
        }
    }
    cout << res.first << "," << res.second << endl;
    return 0;
}

2、HJ20 密码验证合格程序

#include<iostream>
#include<string>
#include <unordered_set> 
using namespace std;
bool is_password(string s){
    int len = s.size();
    // 要求1： 长度大于8
    if (len <= 8) return false;
    // 要求2：至少包含3种字符
    unordered_set<int> set;
    for (int i = 0; i < len; ++i) {
        // 包含A-Z
        if (s[i] >= 'A' && s[i] <= 'Z')
            set.insert(1);
        // 包含a-z
        else if (s[i] >= 'a' && s[i] <= 'z')
            set.insert(2);
        // 包含0-9
        else if (s[i] >= '0' && s[i] <= '9')
            set.insert(3);
        else
            set.insert(4);
    }
    if (set.size() < 3) return false;
    // 要求3：不能有长度大于2的不含公共元素的子串重复 
    for (int i = 0; i < len - 3; ++i) {
        for (int j = i + 3; j < len - 3; ++j) {
            if (s.substr(i, 3) == s.substr(j, 3)) {
                return false; 
            }
        }
    }
    return true; 
}
int main(){
    // 读取输入
    string s;
    while(cin>>s){
        bool flag = is_password(s);
        if (flag) cout<<"OK";
        else cout<<"NG";
    }
    return 0;
}

3、HJ26 字符串排序

#include<iostream>
#include<string>
#include <vector>
using namespace std;
/*
    思路：首先遍历26轮字符串，每次提取其中的一个字母到数组中
    然后再次遍历字符串，将其中的字母全部替换掉
*/
int main(){
    // 读取输入
    string str;
    getline(cin,str);
    int len = str.size(); //获取字符串长度
    vector <char> vec; //用一个 char 型的向量存储按规则排序后的字符串中的字母字符
    //规则一：英文字母从 A 到 Z 排列，不区分大小写。
    //规则二：同一个英文字母的大小写同时存在时，按照输入顺序排列。
    for (int j = 0; j < 26; j++)
    {
        // 遍历整个数组，每次遍历只取其中的一个英文字母
        for (int i = 0; i < len; i++)
        {
            if ((str[i] - 'a' == j) || (str[i] - 'A' == j))
            {
                vec.push_back(str[i]); //将符合规则的字母字符先后写入向量
            }
        }
    }
    //规则三：非英文字母的其它字符保持原来的位置。
    // 同时遍历字符串和vec
    for(int i = 0,k = 0;(i < len) && (k < vec.size()); i++)
    {
        // 如果当前字符是英文字母，就用vec[k]覆盖，否则跳过
        if((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
        {
            str[i] = vec[k];
            k++;
        }
    }
    cout<<str;
    return 0;
}

4、HJ27 查找兄弟单词

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

bool is_brother(string &s,string &x){
    if(s==x) return false;
    unordered_map<char,int> dict;
    for(char c:s) dict[c]++;
    for(char c:x) dict[c]--;
    for(auto pair:dict){
        if(pair.second!=0) return false;
    }
    return true;
}

int main(){
    // 读取输入
    int n;
    int k;
    cin>>n;
    string s;
    vector<string> arr;
    vector<string> broArr;
    while(n--){
        cin>>s;
        arr.push_back(s);
    }
    string x;
    cin>>x;
    cin>>k;
    // 查找兄弟单词
    for(string str:arr){
        if(!is_brother(str,x))continue;
        broArr.push_back(str);
    }
    // 输出结果
    cout<<broArr.size()<<endl;
    if(k<=broArr.size()){
        sort(broArr.begin(),broArr.end());//排序
        cout<<broArr[k-1]<<endl;
    }
    return 0;
}

5、HJ29 字符串加解密

#include<iostream>
#include<string>
#include <sstream>// 字符串流
#include <regex> // 正则表达式
using namespace std;

char encode(char c){
    if(c=='z')c='A';
    else if(c=='Z')c='a';
    else if(c=='9')c='0';
    else if(c>='a'&&c<'z'){
        c=c-'a'+1+'A';
    }
    else if(c>='A'&&c<'Z'){
        c=c-'A'+1+'a';
    }
    else if(c>='0'&&c<'9'){
        c=c-'0'+1+'0';
    }
    return c;
}
char decode(char c){
    if(c=='A')c='z';
    else if(c=='a')c='Z';
    else if(c=='0')c='9';
    else if(c>'a'&&c<='z'){
        c=c-'a'-1+'A';
    }
    else if(c>'A'&&c<='Z'){
        c=c-'A'-1+'a';
    }
    else if(c>'0'&&c<='9'){
        c=c-'0'-1+'0';
    }
    return c;
}

int main(){
    // 读取输入
    string s1;
    string s2;
    getline(cin,s1);
    getline(cin,s2);
    // 处理字符串
    for(int i=0;i<s1.length();++i) s1[i]=encode(s1[i]);
    for(int i=0;i<s2.length();++i) s2[i]=decode(s2[i]);
    cout<<s1<<endl;
    cout<<s2<<endl;
    return 0;
}

6、HJ36 字符串加密

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

string getKeyTab(string& key,string& tab){
    string m_key;
    // 去除key中的重复字母
    for(int i=0;i<key.size();i++){
        if(m_key.find(key[i])==-1)
            m_key.append(string(1,key[i]));
    }
    // 添加新字母
    char a='a';
    for(int i=m_key.size();m_key.size()<26;i++){
        if(m_key.find(a)==-1){
            m_key.append(string(1,a));
        }
        a++;
    }
    return m_key;
}


int main(){
    // 读取输入
    string key;
    string s;
    getline(cin,key);
    getline(cin,s);
    string tab="abcdefghijklmnopqrst";
    
    // 处理字符串
    string keytab=getKeyTab(key,tab);
    for(int i=0;i<s.size();++i){
        s[i]=keytab[s[i]-'a'];
    }
    cout<<s;
    return 0;
}