华为机试题刷题总结

大家好，欢迎来到IT知识分享网。

总体来说，最近一年的题，难易程度简单偏中等。

题总共分为五大类，分别是字符，排序，查找，算法题，其中二叉树单独拿出来考的

难易程度：百分之80属于简单题的范畴，剩下的属于运气题——————————。

一.字符串

经常考的题有：（字符串比较，字符串拼接，字符串排序，是否为公共子串，字符串翻转，字符串重排；）

字符串类的题就直接用map函数就行，剩下的百分之2.5的题用for循环输出结果就可以；

二.排序类

经常考的题有：（K个字母组合，问第几个字符或者数字，小朋友按照身高体重排序；）

三.查找类

经常考的题有：（查找中位数，小朋友查找身高体重；）

四.算法题（BFS，DFS；）

经常考的题有：（对角线上人数，迷宫，最优规划，背包问题；）

上面是几类高频的考试内容，以下是考试常用的几个函数 **

1. getline 函数，此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。

当 cin 读取数据时，一旦它接触到第一个非空格字符即开始阅读，当它读取到下一个空白字符时，它将停止读取。

getline(cin, inputLine);   举例： getline(cin, name);

2. sort函数，包含在头文件为#include
   
   的c++标准库中，调用标准库里的排序方法可以实现对数据的排序。
   

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); 

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b);
main(){
　　//sort函数第三个参数自己定义，实现从大到小
　　int a[]={45,12,34,77,90,11,2,4,5,55};
　　sort(a,a+10,cmp);
　　for(int i=0;i<10;i++)
　　　　cout<<a[i]<<" ";
}
//自定义函数
bool cmp(int a,int b){
　　return a>b;
}

2.2 STL实现从小到大排序，从大到小排序

Sort函数的第三个参数可以用这样的语句告诉程序你所采用的排序原则

less<数据类型>()//从小到大排序

greater<数据类型>()//从大到小排序

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

 int a[10]={9,6,3,8,5,2,7,4,1,0};

 for(int i=0;i<10;i++)

 cout<<a[i]<<endl;

sort(a,a+10,less<int>());

 for(int i=0;i<10;i++)

 cout<<a[i]<<endl;

 return 0;

}

 


#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

 int a[10]={9,6,3,8,5,2,7,4,1,0};

 for(int i=0;i<10;i++)

 cout<<a[i]<<endl;

 sort(a,a+10,greater<int>());

 for(int i=0;i<10;i++)

 cout<<a[i]<<endl;

 return 0;

}

2.3 利用sort函数还可以实现对字符的排序，排序方法大同小异

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

 char a[11]="asdfghjklk";

 for(int i=0;i<10;i++)

 cout<<a[i]<<endl;

 sort(a,a+10,greater<char>());

 for(int i=0;i<10;i++)

 cout<<a[i]<<endl;

 return 0;

}

3. substr函数，返回一个string，包含s中从pos开始的n个字符的拷贝（pos的默认值是0，n的默认值是s.size() – pos，即不加参数会默认拷贝整个s）

#include<string>
#include<iostream>
using` `namespace` `std;
int` `main()
{
　　string s(``"12345asdf"``);
　　string a = s.substr(0,5);   ``//获得字符串s中从第0位开始的长度为5的字符串
　　cout << a << endl;
}

4. atoi函数，转化的是char[]，c++标准库中字符串转化为int的函数；数字类型字符串转化为整数类型

   stoi（字符串，起始位置，n进制），将 n 进制的字符串转化为十进制

stoi(str, 0, 2); //将字符串 str 从 0 位置开始到末尾的 2 进制转换为十进制
int i_dec = std::stoi (str_dec,&sz);  
int i_hex = std::stoi (str_hex,nullptr,16);  
int i_bin = std::stoi (str_bin,nullptr,2);  
int i_auto = std::stoi (str_auto,nullptr,0);   
std::cout << str_dec << ": " << i_dec << " and [" << str_dec.substr(sz) << "]\n";  
std::cout << str_hex << ": " << i_hex << '\n';  
std::cout << str_bin << ": " << i_bin << '\n';  
std::cout << str_auto << ": " << i_auto << '\n'

5. c_str()。标准库的string类成员函数，从一个string得到c类型的字符数组

#include <iostream>
//需要包含cstring的字符串
#include <cstring>
using namespace std;
 
int main()
{
    //string-->char*
    //c_str()函数返回一个指向正规C字符串的指针, 内容与本string串相同
 
    //这个数组的数据是临时的，当有一个改变这些数据的成员函数被调用后，其中的数据就会失效。
    //因此要么现用先转换，要么把它的数据复制到用户自己可以管理的内存中
    const char *c;
    string s = "1234";
    c = s.c_str();
    cout<<c<<endl;
    s = "abcde";
    cout<<c<<endl;
}

6. sscanf，sscanf()函数用于从字符串中读取指定格式的数据， int sscanf (char *str, char * format [, argument, ...]);参数str为要读取数据的字符串；format为用户指定的格式；argument为变量，用来保存读取到的数据。

成功则返回参数数目，失败则返回-1，错误原因存于errno 中。

sscanf()会将参数str 的字符串根据参数format（格式化字符串）来转换并格式化数据（格式化字符串请参考scanf()）， 转换后的结果存于对应的变量中。

sscanf()与scanf()类似，都是用于输入的，只是scanf()以键盘(stdin)为输入源，sscanf()以固定字符串为输入源。

#include <stdio.h>
int main(void)
{
    char str[100] ="123568qwerSDDAE";
    char lowercase[100];
    int num;
    sscanf(str,"%d %[a-z]", &num, lowercase);
    printf("The number is: %d.\n", num);
    printf("The lowercase is: %s.", lowercase);
    return 0;
}

7. bitset，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。

bitset<4> bitset1;　　//无参构造，长度为４，默认每一位为０

    bitset<8> bitset2(12);　　//长度为８，二进制保存，前面用０补充

    string s = "100101";
    bitset<10> bitset3(s);　　//长度为10，前面用０补充
    
    char s2[] = "10101";
    bitset<13> bitset4(s2);　　//长度为13，前面用０补充

    cout << bitset1 << endl;　　//0000
    cout << bitset2 << endl;　　//00001100
    cout << bitset3 << endl;　　//0000100101
    cout << bitset4 << endl;　　//0000000010101

大神博客链接：华为机试题刷题总结

8. C++控制输出浮点数的，要用到iomanip头文件，在输出数据前要加<< setprecision(6)控制输出位数。

#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
    double h;
    cin >> h;
    cout << setprecision(6) << 2.875 * h << endl << setprecision(6) << 0.03125 * h << endl;
    return 0;
}

9. greater

greater表示内置类型从大到小排序，less表示内置类型从小到大排序。

#include <iostream>

#include<algorithm>//sort函数的头文件

#include<functional>//greater/less的头文件

using namespace std;

int main() {    

int a[10]={0};    

int i;    

for(i=0;i<10;i++)        

     cin>>a[i];      

sort(a,a+10,greater<int>());//快速排序

for(i=0;i<10;i++)    

     cout <<a[i]<< endl;  

return 0

10. set

set 翻译为集合，是一个内部自动有序且不含重复元素的容器。

#include<iostream>
#include<set>
using namespace std;
int main() {
    int n;
    while(cin>>n) {    //输入每组数据的个数
        set<int> order;    //使用set容器可以自动实现去重和排序的操作，这里很关键
        for(int i=0;i<n;i++) {
            int num;
            cin>>num;    //输入数字
            order.insert(num);    //插入到容器order中
        }
        set<int>::iterator it;    //set类型迭代器
        for(it=order.begin();it!=order.end();it++){
            cout<<*it<<endl;    //遍历输出
        }
    }
    return 0;
}

11. [C++中string.find()函数与string::npos]

    查找字符串a是否包含子串b,
    不是用strA.find(strB) > 0而是strA.find(strB) != string:npos

12. C++ memset函数用法

    #include<string.h>
    void *memset(void *s, int ch, size_t n);
    

    memset解释：将s中当前位置后面的n个字节用ch替换并返回s。

    函数作用

    1，memset() 函数常用于内存空间初始化。

    2，memset()的深刻内涵:用来对一段内存空间全部设置为某个字符，一般用在对定义的字符串进行初始化

    例如:memset(a,’\0’,sizeof(a));

    3，memset可以方便的清空一个结构类型的变量或数组。

    struct sample_struct
    {
        char csName[16];
        int iSeq;
        int iType;
    };
    

    一般的初始化方式：（对于变量：struct sample_strcut stTest; ）

    stTest.csName[0]={'\0'};
    stTest.iSeq=0;
    stTest.iType=0;
    

    用memset

    memset(&stTest,0,sizeof(sample_struct));
    

13. next_permutation函数

1、头文件
naxt_permutation函数包含在algorithm库中

2、参数
和sort的参数一样，一般传两个参数，第一个是排列开始的地址，第二个是排列结束的下一个地址，如实现数组第1-3排列的下一个排列：next_permutation(a,a+3)。一般作用对象是数组。

3、作用
next_permutation是求当前排列的下一个排列（按字典序升序的下一个序列），如1234的next_permutation是1243。在全排列当中经常会用。

4、返回值
返回值是Ture或者False，若当前排列有下一个排列，则返回Ture，反之返回False：如54321的返回值为False。该函数会直接修改数组为下一个排列。

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int num[3]={1,2,3};
    //sort(num,num+3);
    do
    {
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
    }while(next_permutation(num,num+3));
    return 0;
}

14.stoi函数

stoi（字符串，起始位置，n进制），将 n 进制的字符串转化为十进制
示例：

stoi(str, 0, 2); //将字符串 str 从 0 位置开始到末尾的 2 进制转换为十进制

15. pair的基本用法

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

16. vector

vector 是向量类型，它可以容纳许多类型的数据，如若干个整数，所以称其为容器。vector 是C++ STL的一个重要成员，使用它时需要包含头文件

1.vector 的初始化：

vector<int> a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初值，其值是不确定的。

vector<int> a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1

vector<int> a(b); //用b向量来创建a向量，整体复制性赋值
vector<int> a(b.begin(),b.begin+3); //定义了a值为b中第0个到第2个（共3个）元素
int b[7]={1,2,3,4,5,9,8};
vector<int> a(b,b+7); //从数组中获得初值ector的初始化  

2.vector对象的操作

（1）a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
    （2）a.assign(4,2); //是a只含4个元素，且每个元素为2
    （3）a.back(); //返回a的最后一个元素
    （4）a.front(); //返回a的第一个元素
    （5）a[i]; //返回a的第i个元素，当且仅当a[i]存在2013-12-07
    （6）a.clear(); //清空a中的元素
    （7）a.empty(); //判断a是否为空，空则返回ture,不空则返回false
    （8）a.pop_back(); //删除a向量的最后一个元素
    （9）a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+         3（不包括它）
    （10）a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
    （11）a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
    （12）a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
    （13）a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8         ，插入元素后为1,4,5,9,2,3,4,5,9,8
    （14）a.size(); //返回a中元素的个数；
    （15）a.capacity(); //返回a在内存中总共可以容纳的元素个数
    （16）a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
    （17）a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
    （18）a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才         显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能） 
    （19）a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换
    （20）a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,<

17. cin.get()函数

首先cin的输入有一个特点，在遇到‘ ’（空格）时，会结束输入，而cin.get()则将‘ ’也作为了一个字符放到输入里。

1.cin.get(字符变量名)可以用来接收字符

char ch; 
ch=cin.get();               //或者cin.get(ch); 
cout<<ch<<endl; 

2.cin.get(字符数组名,接收字符数目)用来接收一行字符串

char a[20]; 
cin.get(a,20); 
cout<<a<<endl; 

输入：jkl jkl jkl
输出：jkl jkl jkl

输入：abcdeabcdeabcdeabcdeabcde （输入25个字符）
输出：abcdeabcdeabcdeabcd （接收19个字符+1个’\0’）

3.cin.get(无参数)没有参数主要是用于舍弃输入流中的不需要的字符,或者舍弃回车,弥补cin.get(字符数组名,接收字符数目)的不足

string a;
cin>>a;
cout<<a<<endl;
cin.get();
cin.get();
//cin.ignore(1024,'\n');
//cin.get();

此时的第一个cin.get()获取的是cin中最后的’\n’，第二个的作用在于在程序结束时输入一个字符，让程序停留在运行界面

注意：此时的第一个cin.get()与cin.ignore()的用法相似，均是消除输入流中的’\n’

常考的算法：

dfs和bfs

图文详解 BFS, DFS – 力扣（LeetCode） https://leetcode.cn/circle/article/YLb5l4/

双指针

概念：

• 双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务

• 若两个指针指向同一数组，遍历方向相同且不会相交，也成为滑动窗口

• 若指向同一数组，但是遍历方向相反，则可用来进行搜索

  题解一（两数之和）

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left=0,right=numbers.size()-1;
        while(left<right){
            int sum=numbers[left]+numbers[right];
            if(sum==target) return {left+1,right+1};
            else if(sum<target) left++;
            else right--;
        }
        return {-1,-1};
    }
};

递归和动态规划的区别

相同点：
递归与动态规划是两个十分基本的算法，它们使用的思路都是分而治之，将一个大问题拆解成一个小问题。

不同点：
1.递归是从上而下（从大问题到小问题），而动态规划是由下而上（先解决小问题最后到大问题）；
2.动态规划会储存每个小问题的结果，从而它的计算速度会比递归要快。（代价是动态规划的空间复杂度更高，即用空间换取的时间）。
3.动态规划是用递归实现的，递归是用函数实现的。

动态规划

动态规划有两种实现方法，一种是递推，另一种是记忆化搜索。两种方法时间复杂度完全相同，但是，递推的效率要比记忆化搜索高不少，而且以后的大量优化技巧都建立在递推上（滚动数组、单调队列、斜率优化……）。所以，我们一般用递推来写动态规划。

1.算法实现步骤

1.1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述

1.2、找到初始条件，设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。

1.3、根据初始条件或边界条件，找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。

1.4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。

2.解题步骤

拆分问题；

定义状态并找出初状态；

状态转移方程。

具体可以看大佬写的文章，https://blog.csdn.net/weixin_51951103/article/details/120241450?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166078556816782414922143%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166078556816782414922143&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_click~default-2-120241450-null-null.142v41pc_rank_34_ecpm25,185v2control&utm_term=C%2B%2B%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92&spm=1018.2226.3001.4187

具体步骤：

1. 确定dp数组（dp table）以及下标的含义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序（dp[i] 是根据dp[i – 2] 和 dp[i – 1] 推导出来的，那么一定是从前到后遍历！）

5. 举例推导dp数组

   https://www.programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html#_198-%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D

栈

1、栈(Stack)是一种线性存储结构，它具有如下特点：

（1）栈中的数据元素遵守“先进后出”(First In Last Out)的原则，简称FILO结构。（后进先出的叫法，也是可以的）

（2）限定只能在栈顶进行插入和删除操作。

2.栈的常见分类：

（1）基于数组的栈——以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向

（2）基于单链表的栈——以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的新节点将一直出现在链表的头部

3.基本操作

s.empty();         //如果栈为空则返回true, 否则返回false;
s.size();          //返回栈中元素的个数
s.top();           //返回栈顶元素, 但不删除该元素
s.pop();           //弹出栈顶元素, 但不返回其值
s.push();          //将元素压入栈顶

//基于数组的栈
#include <stack>
#include <iostream>
using namespace std;

int main()
{
	stack<int> mystack;
	int sum = 0;
	for (int i = 0; i <= 10; i++){
		mystack.push(i);
	}
	cout << "size is " << mystack.size() << endl;
	while (!mystack.empty()){
		cout << " " << mystack.top();
		mystack.pop();
	}
	cout << endl;
	system("pause");
	return 0;
}
//size is 11   
// 10 9 8 7 6 5 4 3 2 1 0

———————————分割线—————————————

需要学习知识点的题

5.写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

#include<iostream>
using namespace std;
int main(){
    string a;
    while(getline(cin,a)){
        int res=0;
        int pos=a.find('x');
        for(int i=pos+1;i<a.size();++i){
            int tmp=0;
            if(a[i]>='A'&&a[i]<='F'){
                tmp=10+(a[i]-'A');
            }
            else{
                tmp=a[i]-'0';
            }
            res=res*16+tmp;
        }
        cout<<res<<endl;
    }
    return 0;
}

需要知道十进制转为十六进制的原理：十六进制数从低位到高位（即从右往左）计算，第0位的权值是16的0次方，第1位的权值是16的1次方，第2位的权值是16的2次方，依次递增下去，把最后的结果相加的值就是十进制的值了。

　　十六进制就是逢16进1，十六进制的16个数为0123456789ABCDEF。

　　例：将十六进制的(2B)H转换为十进制的步骤如下：

\1. 第0位 B x 16^0 = 11；

\2. 第1位 2 x 16^1 = 32；

\3. 读数，把结果值相加，11+32=43，即(2B)H=(43)D。

具体其他进制相互转换，请看大神博客：

华为机试题刷题总结