华为机试一霸教你过华为机试.docx

大师兄教你如何过华为机试

宝典1—内功心法
大华为这个大数据时代土豪金海量式的招聘又要开始了！！！
近期听说大华为的校招机试马上就要开始了，由于华为软件岗位的招聘只有技术面跟机试是与技术有关的内容，所以机试的地位非常重要。对于机试，除了长期积累的软件基本功以外，还有很多可以短期训练的东西，类似于考试之前的突击，可以迅速提高机试成绩，就像在我西电大杨老师考前最后一堂课一定要去，那个重点就是考点阿。
这篇机试葵花宝典的内容是针对华为软件类上机准备的，如果你认真看了本宝典,如果你是真正通过自己能力考上西电的话,想不过都难。同样想拿高级题的同学，请移步
对于机试，首先应该调整好自己的心态，不要觉得写程序很难，机试题很难，也不要去考虑，万一机试考到自己不会的内容怎么办，要相信，机试题永远是考察每个人的基础，基础是不会考的很偏的，会有人恰好做过某个题而做出来那个题，但不会有人恰好没做过一个题而做不出来那个题。
机试之前，应该做的准备有：
1、 买一本《算法竞赛入门经典》，这本书不同于普通的算法或者编程语言的书籍，这本书既讲语言，又讲算法，由浅入深，讲的很好，能看完前几章并且把例题都做会，想通过机试就很简单了
2、 调整好心态，时刻告诉自己，哪些小错误是自己以前经常犯的，最好用笔记本记录下来，写每道题前再看一遍，如果遇到代码调不出来了，先想想自己是否犯过以前那些错误。还有就是，看了题目以后，先仔细想清楚细节，在纸上写清楚自己需要用到的变量，以及代码的基本框架，不要急于动手去写代码
3、 不要惧怕任何一道看起来很难的题目，有不会的就去问身边会的人，让别人给自己讲清楚
4、 心中默念10遍C++跟C除了多了两个加号其实没有区别，会C就能上手C++
5、 大量的练习是必要且有效的
6、 看完这篇宝典，预过机试、必练此功。
在这里推荐一个帖子，是机试归来的学长写的，写的很不错，里面的例题在后面的攻略中也会提及, 就在好网上。
宝典二：常用招式
1：机试常用变量类型
C\C++常用的变量类型有很多种，想通过机试，掌握好其中的几种就可以，他们分别是int，double, string, char[]
int 类型是最常用的整数类型，对于输入类型是整形的变量，使用int来进行定义和读入。还有一种更大的整形变量是long long，在机试中一般不会涉及到考察，如果考虑到运算的过程中有可能超过int的大小，再考虑使用long long，int最大可以到达2^31级别，long long最大可以到达2^63。
PS：有时机试读入多个整数的时候会是这样的形式
5,10
中间有一个逗号，在这种情况下，其实读入也是很简单的，可以这么写：
scanf(“%d%c%d”,&a,&b,&c);
或者是：
scanf(“%d”,&a);
getchar();
scanf(“%d”,&c);
有的机试题会说：两个整数之间有若干个空格符或tab字符。在这种情况下，读入的方式还是使用scanf(“%d%d”,&a,&b)这样，scanf函数或者cin函数都可以很好的吃掉除了数字字符以外的字符。

double类型是最常用的浮点数类型，当运算涉及到小数运算的时候，需要使用double来定义。其中，特别需要注意的一点是，如果使用了如下语句：
double x=a/b;
在这里，a和b是int，那么x的值将是a和b整除后的结果，而不是想要的结果，想要得到期望的结果，须改成
double x=(a+0.0)/b;
在这里，将a加上一个浮点数，程序会在后台将它强制转换成一个double类型的数字，此时再除一个整数，就没有问题了

string类型是遇到字符串类问题应该首选的变量，区别于字符数组char[]，string类型是直接将字符数组封装了进去，定义string s相当于定义了一个大小特别长的字符数组。使用string的好处是，避免了使用char数组时定义数组长度过小导致越界，同时更加直观的将字符串看做了一个对象。
如果要定义一个string变量，首先得包含string的头文件以及使用C++中的标准命名空间，标准命名空间这个东西，只要记得写上就行，没有任何影响。
#include //这一句是c++的头文件，c语言代码一样可以把它包含进来，只要将程序后缀名改成.cpp即可，其他都是一样的。
#include
using namespace std;
在不同的环境下，可能会有不同的头文件包含了string的用法，可能的头文件有cstring,string。在机试的环境中，一般使用string.h即可。
定义一个string和定义其他变量方式相同：
string s;
读入和输出string也只需要使用
cin>>s;
cout<了很多的。
需要注意的是，string类型读入的时候与char数组的scanf读入一样，都是遇到空格符或者回车符就停止读入，当做一个完整字符串来处理，因此，使用string处理带空格的字符串是不明智的，其他情况下是都可以的。
string变量包含了很多强大的功能，如：
[cpp] view plaincopyprint?
1. s[i]; //这么写，返回的就是字符串s第i+1位的字符，返回的类型是char型，其中,s[0]是它的第一位，与字符串相同。
2. s.size(); //返回字符串的长度，返回的长度是l，则s从s[0]到s[l-1]表示的是其每一位的字符。
3. if (s1型很像，只不过他是C语言里面的用法，对于机试，只建议在输入带有空格字符的字符串时使用char数组，使用的方式是：
gets(s);
在这里，gets函数区别于scanf函数的是，gets函数会直接将一整行读进来，而不会遇到空格就停下来。
常见机试题类型
初级题常见的类型无非就是字符串处理类的题目和数字处理类的题目，在这里归结如下：
1：字符串处理类
字符串所有大写转小写：
1. for (int i=0;i=’A’ && s[i]<=’Z’)
3. s[i]=s[i]-’A’+’a’;
//s[i]-’A’返回的是两个大写字母之间的差值，比如’C’与’A’的差值是2，这个差值是一个int类型，也可以直接提取出来使用。给这个差值再加上字母’a’，相当于给’a’再往后推移二位，变成字母’c’。这种用法是字符串内最普遍的一种用法，小写转大写也是一样。
删除满足指定要求的字符后输出：
在机试中，判定对错的方式是比较输出的结果，而非检查内部的结果，因此，“删除”对于机试来说，相当于“不输出”，也就是说，不需要调用s.erase()函数，只需要在遇到被删除的字符时，跳过，不输出即可。
1. for (int i=0;i
2. {
3. if (s[i]满足删除要求) 跳过;
4. else 输出s[i];
5. }
倒转字符串：
与删除字符串的思路类似，倒转一个字符串，其实就是倒着输出，只需要将循环反过来就可以。
1. for (int i=s.size()-1;i>=0;i--)
字符串比较大小：
如果比较的规则与字符串的比较规则相同，则直接使用s1>s2这种方式，如果规则不同，则用一重循环按位比较即可。
2、数字处理类
数字处理类的题目，最常见的两种考察形式是整数拆分、进制转换和排序。
整数拆分是指将一个整数拆分开每一位，比如123拆分成1,2,3。整数拆分的思路有两种，第一种是直接用字符串读入，然后把每一位用字符的形式提取出来：
[cpp] view plaincopyprint?
1. for (int i=0;i num[i]=s[i]-'0';
还有一种思路是不断去除以10，把余数提取出来，方法是：
[cpp] view plaincopyprint?
1. while (n!=0)
2. {
3. num[i]=n%10;
4. n=n/10;
5. i++;
6. }
进制转换：
进制转换又分为10进制转换成别的进制以及别的进制转换成10进制，进制转换其实特别简单，只需要记住如下代码：
10进制转换成X进制
[cpp] view plaincopyprint?
1. while (n!=0)
2. {
3 num[i]=n%x;
4. i++;
5. n=n/x;
6. }
X进制转换成10进制
[cpp] view plaincopyprint?
1. for (int i=0;i<=length;i++)
2. {
3. ans=ans*x+num[i];
4. }
其中num[i]表示的是该x进制数的每一位，比如一个二进制数101，用这种转换方式去转换，ans的值从i=0到i=2处理后分别是1,2,5。
排序：
排序这个东西，其实不需要学习冒泡啊、快排啊之类的算法，应对机试，C++中自带的sort函数就可以很好的解决，请看下面一段代码
[cpp] view plaincopyprint?
1. td;
4. int arr[100],n;
5. int cmp(int x,int y) //这个函数是sort函数比较两个元素优先级的函数，在这里计算出两个元素的优先级，然后返回即可。
6. {
7. int importance1,importance2;
8. //此处插入代码计算x,y的重要性
9. return importance1
12. {
13. cin>>n;
14. for (int i=0;i>arr[i];
15. sort(arr,arr+n,cmp);
16. return 0;
17. }
这一段代码的作用是读入n个数字,然后按优先级进行排序，排序的比较方法在cmp函数中实现，排序的具体过程不需要考虑。
可以看到，其实只需要记住sort函数的用法，要通过机试，排序算法是根本不需要学习的，so easy！
总结：机试中，掌握好int，double，string，char[]，还有数组，就足够用了，但考察的内容不仅仅是上述这些，想要通过机试，还是应该多多练习，多多学习，不局限于上面所说的内容
宝典三：擂台实战
首先推荐一个网站:
很简单：1031,1120,1122,1121,1103,1104,1281，
简单：1049，1181，1182，1279,1280，
中等：1106,1108，1183，1288.
难：1105，1282,1283，
大家可以根据自己的水平去训练，其实里面的难题也是很简单的，归类到题库中的话都属于简单题，只要好好看书学习都是可以做出来的，下面放几道例题，这些题都是机试很有可能考的题目，或者是非常类似的题目，已经有了仔细的注释代码写的仓促
1. 简单题
2. 题目描述
3. 输入一个字符串，删除其中所有的数字，所有大写字母改成小写，其他不变，并输出
4.
5. 输入描述
6. 一个字符串，保证没有空格，以回车符结束，字符串长度<=20
7. 输出描述
8. 一个字符串，为题目要求的结果
9.
10. 输入样例
11. aAbB13A
12. 输出样例
13. aabba
14.
15. 解题思路：模拟题目要求即可，遇到数字就跳过不输出，遇到大写字母就改成小写。
16.
17. */
18. #include

19. #include
20. using namespace std;
21. int main()
22. {
23. string s;
24. cin>>s;
25. for (int i=0;i='0' && s[i]<='9') continue; //遇到数字就跳过
28. if (s[i]>='A' && s[i]<='Z') s[i]=s[i]-'A'+'a'; //遇到大写字母就改成小写
29. cout<

34. 简单题
35. 题目描述
36. 输入一个字符串，统计其出现频率最高的字符，并输出。若存在两个字符出现频率相同，则输出字典序较小的那一个
37.
38. 输入描述
39. 一个字符串，保证没有空格，以回车符结束，字符串长度<=20
40. 输出描述
41. 一个字符
42.
43. 输入样例
44. aabbaabb
45. 输出样例
46. a
47.
48. 解题思路：做一个频率数组来统计所有字符的出现频率，机试时候不会有汉字输入，因此只考虑输入是ASCII编码的情况。
49.
50. */
51. #include
52. #include
53. using namespace std;
54. int f[200]; //频率数组
55. int biggest=0; //记录最大的值
56. int main()
57. {
58. memset(f,0,sizeof(f)); //将f中的全部元素变成0，写循环也可
59. string s;
60. cin>>s;
61. for (int i=0;i//比较找出最大的
66. }
67. for (int i=0;i<=129;i++) //枚举所有的字符的频率，找出频率最高且字典序最小的那一个
68. if (f[i]==biggest) //如果满足要求
69. {
70. cout<<(char)(i)<

75. 简单题
76. 题目描述
77. 输入一个数字，将其倒序输出，并输出其各个位上的乘积
78.
79. 输入描述
80. 一个正整数，保证在int范围内
81. 输出描述
82. 两个数字，用空格隔开，第一个数字为其倒序的值，第二个数字是各个位上的乘积
83.
84. 输入样例
85. 134
86. 输出样例
87. 431 12
88.
89.
90. 解题思路：删繁就简，直接当字符串读入，处理就简单多了。
91. PS：此处不用纠结于题意，没有特别强调是按照一个数的格式输出，因此可以有前导0
92.
93. */
94. #include
95. #include
96. using namespace std;
97. int main()
98. {
99. string s;
100. int ans=1;
101. cin>>s;
102. for (int i=s.size()-1;i>=0;i--)
103. {
104. cout< ans=ans*(s[i]-'0'); //ans累乘每一位的值
106. }
107. cout<<' '<19. 11 3 2 4 5 9 8 7 10 6
120. 输出样例
121. 10 2 11 3 4 5 6 7 8 9
122.
123. 解题思路：调用C++自带的sort函数，重新改写compare函数即可。
124. */
125. #include
126. #include
127. #include //这个是调用sort函数必须的头文件
128. using namespace std;
129. int arr[10];
130. int cal(int x) //计算一个数字各个位上的和
131. {
132. int ans=0;
133. while (x!=0)
134. {
135. ans+=x%10;
136. x/=10;
137. }
138. return ans;1
139. }
140. int cmp(int i,int j)
141. {
142. if (cal(i)!=cal(j)) //如果两个数字各个位上的和不相同，则按照各个位上的和来排序
143. {
144. return cal(i)>arr[i];
154. sort(arr,arr+10,cmp);
155. for (int i=0;i<=9;i++)
156. {
157. cout< 你有一个容量为100的箩筐，给你30个物品，每个物品的体积已知问：最多能装多少个物品进箩筐
166. 输入描述
167. 一行30个正整数，用空格隔开，表示每个物品的体积
168. 输出描述
169. 一个数字，为最多能装下的物品数
170.
171. 输入样例（此处用3个物品作为样例，实际读入为30个）
172. 5 59 100
173. 输出样例
174. 2
175.
176. 解题思路：利用性价比对所有物品进行排序，优先装性价比高的，在此题中，性价比就是物品的体积
177. */
178. #includem>
179. #include
180. #include //这个是调用sort函数必须的头文件
181. using namespace std;
182. int arr[31];
183. int main()
184. {
185. for (int i=0;i<=29;i++) cin>>arr[i];
186. sort(arr,arr+30); //从小到大排序
187. //从最小的开始装框，直到装满了为止。
188. int sum=0;
189. for (int i=0;i<=29;i++)
190. {
191. if (sum+arr[i]>100) break; //如果不能装了就立刻停下来
192. sum=sum+arr[i]; //否则就把这个也装进去
193. }
194. //程序跳出的那个位置的i，就是我们一共装了的数量，如果全部都装了，则i=30
195. cout<经做的机试题）
198. 描述：10个学生考完期末考试评卷完成后，A老师需要划出及格线，要求如下：
199. (1) 及格线是10的倍数；
200. (2) 保证至少有60%的学生及格；
201. (3) 如果所有的学生都高于60分，则及格线为60分
202. (4) 及格线越高越好，但最高不能超过60
203. 输入：输入10个整数，取值0~100
204. 输出：输出及格线，10的倍数
205. 输入样例：61 51 49 30 20 10 70 80 90 99
206. 输出样例：50
207.
208. 解题思路：从高到低枚举及格线，输出第一个满足要求的及格线就是答案
209. */
210. #include
211. using namespace std;
212. int arr[10];
213. int main()
214. {
215. for (int i=0;i<=9;i++) cin>>arr[i];
216. int line;
217. for (line=60;line>=0;line-=10) //从高到低枚举分数线
218. {
219. int num=0; //该变量用来统计这个分数线下，是否超过60%同学及格
220. for (int i=0;i<=9;i++)
221. if (arr[i]>=line) //如果分数大于等于及格线，说明在这个分数线下是及格的
222. num++;
223. if (num>=6) //如果超过60%的人及格，在这里10的60%就是6
224. break; //满足了要求就立刻break，说明这是分数线
225. }
226. cout<完后，长廊里电灯有几盏亮着。注：电灯数和学生数一致。
231.
232. 输入：电灯的数量
233. 输出：亮着的电灯数量
234. 样例输入：3
235. 样例输出：1
236.
237. 解题思路1：这道题，如果要模拟的话，当然是可以的，但对于代码基础较差的同学写起来就比较吃力了，在这里写模拟的做法
238. 解题思路2：在这道题上面多思考思考，可以看出，对于任何一个灯来说，比如12，其因数有1,2,3,4,6,12。说明，编号为1,2,3,4,6,12的学生分别要拉它一下，在这里发现，1*12=12,2*6=12,3*4=12，所以其因数都是一一对应的也就是，1拉的那一下被12抵消了，2拉的那一下被6抵消了，那么谁不会被抵消呢？答案是平方数，比如9的因数是1,3,9，那么3*3=9，而3只拉一次，所以不会被抵消。因此，这道题的答案就是，输入的n以内的平方数个数，等于(int)sqrt(n)。
239. 从这道题可以看出，编程的很多时候，多思考比多动笔要有用的多。
240.
241. */
242. #include
243. #include
244. using namespace std;
245. int vis[65536],n;
246. int main()
247. {
248. cin>>n;
249. memset(vis,0,sizeof(vis)); //这句话的意思是把vis数组清0,0表示此刻灯是关着的，1表示是开着的
250. for (int i=1;i<=n;i++) //枚举每一个学生的编号
251. for (int j=i;j<=n;j+=i) //从j=i开始，每次给j+i，使得i,i*2,i*3,...,这些灯全部都被拉一次开关
252. vis[j]=1-vis[j]; //1->0,0->1，本质上都是用1减去它本身。
253. int ans=0; //统计答案
254. for (int i=1;i<=n;i++)
255. if (vis[i]==1) //如果现在是开灯状态，答案加一
256. ans++;
257. cout<先中后序遍历，及已知遍历对树的构造等），栈（怎么用数组模拟栈，栈的特性等），图论（最短路算法，连通性判断等），动态规划（这个就太多了，入门请看背包九讲）等等等等。虽然写了这么多，但高级题其实并没有这么难，高级题主要考搜索比较多一些，偶尔会有树、栈、图、动态规划的题目，不过，要想当个好码农，算法和数据结构基础是必须的
机试葵花宝典就写到这里了，大师兄在大华为等你们哪，来了我们一起在练独孤九剑，六脉神剑。
附好网上另一师兄机试心得，共小弟妹们参考：
华为机试成功归来，与小伙伴们分享下经验
前段时间参加华为机试，机试通过的可以优先录取，优先选择岗位和工作地，关键是面的好，还可以谈更高的工资，最多在西安可以拿到18W。好处还是蛮多的，抱着试试看的态度就去了。哈哈，华为机试记录正是开始。
提前在网上交了简历，周围同学只要报了软件研发类的相关岗位都收到短信通知，需要用到编程的同学基本上都受到短信了。一天三波，在西工大毅字楼三楼机房，南门进去直走左拐就到了，我是第二天早上的机试，前一天已经听机试过的同学考的内容涉及数组、链表、指针、字符串、循环、枚举、排序等吧，这个估计要看人品，平时出门多扶老奶奶过马路吧。其实考过后发现这个机试跟平时做项目不一样，项目可能更多的注重实现研究所需要的某个功能不会去注意这么多细节，但是机试考的更多的是基本功。下面重点跟大家分享下上机题吧，我只列举了我抽到的三个，其他同学抽到的跟这个大同小异吧。大家自己编写下，对即将开始的面试都会有帮助的。
考试内容：数组、链表、指针、字符串、循环、枚举、排序等（从考过的同学那儿总结的可能不全）
试题结构：考试总共三道题，说是难中易，初级题（60分）、中级题（100分）、高级题（160分），最难的接近一百行，说多不多，但自己敲出来还是费了点劲，
考试时间：两个小时。平时练得少可能稍微捉鸡点。
最简单的一个
描述：10个学生考完期末考试评卷完成后，A老师需要划出及格线，要求如下：
(1) 及格线是10的倍数；
(2) 保证至少有60%的学生及格；
(3) 如果所有的学生都高于60分，则及格线为60分
输入：输入10个整数，取值0~100
输出：输出及格线，10的倍数
输入样例：61 51 49 30 20 10 70 80 90 99
输出样例：50
自己编写代码简单如下：
1. #include
2.
3.
4. void bubbleSort(int arr[])
5. {
6. int i = 0;
7. int j = 0;
8. int t = 0;
9.
10. for(i = 0i < 10; i++)
11. {
12. for(j = 0; j < (9 - i); j++)
13. {
14. if(arr[j + 1] < arr[j])
15. {
16. t = arr[j + 1];
17. arr[j + 1] = arr[j];
18. arr[j] = t;
19. }
20. }
21. }
22. }
23.
24. int getPassLine(int a[])
25. {
26. int i = 0;
27.
28. bubbleSort(a);
29.
30. if (a[0] >= 60)
31. {
32. return 60;
33. }
34. else
35. {
36. return ((a[4] / 10) * 10);
37. }
38.
39. }
40.
41.
42.
43. int main()
44. {
45. int a[10] = {0};
46.
47.