2015 华为 校招回忆录---篇(上)

本文由CSDN-蚍蜉撼青松【主页：http://blog.csdn.net/howeverpf】原创，转载请注明出处！

写在前面：

        当前华为公司的一次机试，共三道不同难度的编程题（其中，初级题60分、中级题100分、高级题160分），机试成绩>=60即可参加下一轮面试。一定程度上说，只要完全做对初级题，就可以通过机试的考验。当然，这样的通过肯定不太利于后面的面试。

        写作本文的目的有两个，一是对本次参加的华为公司机试做个整理和小结，属于自我提升；二是让各位求职的应届生同道能够直观体验当前一般的机试题大概是何种类型，难度又有几分，属于经验分享。由于只是作为体验而非试题汇总，所以本文只列举了我以及我的小伙伴们遇到的几次机试中的初级题，并不做更多的收集。

        每道题包括题目详情、编程思路、代码实现三部分。  

1、输出重复的英文字符

编程思路：

        先遍历一次整个输入字符串，分别记录所有出现过的字符（剔除重复的，按字符第一次出现位置的先后排列。用数组cExistChar）以及他出现的次数（为了操作方便，可以用分配排序的思想。用数组nApperTimes）；

        再遍历一次数组cExistChar，若其出现次数大于1，则输出。

代码实现：

[cpp] view plaincopyprint?

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
5. #define MAX_IN_SIZE 1000   // 输入字符串的最大长度
7. int print_repeat_chars(char *pszString)  
8. {  
9. char cExistChar[52];   // 所有出现过的字符(剔除重复的|最多52个)
10. int nExistCharCount = 0;  // 当前一共出现了多少不重复的字符
11. int nApperTimes[52];   // 所有英文字符出现过的次数(基于分配排序思想，以英文字符的值的某种运算结果作为下标)
12. int i,nStrLen = 0;  
13. char temp;  
15.     memset(nApperTimes, 0, sizeof(nApperTimes));  
17. // 遍历整个输入字符串
18.     nStrLen = strlen(pszString);  
19. for(i=0; i<nStrLen; i++)  
20.     {  
21.         temp = *(pszString+i);  
22. if( temp>='A' && temp<='Z')  
23.         {  
24. // 大写英文字符是否是第一次出现
25. if(nApperTimes[temp-'A']==0)  
26.             {  
27. // 记录前面没出现过的新大写英文字符
28.                 cExistChar[nExistCharCount++] = temp;  
29.             }  
30.             nApperTimes[temp-'A']++;  
31.         }  
32. else if( temp>='a' && temp<='z')  
33.         {  
34. // 小写英文字符是否是第一次出现
35. if(nApperTimes[temp-'a'+26]==0)  
36.             {  
37. // 记录前面没出现过的新大写英文字符
38.                 cExistChar[nExistCharCount++] = temp;  
39.             }  
40.             nApperTimes[temp-'a'+26]++;  
41.         }  
42. //只处理52个大小写英文字符，其余字符不处理
43.     }  
45. // 遍历cExistChar
46. for(i=0; i<nExistCharCount; i++)  
47.     {  
48.         temp = cExistChar[i];  
49. if( temp>='A' && temp<='Z')  
50.         {  
51. // 输出出现次数大于1的大写字符
52. if(nApperTimes[temp-'A']>1)  
53.                 printf("%c", temp);  
54.         }  
55. else if( temp>='a' && temp<='z')  
56.         {  
57. // 输出出现次数大于1的小写字符
58. if(nApperTimes[temp-'a'+26]>1)  
59.                 printf("%c", temp);  
60.         }  
61.     }  
63. return 0;  
64. }  
66. int main(void)  
67. {  
68. char szInString[MAX_IN_SIZE];  //输入字符串
70. // 获取输入的字符串
71.     scanf("%s", szInString);  
72. // 打印输入字符串中重复的英文字符
73.     print_repeat_chars(szInString);  
75. return 0;  
76. }  

2、笨笨熊搬家打包篇

编程思路：

        先把所有物品按体积从大到小排个序。

        然后用两个指针分别从头、尾向中间遍历，直到头指针与尾指针重合，或超过尾指针。在遍历的过程中，对于头指针，恒速后推；对于尾指针，取当前头、尾指针指向的物品(即当前剩余物品中体积最大和最小的物品)，体积求和，若小于盒子的体积，则尾指针前移一位。

        若头、尾指针重合，则最少所需盒子数为头指针的位移量+1；若头指针超过了尾指针，则最少所需盒子数为头指针的位移量。

代码实现：

[cpp] view plaincopyprint?

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define ITEMS_COUNT_MAX 100
6. // 冒泡降序排序
7. //参数 pSortList, 待排序序列
8. int my_sort_bubble(int *pSortList, int nListSize)  
9. {  
10. int i,j;  
11. bool bIfContinue = true;  //外循环继续标志(如果你要写纯C程序，当然就需要把这里替换成整型)
13. for(i=0; i<nListSize-1 && bIfContinue; i++)  //bIfContinue为false时，直接退出外循环
14.     {  
15.         bIfContinue = false;  //内循环开始前假定i后面的子序列已经完全有序，外循环继续标志置为false
17. // 从最后一个元素开始，直到第 i+1 个元素
18. // 所有元素依次和它的前一个元素作关键字比较，更大则交换
19. for(j=nListSize-1; j>i; j--)  
20.         {  
21. if(pSortList[j] > pSortList[j-1]) //冒泡排序比小，咱比大
22.             {  
23.                 bIfContinue=true;  //只要有一次元素交换，说明未完全有序，则外循环需要继续
25.                 pSortList[j]   = pSortList[j] + pSortList[j-1];  
26.                 pSortList[j-1] = pSortList[j] - pSortList[j-1];  
27.                 pSortList[j]   = pSortList[j] - pSortList[j-1];  
28.             }  
29.         }  
30.     }  
32. return 0;  
33. }  
35. // 计算最少所需盒子数
36. //参数 nVolume_of_box, //盒子的容积V
37. //参数 nNum_of_items,  //物品的数量N
38. //参数 pnVolume_of_items, //N个物品的体积
39. //返回 最少所需盒子数
40. int calc_least_box_count(int nVolume_of_box, int nNum_of_items, int *pnVolume_of_items)  
41. {  
42. int i,j;  
44. if(nNum_of_items <= 1)  
45. return nNum_of_items;  
47. // 先对所有物品的体积从大到小排序
48.     my_sort_bubble(pnVolume_of_items, nNum_of_items);  
50. // 输入合法性判定，不可能有体积大于盒子容积的物品
51. if(pnVolume_of_items[0] > nVolume_of_box)  
52. return -1;  
54. // 物品体积等于盒子容积时，必然单独占一个盒子
55. for(i=0; pnVolume_of_items[i] == nVolume_of_box; i++)  
56.         ;  
58.     j = nNum_of_items-1;  
59. for(; i<j; i++)  
60.     {  
61. // 小物品和大物品的体积和若小于盒子容积，则小物品不单独使用盒子
62. if(pnVolume_of_items[i]+pnVolume_of_items[j] <= nVolume_of_box)  
63.             j--;  
64.     }  
66. if(i == j)  
67. return i+1;  
69. return i;  // i > j
70. }  
72. int main(void)  
73. {  
74. int nVolume_of_box;  //盒子的容积V
75. int nNum_of_items;   //物品的数量N
76. int *pnVolume_of_items; //N个物品的体积
77. int i;  
79.     scanf("%d", &nVolume_of_box);  //获取盒子容积
80.     scanf("%d", &nNum_of_items);   //获取物品数量
82.     pnVolume_of_items = (int*)malloc(nNum_of_items * sizeof(int)); //根据物品数量创建存储空间
83. for(i=0; i<nNum_of_items; i++)  
84.         scanf("%d", &pnVolume_of_items[i]); //挨个录入物品的体积(特别注意勿忘取地址符)
86.     printf("%d", calc_least_box_count(nVolume_of_box, nNum_of_items, pnVolume_of_items));  
88. return 0;  
89. }  

3、出租车计费（测试模拟题）

编程思路：

        分别以里程、时间为依据计算收费，取二者中的较大值。

代码实现：

[cpp] view plaincopyprint?

1. #include <stdio.h>
3. int main(void)  
4. {  
5. float fDistance; // 里程
6. int nTime;       // 时间
7. float fPrice1=6.0,fPrice2=6.0; // 两种不同计费方式的费用值
8. int n;  
10. // 获取输入的里程和时间
11.     scanf("%f %d", &fDistance, &nTime);  
13. if(fDistance<=2.0 && nTime<=10)  
14.         printf("6.0");  // 满足起步价条件，fPrice1=fPrice2=6.0
15. else
16.     {  
17. // 若里程数大于2公里，需要另外计算 fPrice1
18. if(fDistance>2.0)  
19.         {  
20.             n = (int)((fDistance-2.0)/0.5); // 显式取整，因为不足0.5公里不计费
21.             fPrice1 += n*0.7;  
23. // 若里程数大于7公里，需要附加返程费
24. if(fDistance>7.0)  
25.             {  
26.                 n = (int)(fDistance-7.0);   // 显式取整，因为不足1公里不计费
27.                 fPrice1 += n*0.7;  
28.             }  
29.         }  
31. // 若时间大于10分钟，需要另外计算 fPrice2
32. if(nTime>10)  
33.         {  
34.             n = (nTime-10)/3;  // 隐式取整，因为不足3分钟不计费
35.             fPrice2 += n*1.4;  
36.         }  
38. // 打印两种计费方式产生的费用值中的较大值
39.         printf("%.1f", fPrice1>fPrice2?fPrice1:fPrice2);  
40.     }  
42. return 0;  
43. }