首页 > 代码库 > 华为机试 宝典3 —擂台实战
华为机试 宝典3 —擂台实战
首先推荐一个网站:acm.xidian.edu.cn/land/,上面的很多题目,难度很适合机试,如:
很简单: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<iostream>
19. #include<string.h>
20. using namespace std;
21. int main()
22. {
23. string s;
24. cin>>s;
25. for (int i=0;i<s.size();i++) //枚举字符串的每一位
26. {
27. if (s[i]>=‘0‘ && s[i]<=‘9‘) continue; //遇到数字就跳过
28. if (s[i]>=‘A‘ && s[i]<=‘Z‘) s[i]=s[i]-‘A‘+‘a‘; //遇到大写字母就改成小写
29. cout<<s[i];
30. }
31. cout<<endl;
32. }
33. </span>
34. 简单题
35. 题目描述
36. 输入一个字符串,统计其出现频率最高的字符,并输出。若存在两个字符出现频率相同,则输出字典序较小的那一个
37.
38. 输入描述
39. 一个字符串,保证没有空格,以回车符结束,字符串长度<=20
40. 输出描述
41. 一个字符
42.
43. 输入样例
44. aabbaabb
45. 输出样例
46. a
47.
48. 解题思路:做一个频率数组来统计所有字符的出现频率,机试时候不会有汉字输入,因此只考虑输入是ASCII编码的情况。
49.
50. */
51. #include<iostream>
52. #include<string.h>
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<s.size();i++) //枚举字符串的每一位
62. {
63. int num=s[i]; //将s[i]转换成它的ascii码
64. f[num]++; //频率次数加1
65. biggest=max(biggest,f[s[i]]); //比较找出最大的
66. }
67. for (int i=0;i<=129;i++) //枚举所有的字符的频率,找出频率最高且字典序最小的那一个
68. if (f[i]==biggest) //如果满足要求
69. {
70. cout<<(char)(i)<<endl;
71. break; //这句break保证了我们只会输出一个满足要求的结果
72. }
73. }
74. /*
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<iostream>
95. #include<string.h>
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<<s[i]; //倒序输出每一位
105. ans=ans*(s[i]-‘0‘); //ans累乘每一位的值
106. }
107. cout<<‘ ‘<<ans<<endl;
108. }
109. 中级题
110. 题目描述
111. 输入10个数字,按各个位上的和从小到大排序,如果相同,则按数字从小到大排序。
112.
113. 输入描述
114. 10个正整数,保证都在int范围内,用空格隔开
115. 输出描述
116. 10个数字,其从大到小的值,用空格隔开,最后一个数字后不加空格
117.
118. 输入样例
119. 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<iostream>
126. #include<string.h>
127. #include<algorithm> //这个是调用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)<cal(j);
145. }
146. else //否则,即两个数各个位上的和相等,则按照数字本身来排序
147. {
148. return i<j;
149. }
150. }
151. int main()
152. {
153. for (int i=0;i<=9;i++) cin>>arr[i];
154. sort(arr,arr+10,cmp);
155. for (int i=0;i<=9;i++)
156. {
157. cout<<arr[i];
158. if (i!=9) cout<<‘ ‘; //如果不是最后一个数字,则需要在两个数字中间输出一个空格。
159. }
160. cout<<endl;
161. //PS:最后一个输出的后面一定要跟回车符而不是空格符
162. }
163. 中级题
164. 题目描述
165. 你有一个容量为100的箩筐,给你30个物品,每个物品的体积已知问:最多能装多少个物品进箩筐
166. 输入描述
167. 一行30个正整数,用空格隔开,表示每个物品的体积
168. 输出描述
169. 一个数字,为最多能装下的物品数
170.
171. 输入样例(此处用3个物品作为样例,实际读入为30个)
172. 5 59 100
173. 输出样例
174. 2
175.
176. 解题思路:利用性价比对所有物品进行排序,优先装性价比高的,在此题中,性价比就是物品的体积
177. */
178. #include<iostream>
179. #include<string.h>
180. #include<algorithm> //这个是调用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<<i<<endl;
196. }
197. 初级题:(此题是我曾经做的机试题)
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<iostream>
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<<line<<endl;
227. }
228. 中级题:100分 (此题是我曾经做的机试题)
229. 描述:一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯,从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始,电灯全部关着。
230. 有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下;接着第二个学生把号码凡是2的倍数的电灯的开关拉一下;接着第三个学生把号码凡是3的倍数的电灯的开关拉一下;如此继续下去,最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。n个学生按此规定走完后,长廊里电灯有几盏亮着。注:电灯数和学生数一致。
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<iostream>
243. #include<string.h>
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<<ans<<endl;
}
上面的所有代码能够看懂,并且自己实现一遍,再练上几个类似的题,过机试肯定没问题,能够轻松写出上面的代码,那么机试优秀肯定没问题。想拿满分,请去学习搜索(dfs,bfs),树(先中后序遍历,及已知遍历对树的构造等),栈(怎么用数组模拟栈,栈的特性等),图论(最短路算法,连通性判断等),动态规划(这个就太多了,入门请看背包九讲)等等等等。虽然写了这么多,但高级题其实并没有这么难,高级题主要考搜索比较多一些,偶尔会有树、栈、图、动态规划的题目,不过,要想当个好码农,算法和数据结构基础是必须的。
华为机试 宝典3 —擂台实战