华为机试历年试题【part3】

时间:2022-06-07 15:47:30

 一、数组比较

题目简介:

比较两个数组,要求从数组最后一个元素开始逐个元素向前比较,如果2个数组长度不等,则只比较较短长度数组个数元素。请编程实现上述比较,并返回比较中发现的不相等元素的个数

比如:

数组{1,3,5}和数组{77,21,1,3,5}按题述要求比较,不相等元素个数为0

数组{1,3,5}和数组{77,21,1,3,5,7}按题述要求比较,不相等元素个数为3

• 要求实现函数:

int array_compare(int len1, int array1[], int len2, int array2[])

【输入】 int len1:输入被比较数组1的元素个数;

int array1[]:输入被比较数组1;

int len2:输入被比较数组2的元素个数;

int array2[]:输入被比较数组2;

【输出】 无

【返回】 不相等元素的个数,类型为int

• 示例

1) 输入:int array1[] = {1,3,5},int len1 = 3,int array2[] = {77,21,1,3,5},int len2 = 5

函数返回:0

2) 输入:int array1[] = {1,3,5},int len1 = 3,int array2[] = {77,21,1,3,5,7},int len2 = 6

函数返回:3

题目解答:
比较简单,看看代码就懂了,不赘述。 完整代码:http://www.anycodex.com/blog/?p=232

 二、约瑟夫环问题

题目简介:

输入一个由随机数组成的数列(数列中每个数均是大于0的整数,长度已知),和初始计数值m。从数列首位置开始计数,计数到m后,将数列该位置数值替换计数值m,并将数列该位置数值出列,然后从下一位置从新开始计数,直到数列所有数值出列为止。如果计数到达数列尾段,则返回数列首位置继续计数。请编程实现上述计数过程,同时输出数值出列的顺序

比如: 输入的随机数列为:3,1,2,4,初始计数值m=7,从数列首位置开始计数(数值3所在位置)

第一轮计数出列数字为2,计数值更新m=2,出列后数列为3,1,4,从数值4所在位置从新开始计数

第二轮计数出列数字为3,计数值更新m=3,出列后数列为1,4,从数值1所在位置开始计数

第三轮计数出列数字为1,计数值更新m=1,出列后数列为4,从数值4所在位置开始计数

最后一轮计数出列数字为4,计数过程完成。

输出数值出列顺序为:2,3,1,4。

• 要求实现函数:

void array_iterate(int len, int input_array[], int m, int output_array[])

【输入】 int len:输入数列的长度;

int intput_array[]:输入的初始数列

int m:初始计数值

【输出】 int output_array[]:输出的数值出列顺序

【返回】 无

• 示例

输入:int input_array[] = {3,1,2,4},int len = 4, m=7

输出:output_array[] = {2,3,1,4}


题目解答:

我觉得这道题目,关键在于考察实习生对基础知识的熟悉程度吧。如果是对循环链表很熟的话,短时间就能把这道题写完。就我写代码的工作量而言,反正我大部分时间都是花在了循环链表的构造上。所以有人说对于这些基础的程序,最好能锻炼到手写几分钟就能写出来的程度,包括排序啊之类的。话不多说吧,说说思考的过程吧。

1、构造循环链表

2、设置一个计数变量,从循环链表的入口(本例中为3所在的节点),开始计数。当计数器的值等于m时,我们需要打印该节点的值删除这个节点链表长度减一更改开始计数的位置计数器清零。为了删除该节点,我们需要设置一个变量来保存被删节点的前一节点;

3、注意释放申请的内存空间。

其他的就没什么了,结合代码看吧。

完整代码请见:http://www.anycodex.com/blog/?p=241


 三、简单四则运算

题目简介:

输入一个只包含个位数字的简单四则运算表达式字符串,计算该表达式的值
注: 1、表达式只含 +, -, *, / 四则运算符,不含括号
2、表达式数值只包含个位整数(0-9),且不会出现0作为除数的情况
3、要考虑加减乘除按通常四则运算规定的计算优先级
4、除法用整数除法,即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生
5、输入字符串一定是符合题意合法的表达式,其中只包括数字字符和四则运算符字符,除此之外不含其它任何字符,不会出现计算溢出情况
• 要求实现函数:
int calculate(int len, char *expStr)
【输入】 int len: 字符串长度;
char *expStr: 表达式字符串;
【输出】 无
【返回】 计算结果

• 示例
1) 输入:char *expStr = “1+4*5-8/3”
函数返回:19
2) 输入:char *expStr = “8/3*3”
函数返回:6

题目解答:

定义两个栈(用vector来模拟),一个叫OS,专门存储操作符;另外一个叫NS,专门存储数据。主要过程如下:

1、遇见数据,直接压入NS栈;

2、遇见操作符,如果是第一个的话,直接压入OS栈;

3、遇见操作符(非第一次遇见),和OS栈栈顶的操作符进行优先级比较,若小于等于栈顶的操作符优先级,则去NS栈顶的两个元素进行运算。运算过后,将NS栈顶参与运算的两个元素pop出来,将运算结果push进去,此外还需将OS栈栈顶的操作符pop出去。接着再讲操作符和OS新的栈顶进行优先级比较,若小于或等于则重复前面的步骤,若大于则压入OS栈。

注意:循环的范围是从输入字符串开始到‘\0’结束。意味着我们将\0也当着一个操作符,只不过它的优先级最低。

优先级: */   > +- > ‘\0′

具体过程,请见下图:

华为机试历年试题【part3】

完整代码http://www.anycodex.com/blog/?p=246

测试平台(www.anycodex.com

欢迎留言交流。