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

[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());
//计算x的y次幂
pow(x,y);
//将数字常量转换为字符串
#include<string>
int n;
cin>>n;
string s=to_string(n);
//字符串的长度
s.length();
//将字符串逆序
#include<algorithm>
reverse(s.begin(),s.end());//reverse函数的参数应该是迭代器？
//获取字符串的子串
s.substr(3,5);//表示索引3开始的5个字符
//sort()函数
//sort默认按照字典序排序,即按照ASCII的顺序排序：数字，大写英文字母，小写英文字母
#include <algorithm>//sort位于这个头文件中
#include<vector>
vector<int> arr;
sort(arr.begin(),arr.end());//默认做升序排序

数字字符与数字的转换的两种方法：

第一种：

​ 用数字字符出减去’0’。例如：’1’-‘0’=1　　(它俩是用ASCII码相减的。即49-48=1)

1+’0’=’1’

第二种：

​ 用数字字符出减去48。（48是‘0’的ASCII码）例如：’1’-48=1。

ASCII码的大小规则

常见ASCII码的大小规则：09<AZ<a~z。

0:48 A:65 a:97

1）数字比字母要小。如 “7”<“F”；

2）数字0比数字9要小，并按0到9顺序递增。如 “3”<“8” ；

3）字母A比字母Z要小，并按A到Z顺序递增。如“A”<“Z” ；

4）同个字母的大写字母比小写字母要小32。如“A”<“a” 。

几个常见字母的ASCII码大小： “A”为65；“a”为97；“0”为 48 [4] 。

在英语中，用128个符号编码便可以表示所有，但是用来表示其他语言，128个符号是不够的。

字符串流

#include <sstream>// 字符串流
string s;
stringstream ss(s);//将字符串转换为字符串流

字符串流是以内存中用户定义的字符串或字符数组为输入输出对象，也称为内存流 .

c++正则表达式

regex_match: match是全文匹配，即要求整个字符串符合匹配规则。

将逆序字符串的函数

1、直接调用函数

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

2、编写逆序函数

#include<string>
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;
    }
}

判断字符是否为大小写英文字母

1、直接使用现有的函数

#include<string>
string s;
isalpha(s);//返回值为false或true

2、

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

动态数组：添加

vector arr;

arr.push_back();

c++的输出格式

1.转换说明符

%f 浮点数(包括float和double)

​ %c 字符
%d 有符号十进制整数

%i 有符号十进制整数(与%d相同)
%u 无符号十进制整数

%s 字符串

2、格式字符： 用以指定输出项的数据类型和输出格式。

f格式：

%f：不指定宽度，整数部分全部输出并输出6位小数。
%m.nf：输出共占m列，其中有n位小数，如数值宽度小于m左端补空格。
%-m.nf：输出共占n列，其中有n位小数，如数值宽度小于m右端补空格。

sort函数

//sort默认按照字典序排序,即按照ASCII的顺序排序：数字，大写英文字母，小写英文字母
#include <algorithm>//sort位于这个头文件中
#include<vector>
vector<int> arr;
sort(arr.begin(),arr.end());//默认做升序排序

//降序排序
sort(arr.begin(),arr.end(),cmp);
bool cmp(int a,int b){
    return a>b;
}

双指针法删除数组中出现次数最少的元素

( 若出现次数最少的字符有多个，则把出现次数最少的字符都删除。 )

string s;
int left=0;
int right=0;
int n=s.length();
while(right<n){
   if(dict[s[right]]==min_q){//min_q是出现的最小次数
       right++;
   }
   else{
      s[left++]=s[right++]; 
   }
}
cout<<s.substr(0,left);

链表结点的定义

struct ListNode{
    int m_nKey;
    ListNode* m_pNext;
    ListNode(int val){
        m_nKey=val;
        m_pNext=NULL;
    }
};

创建链表

ListNode *myNode=new ListNode(0);
        ListNode *p=myNode;//遍历指针
        int temp=0;
        //创建链表
        while(n--){//n为链表节点个数

            cin>>temp;
            ListNode *newNode=new ListNode(temp);
            p->next=newNode;
            p=p->next;
        }

找链表中倒数第k个元素

int k;
//头结点
ListNode *myCode=new ListNode(0);、
//left，right都指向第一个节点（头节点的下一个结点）
ListNode *left=myCode->m_pNext;
ListNode *right=myCode->m_pNext;
//right先走k步
while(k--){
    right=right->m_pNext;
}
//left和right一起走，直到right指向NULL
while(right){
    left=left->m_pNext;
    right=right->m_pNexst;
}
cout<<left->m_nKey<<endl;

判断字符是否大小写字母、数字等的库函数

1. isupper()判断一个字符是否是大写字母

2. isalpha()判断一个字符是否是字母

3. isblank()判断一个字符是否是空白符

4. isdigit()判断一个字符是否是十进制数字

5. islower()判断一个字符是否是小写字母

6. isspace()判断一个字符是否是空白符

7. tolower()将大写字母转换为小写字母

8. toupper()将小写字母转换为大写字母

十进制转二进制

输入描述：

输入一个整数

输出描述：

计算整数二进制中1的个数

输入：

5

复制

输出：

2

复制

说明：

5的二进制表示是101，有2个1   

#include<iostream>
using namespace std;

int main(void){
    int n;
    while(cin>>n){
        int  m=0;
        while(n){
            m+=n%2;
            n=n/2;
        }
        cout<<m<<endl;
    }
    
    
    return 0;
}

unordered_map查找某个元素是否存在的函数

unordered_map<string,int> mp;
string s;
mp.count(s)//返回值为0：不存在；1：存在。
mp.find(s)==mp.end();//mp中不存在s

按要求对哈希表排序

输入一个只包含小写英文字母和数字的字符串，按照不同字符统计个数由多到少输出统计结果，如果统计的个数相同，则按照ASCII码由小到大排序输出。

方法一：使用自定义sort

#include<bits/stdc++.h>
using namespace std;
//函数参数加const，可以防止参数被改变
//函数参数加&，效率更高
bool cmp(const pair<char,int>& a,const pair<char,int>& b){
    if(a.second!=b.second){
        return a.second>b.second;
    }else{
        return a.first<b.first;
    }
}

int main(void){
    string s;
    getline(cin,s);
    unordered_map<char,int> mp;// k-v
    for(int i=0;i<s.size();i++){
        mp[s[i]]++;
    }
    vector<pair<char,int>> arr;
    for(auto iter=mp.begin();iter!=mp.end();++iter){
        arr.push_back(make_pair(iter->first, iter->second));
    }
    sort(arr.begin(),arr.end(),cmp);// 从大到小
    for(auto p:arr){
        cout<<p.first;
    }
    return 0;
}

方法二：优先级队列和仿函数（其实是个类）

仿函数的operator()是函数名。

priority_queue<pair<char,int>,vector<pair<char,int>>,mycomp> que;的<>里的第一个是队列元素类型，第二个是把队列元素放到指定容器中进行排序。

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

class mycomp{
public:
    bool operator()(const pair<char,int>& a,const pair<char,int>& b){
        if(a.second==b.second){
            return a.first>b.first;
        }
        else{
            return a.second<b.second;
        }
    }
};

int main(){
    // 获取输入
    string s;
    unordered_map<char,int> dict;
    priority_queue<pair<char,int>,vector<pair<char,int>>,mycomp> que;
    while(getline(cin, s)){
        for(char c:s) dict[c]++;//统计长字符串中的所有字符频率
        // 遍历
        for(auto p:dict){
            que.push(p);
        }
        // 输出
        while(!que.empty()){
            auto p=que.top();
            que.pop();
            cout<<p.first;
        }
        cout<<endl;
    }
}

十进制数字转为二进制字符串

int n;
    cin>>n;
    string s;
    //转为二进制
    while(n){
        s=to_string(n%2)+s;
        n/=2;
    }

合并两个有序数组

将两个整型数组按照升序合并，并且过滤掉重复数组元素。

输出时相邻两数之间没有空格。

//合并两个有序数组
   string res;
   int i=0,j=0;
   unordered_set<int> set;//哈希集合，用来去重
   while(i<s1.size()&&j<s2.size()){
       if(s1[i]<=s2[j]){
           if(!set.count(s1[i])){//不重复的才添加
               set.insert(s1[i]);
               res+=to_string(s1[i]);
           }
           i++;
       }
       else if(s1[i]>s2[j]){//不重复的才添加
           if(!set.count(s2[j])){
               set.insert(s2[j]);
               res+=to_string(s2[j]);
           }
           j++;
       }
   }
   //数组s1没有比较完
   while(i<s1.size()){
       if(!set.count(s1[i])){
           set.insert(s1[i]);
           res+=to_string(s1[i]);
       }
       i++;
   }
   //数组s2没有比较完
   while(j<s2.size()){
       if(!set.count(s2[j])){
           set.insert(s2[j]);
           res+=to_string(s2[j]);
       }
       j++;
   }
   cout<<res;

判断是否为回文子串

//判断是否是回文子串
bool is_true(string &s){
    int left=0;
    int right=s.size()-1;
    while(left<=right){
        if(s[left++]!=s[right--])return false;
    }
    return true;
}

遍历所有的子串

//定义动态数组
    int len=s.size();
    for(int i=0;i<len;i++){
        for(int j=1;j<len-i+1;j++){
            string str=s.substr(i,j);
            //对字串进行处理
        }
    }