2015华为校园招聘机试题+1道2013年网易校园招聘笔试题

时间:2021-08-28 23:43:34

题目是在hackbuteer1的专栏上看到的(http://blog.csdn.net/hackbuteer1),代码跟题目分析是原创的。

转载注明出处,原文地址:http://blog.csdn.net/powerwoo25/article/details/47380677


2015华为校招机试题


第一题:拼音转数字
输入是一个只包含拼音的字符串,请输出对应的数字序列。转换关系如下:
描述:      拼音        yi  er  san  si  wu  liu  qi  ba  jiu
      阿拉伯数字        1   2   3      4   5    6    7   8   9
输入字符只包含小写字母,所有字符都可以正好匹配

运行时间限制:无限制
内存限制:       无限制
输入:              一行字符串,长度小于1000
输出:              一行字符(数字)串
样例输入:       yiersansi
样例输出:       1234


思路:顺序遍历字符串,逐一判断拼音首字母(个别需要判断第二个字母)输出对应数字字符

<span style="font-family:Verdana;font-size:18px;">转载注明出处,原文地址:http://blog.csdn.net/powerwoo25/article/details/47380677</span>
#include <stdio.h>

void Solve(char *arr)
{
if(arr == NULL)
{
perror("Invalid input array!\n");
return;
}

while(*arr != '\0')
{
switch(*arr)
{
case 'y':
arr += 2;
printf("1");
break;
case 'e':
arr += 2;
printf("2");
break;
case 's':
if(*(arr+1) == 'a')
{
arr += 3;
printf("3");
break;
}
else
{
arr += 2;
printf("4");
break;
}
case 'w':
arr += 2;
printf("5");
break;
case 'l':
arr += 3;
printf("6");
break;
case 'q':
arr += 2;
printf("7");
break;
case 'b':
arr += 2;
printf("8");
break;
case 'j':
arr += 3;
printf("9");
break;
}
}
printf("\n");
}

int main()
{
char inputArr[1000];

while(~scanf("%s", inputArr))
{
Solve(inputArr);
}

return 0;
}

第二题:去除重复字符并排序
运行时间限制:无限制
内容限制:       无限制
输入:              字符串
输出:              去除重复字符并排序的字符串
样例输入:       aabcdefff
样例输出:       abcdef

思路:顺序遍历字符串,将字符hash到数组中并存储对应值数组初始化为0,检查到一个字符将相应位的赋为1,如果已经赋有值则跳过),再按数组下标(字符顺序)依次打印字符


<span style="font-family:Verdana;font-size:18px;">转载注明出处,原文地址:http://blog.csdn.net/powerwoo25/article/details/47380677</span>
#include <stdio<span style="font-family:Verdana;">.h</span>>
#include <memory.h>

void HashCount(char *inputArr)
{
if(inputArr == NULL || *inputArr == '\0')
{
perror("Invalid input array!");
return;
}

int countArr[257];
memset(countArr, 0, sizeof(countArr));

int len = strlen(inputArr);

for(int i = 0; i < len; i++)
{
if(countArr[(int)inputArr[i]] == 0)
{
countArr[(int)inputArr[i]] = 1;
}
}
for(int i = 0; i < 256; i++)
{
if(countArr[i])
{
putchar(i);
}
}

return;
}

int main()
{
char arr[256] = {};

  while(~scanf("%s", arr))
{
HashCount(arr);
}

  return 0;
}


第三题:等式变换
输入一个正整数X,在下面的等式左边的数字之间添加+号或者-号,使得等式成立。
1 2 3 4 5 6 7 8 9 = X
比如:
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序,统计满足输入整数的所有整数个数。
输入:       正整数,等式右边的数字
输出:       使该等式成立的个数
样例输入:5
样例输出:21

思路:遇到这种情况,办法是暴力尝试所有的符号组合(不知道是不是有什么数学方法可以解决?)。一般都是递归填满所有运算符(包括表示无运算符的’ ‘)下面的代码是用了递归全排列,一次递归填一次符号,在递归函数体里面进行阶段性的结果计算进行到最后一个数字后判断输出具体见代码注释。


<span style="font-family:Verdana;font-size:18px;">转载注明出处,原文地址:http://blog.csdn.net/powerwoo25/article/details/47380677</span>
#include <cstdio>
#include <iostream>

using namespace std;

const char sym[3] = {' ', '+', '-'};
int target = 0, hitCount = 0, flag = 1;
char opts[10];

/*
* lastSum,curRes分别保存上一个符号之前的计算结果与当前的数字结果,
* 如1+2+345搜索到4的时候lastSum保存1+2+3的结果,curRes保存34
* flag保存正负号相关的计算因子
*/
void RecursivePermutation(int lastSum, int curRes, char curOpt, int curNum)
{
/* 这行代码用于记录结果运算符*/
opts[curNum] = curOpt;

if(curOpt == sym[0])
{
curRes = curRes * 10 + flag * curNum;
}
else
{
lastSum += curRes;
flag = (curOpt == sym[1]) ? 1 : -1;
curRes = flag * curNum;
}

if(curNum == 9)
{
lastSum += curRes;
if(lastSum == target)
{
++hitCount;
/* 这段代码用于打印结果式子进行对照 */
for(int i = 1; i <= 9; i++)
{
if(opts[i] != ' ')
{
cout << opts[i];
}
cout << i;
}
cout << endl;
}
lastSum = curRes = 0;
flag = 1;
}
else
{
for(int i = 0; i < 3; i++)
{
int newNum = curNum + 1;
RecursivePermutation(lastSum, curRes, sym[i], newNum);
}
}
}

int main()
{
cin >> target;

 Recursive_permutation(0, 0, ' ', 1);

  cout << hitCount << endl;
}



2013网易校招笔试题

请问func(0x7f530829)的返回值是()。答案是15,是一个关于统计二进制i的1的个数的函数。

    int func(unsigned int i)  
{
unsigned int temp = i;
temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa)>>1);
temp = (temp & 0x33333333) + ((temp & 0xcccccccc)>>2);
temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0)>>4);
temp = (temp & 0xff00ff) + ((temp & 0xff00ff00)>>8);
temp = (temp & 0xffff) + ((temp & 0xffff0000)>>16);
return temp;
}


1、算法起源

Herry.S.Warren, JrHacker's Delight(中文名叫算法心得)里面的位计数一章里面提到过IBM的Stretch计算机跟SPARCv9架构的CPU有一个能实现“种群计数”函数(population count)的指令,这个“种群计数”就是统计数组中值位“1”的个数。在非Stretch计算机非SPARCv9架构的CPU中,使用的是分治策略来统计“1”的个数。这个分治法,就是上述问题的函数所描述的算法。

2、具体分析

2015华为校园招聘机试题+1道2013年网易校园招聘笔试题

       第一行为二进制数组,它代表一个数,也是代表一个二进制序列。将统计这个二进制序列的“1”的个数这个问题分解为统计二进制数组左半边“1”的个数与统计二进制数组右半边“1”的个数这两个子问题,就是一个分治的步骤。一直进行二分直到统计单位里面的数字个数为1个,然后开始归并求和(如上图所示)。第二行为统计第一行每2个二进制位“1”的个数之和的结果,第三行为统计第二行每4个二进制位“1”的个数之和...第五行统计为第四行每16个二进制位“1”的个数之和。

2015华为校园招聘机试题+1道2013年网易校园招聘笔试题

上图中为把奇数位的“1”跟偶数位的“1”都统计到了。用C语言来描述应该是如下代码:

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 1) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 1) & 0x0f0f0f0f);
x = (x & 0xff00ff) + ((x >> 1) & 0xff00ff);
x = (x & 0xffff) + ((x >> 1) & 0xffff);
       为什么不用题中那种更直观的写法? Henrry给出解释说,由于大部分带立即数的RISC指令都只支持16位常量,所以若某常数比较“大”,也就是16个位元无法容纳,则通常要先花两条指令将其载入寄存器,然后再参与其他运算。题中若写成(x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1),在计算到 x & 0xaaaaaaaa时,必须把先前装入寄存器中的“大常数”0x55555555取反,变成0xaaaaaaaa,然后再和x取与。若有"and not"指令,此操作可以一步完成,否则必须取反,再取与,这样就比(x >> 1) & 0x55555555多花一条指令了。(看到这里,给作者的细节优化跪了,ORZ)

       其实还有更丧心病狂的“种群计数”算法,不过已经进入了部分数学领域了,代码带有一些魔法数字,当然也更难懂。有空再介绍吧。