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

题目是在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, Jr的Hacker's Delight（中文名叫算法心得）里面的位计数一章里面提到过IBM的Stretch计算机跟SPARCv9架构的CPU有一个能实现“种群计数”函数（population count）的指令，这个“种群计数”就是统计数组中值位“1”的个数。在非Stretch计算机非SPARCv9架构的CPU中，使用的是分治策略来统计“1”的个数。这个分治法，就是上述问题的函数所描述的算法。

2、具体分析

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

上图中为把奇数位的“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)

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