我来说说华为机试

受乔哥的启发，决定写一个关于华为机试的简介，首先声明本人并非大牛，也无权拿到华为的内部资料，以下内容大部分源自网络，还有一部分是自己的感悟，本文以整理和疏导为主。由于我不会JAVA，在这也就不写JAVA的东西了吧，下面的内容以C/C++为主。分为几个部分：第一部分是华为机试流程、题型等相关介绍，第二部分是一些经典题目的剖些，第三部分是一些提示和建议。一、华为机试介绍1.大致介绍时间：120分钟环境：VisualStudio(去年是vs2005)、VisualC++、Eclipse(Java)题量：共3题初级题——60分——3组测试数据中级题——100分——5组测试数据高级题——160分——8组测试数据注：初级题和中级题为必答题，高级题为附加题。提交次数：每题最多5次评判方式：按通过测试数据组数给分，每通过一组得20分2.考试说明这里有一个老版的机试考试说明，供大家参考：C/C++，JAVA机试流程：①打开IE浏览器，输入机试系统IP地址（以当天告知的地址为准）；②输入姓名、手机，选择“C/C++”或“JAVA”，登录；③登录后显示题目，阅读题目并点击页面最下方“下载框架文件”，将文件解压到D盘；④用VC6.0或Eclipse打开工程工程；⑤补充函数体、调试；⑥将工程压缩打包；⑦返回IE浏览器中的试题页面，点击最下方的“提交”按钮，完成提交。3.注意事项华为的机试阅卷为电脑自动阅卷，大致流程是输入测试数据，判断结果是否正确，所以，在编写好程序后，一定要多测试几组数据，至少要保证题目中测试数据输入后，结果符合题目要求。二、经典题目剖析1.在分析具体题目之前，有几个注意事项说一下：1）同学们平时写代码的编译环境不太一样，大致有GCC/G++，VC，VS，在这几种之中又细分了好多个版本，但是既然是准备华为机试，那么就装个最简单的VS2005吧，只要代码在这个版本上通过，相信机试的时候也不会出问题。2）现在很多新旧编程标准交织，这几年还有很实用的C++11，但是为了机试，这些还是先别秀吧，你问为什么有这么好的东西却不让用？因为VS2005不支持呗，类似的还有atoi(),itoa()这些局限于编译环境的函数也最好别用。2.机试的时候分为3类题：3）初级题——多为简单字符串处理或数字操作4）中级题——在考察编程语言能力的基础上加入一定简单的算法和数据结构。5）高级题——更多的算法和数据结构要求，代码量明显增大，栈、图、树、查找、搜索都在考察范围内。3.具体题目（以下所有代码本人均在VS2005环境上编译测试通过）1)排序方法总结题1:排序是编程语言里最基本的方法，目前典型的排序方法有：冒泡排序、快速排序、选择排序、简单插入排序、二分插入排序、希尔排序、归并排序等。既然是基础，那么就必然要了然于心。代码见：1.cpp（打开：Ctrl+鼠标左键点击）排序算法这么多，比较麻烦，但是思想一定要了然于心，说不定面试的时候就会让你写个排序算法看看呢？但是如果我们只是在程序中用到一个排序的功能，大可不必话费很长的时间去写这些排序算法，C++中给出了一个sort函数，非常方便，大家可以去了解一下，因为使用起来非常简单，并且在接下来的题目中会用到，在这就不多讲了。题2:输入10个数字，按各个位上的和从小到大排序，如果相同，则按数字从小到大排序。输入描述:10个正整数，保证都在int范围内，用空格隔开输出描述:10个数字，其从大到小的值，用空格隔开，最后一个数字后不加空格输入样例113245987106输出样例102113456789代码见：2.cpp题3:操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级50，用户任务的优先级=50且=255。优先级大于255的为非法任务，应予以剔除。现有一任务队列task[]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler实现如下功能，将task[]中的任务按照系统任务、用户任务依次存放到system_task[]数组和user_task[]数组中（数组中元素的值是任务在task[]数组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。例如：task[]={0,30,155,1,80,300,170,40,99}system_task[]={0,3,1,7,-1}user_task[]={4,8,2,6,-1}代码见：3.cpp题4:输入一组身高在170到190之间（5个身高），比较身高差，选出身高差最小的两个身高；若身高差相同，选平均身高高的那两个身高；从小到大输出；如：输入170181173186190输出170173代码见：4.cpp2）求最大、最小数题5:输入整型数组求数组的最小数和最大数之和，例如输入1,2,3,4则输出为5，当输入只有一个数的时候，则最小数和最大数都是该数，例如只输入1，则输出为2；数组的长度不超过50。代码见：5.cpp题6:输入一串字符，只包含“0-10”和“，”找出其中最小的数字和最大的数字（可能不止一个），输出最后剩余数字个数。代码见：6.cpp相信通过题2、题3，在找最大、最小数时，不论是数组还是字符类型都可以轻松应对了。3）链表题7：一组人（7个），围成一圈，从某人开始数到第3个的人出列，再接着从下一个人开始数，依次输出出列的人。（报数：共n个人从1编号，设从第s个人报号，报到m出队，依次输出出队的人。）代码见：7.cpp约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，这题既可以使用循环列表又可以使用数组在程序中两种方法都罗列了。题8：出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现。代码见：8.cpp如果这题能够轻松地写出，那么单项列表的知识就算是基本掌握了。4）大数、高精度数运算。题9:求两个长长整型的数据的和并输出。代码见：9.cpp题10:在计算机中，由于处理器位宽限制，只能处理有限精度的十进制整数加减法，比如在32位宽处理器计算机中，参与运算的操作数和结果必须在-231~231-1之间。如果需要进行更大范围的十进制整数加法，需要使用特殊的方式实现，比如使用字符串保存操作数和结果，采取逐位运算的方式。如下：9876543210+1234567890=?让字符串num1=9876543210，字符串num2=1234567890，结果保存在字符串result=11111111100。-9876543210+(-1234567890)=?让字符串num1=-9876543210，字符串num2=-1234567890，结果保存在字符串result=-11111111100。要求编程实现上述高精度的十进制加法。代码见：10.cpp上面两题，分别实现了正大数的加运算，大数的加运算，相信完全吃透后再编写大数运算的程序就不是问题了。题11:输入两行字符串正整数，第一行是被减数，第二行是减数，输出第一行减去第二行的结果。代码见：11.cpp5）字符串常见操作题12:通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。比如字符串“abacacde”过滤结果为“abcde”。代码见：12.cpp题13:通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。压缩规则：1.仅压缩连续重复出现的字符。比如字符串abcbc由于无连续重复字符，压缩后的字符串还是abcbc.2.压缩字段的格式为字符重复的次数+字符。例如：字符串xxxyyyyyyz压缩后就成为3x6yz代码见：13.cpp题14:删除子串，只要是原串中有相同的子串就删掉，不管有多少个都删除，返回子串个数。输入字符串为：123abc12de234fg1hi34j123k，子串为：123则输出为：abc12de234fg1hi34jk2代码见：14.cpp题15:将输入的字符串（字符串仅包含小写字母‘a’到‘z’），按照如下规则，循环转换后输出：a-b,b-c,…,y-z,z-a；若输入的字符串连续出现两个字母相同时，后一个字母需要连续转换2次。例如：aa转换为bc，zz转换为ab；当连续相同字母超过两个时，第三个出现的字母按第一次出现算。代码见：15.cpp题16：在给定字符串中找出单词（“单词”由大写字母和小写字母字符构成，其他非字母字符视为单词的间隔，如空格、问号、数字等等；另外单个字母不算单词）；找到单词后，按照长度进行降序排序，（排序时如果长度相同，则按出现的顺序进行排列），然后输出到一个新的字符串中；如果某个单词重复出现多次，则只输出一次；如果整个输入的字符串中没有找到单词，请输出空串。输出的单词之间使用一个“空格”隔开，最后一个单词后不加空格。代码见：16.cpp题17:字符串单词首字母转换成大写举例：输入：thisisabook返回：ThisIsABook代码见：17.cpp题18:通过键盘输入任意一个字符串序列，字符串可能包含多个子串，子串以空格分隔。请编写一个程序，自动分离出各个子串，并使用’,’将其分隔，并且在最后也补充一个’,’并将子串存储。如果输入“abcdefghid”，结果将是abc,def,gh,i,d。代码见：18.cpp题19:输入一个字符串，删除其中所有的数字，所有大写字母改成小写，其他不变，并输出。代码见：19.cpp题20：编写一个字符串替换函数，如：“ABCDEFGHIJKLMNOPQRSTUVWXYZ”这个字符串，把其中的“RST”替换为“ggg”这个字符串，结果就变成了：ABCDEFGHIJKLMNOPQgggUVWXYZ代码见：20.cpp题21:写一个程序实现功能：将两个字符串合并为一个字符串并且输出，用指针实现。代码见：21.cpp题22:给定一个字符串,实现一个函数,按下述方式输出字符串：如果此字符的下一个字符和此字符不一样，原样输出此字符，否则先输出此字符，再输出此字符连续出现的次数（次数不大于9）。例如,字符串ABBCCCDEDFFF，输出的结果为AB2C3DEDF3。不用考虑溢出问题，不能使用任何I/O函数。代码见：22.cpp题23:字符串匹配问题，给定两个字符串，求字符串2，在字符串1中的最先匹配结果。字符串2中可以存在'*'符号，且该符号可以代表任意字符，即字符串2中存在通配符。e.g.输入：abcdefghabef,a*f输出：abcdef代码见：23.cpp题24:输入m个字符串和一个整数n,把字符串M化成以N为单位的段，不足的位数用0补齐。如n=8m=9，123456789划分为：1234567890000000123化为：12300000代码见：24.cpp题25:统计字符串中数字出现的次数，最大次数的统计出来举例：输入：323324423343输出：3,6代码见：25.cpp题26:输入一段英文文本，用程序统计出现频率最高和最低的两个单词;英文文本中仅出现这四类字符：空格()、英文逗号(,)、英文句号(.)、英文大小写字母（a-z、A-Z）单词之间的分隔符仅考虑这三种：空格()、英文逗号(,)、英文句号(.);仅大小写不同的单词算同一个单词；如果两个单词出现次数相同，则在文本中首次出现的单词优先返回。返回的单词统一用小写字母返回例如：输入字符串“Helloworld,isaidhelloworldtotheworld”，返回“world”,“i”代码见：26.cpp题27:将整数倒序输出，剔除重复数据输入一个整数，如12336544，或1750，然后从最后一位开始倒过来输