校招回顾录---华为篇(下)

2015届[2014年夏]华为公司校招机试中级题试水

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

写在前面：

        当前华为公司的一次机试。共三道不同难度的编程题（当中，0基础题60分、中级题100分、高级题160分），机试成绩>=60就可以參加下一轮面试。

一定程度上说。仅仅要全然做对0基础题，就行通过机试的考验。可是，可以部分或全然完毕后面的中高级题，一定会为你后面的面试增色不少。

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

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

1、逆序链表输出（測试模拟题）

描写叙述:	输入一个单向链表，将链表逆序后输出各结点的值。 链表结点结构定义例如以下： typedef struct tagListNode {     int value;     struct tagListNode *next; }ListNode;
执行时间限制:	60 Sec
内存限制	256 MByte
输入:	顺序输入链表的各结点，用逗号(",")作为结点数据的分隔符； 比如：链表1->2->3->4->5，输入为："1,2,3,4,5"
输出:	逆序后链表的各结点，用逗号(",")作为结点数据的分隔符； 比如上述链表逆序后为5->4->3->2->1。输出为："5,4,3,2,1"
例子输入:	1,2,3,4,5
例子输出:	5,4,3,2,1

编程思路：

        遍历原链表，对每一个结点：记录前一个被遍历的结点(即其前驱结点，需额外开辟空间)、当前结点、当前结点的后继；令当前结点的前驱结点变为其后继结点。当前结点的后继结点变为新的当前结点。对链表的第一个和最后一个结点特殊处理。

代码实现：

#include <stdio.h>
#include <stdlib.h>

// 链表结点结构
typedef struct tagListNode
{
    int value;
    struct tagListNode *next;  //后继结点指针
}ListNode;

// 创建一个新的链表结点
//參数 ppstNode，指向新结点指针的指针
//參数 nValue，  新结点的值(整数形式)
void new_node_create(ListNode **ppstNode, int nValue)
{
    *ppstNode = (ListNode*)malloc(sizeof(ListNode));
    (*ppstNode)->value = nValue;
    (*ppstNode)->next  = NULL;
}

// 创建一个新的链表结点并将其附加到指定链表的尾部
//參数 ppstTail，指向链表最后一个结点指针的指针
//參数 pValue，  新结点的值(字符串形式)
void new_node_append(ListNode **ppstTail, char *pValue)
{
    ListNode *pstNow;

    new_node_create(&pstNow, atoi(pValue));
    (*ppstTail)->next = pstNow;
    *ppstTail = pstNow;
}

// 依据标准输入的内容创建链表
//參数 ppstTail，指向链表头结点的指针的指针
void list_create(ListNode **ppstHead)
{
    ListNode *pstTail;
    char szInput[100];
    char *p;
    int i;

    // 读入标准输入
    scanf("%s", szInput);
    // 依据标准输入的内容创建链表
    pstTail = *ppstHead;
    p = szInput;
    for(i=0; szInput[i]!=''; i++)
    {
        if(szInput[i]==',')
        {
            szInput[i]='';
            // 创建新结点，并将其加入到链表尾部
            new_node_append(&pstTail, p);
            p = szInput+i+1;
        }
    }
    // 对最后一个无逗号结尾的结点单独处理
    new_node_append(&pstTail, p);
}

// 链表逆置
//參数 ppstTail。指向链表头结点的指针的指针
void list_reverse(ListNode **ppstHead)
{
    ListNode *pstNow, *pstPrev, *pstNext;  //当前结点、前驱结点、后继结点

    pstNow = (*ppstHead)->next;  //当前结点初始化为单链表的第一个结点
    pstPrev = *ppstHead;         //前驱结点初始化为头结点
    while(pstNow!=NULL)
    {
        //保存当前结点的后继结点
        pstNext = pstNow->next;

        if(pstPrev == *ppstHead)
            pstNow->next = NULL;     //原单链表的第一个结点逆置后的后继指针为空
        else
            pstNow->next = pstPrev;  //原单链表的其它结点的前驱结点变为其后继结点

        pstPrev = pstNow;  //下一个结点的前驱结点为当前结点
        pstNow = pstNext;  //下一个结点变为当前结点
    }
    (*ppstHead)->next = pstPrev;  //原单链表的最后一个结点变为逆置后的第一个结点，亦即头结点的后继结点
}

// 链表元素遍历打印
//參数 ppstTail，指向链表头结点的指针的指针
void list_print(ListNode **ppstHead)
{
    ListNode *pstNow;

    pstNow = (*ppstHead)->next;
    while(pstNow->next!=NULL)
    {
        printf("%d,", pstNow->value);
        pstNow = pstNow->next;
    }
    printf("%d", pstNow->value);  //最后一个结点后木有逗号
}

// 链表释放
//參数 ppstTail。指向链表头结点的指针的指针
void list_free(ListNode **ppstHead)
{
    ListNode *pstNow, *pstNext;

    pstNow = (*ppstHead)->next;
    while(pstNow!=NULL)
    {
        pstNext = pstNow->next;
        free(pstNow);
        pstNow = pstNext;
    }
}

int main(void)
{
    ListNode *pstHead;

    // 创建头结点
    new_node_create(&pstHead, 0);
    // 依据标准输入的内容创建链表
    list_create(&pstHead);
    //printf("After create : ");   //提交的时候一定注意把这些调试输出删除或凝视掉
    //list_print(&pstHead);        //提交的时候一定注意把这些调试输出删除或凝视掉

    // 链表逆置
    list_reverse(&pstHead);
    //printf("
After reverse: "); //提交的时候一定注意把这些调试输出删除或凝视掉
    list_print(&pstHead);

    // 链表释放
    list_free(&pstHead);

    return 0;
}

2、心有灵犀一点通

描写叙述:	在某相亲节目现场。有n(1≤n≤500)对善男俊女,为測试男女两方心有灵犀程度,主持人想出了一个非常有意思的游戏：主持人在地上画出一排(共2n个)格子，每一个格子里都写着一个整数Ai(1≤Ai≤500)。游戏開始后，让他们随意地站成一排(可能会有两个人站在了同一个格子里)。等他们都站好以后，司仪開始计算他们每一个人自己的得分，记分规则是：男方的分数等于把从自己所站的位置開始一直累加到开头。女方的分数等于从自己所站位置開始一直累加到末尾。假设某一对男女的得分数是同样的，那他们得默契度较高,比較有缘,交友成功率也高。 比方，有3对男女，地上的那一排数字为:3，6，2。4，5，2。假设男方站在第三个位置(2)，他的得分为：3+6+2=11。女方站在第4个位置(4)，她的得分为4+5+2=11。两人得分同样，就觉得两人非常有默契。或者男方站第6个位置(2)。女方站第1个位置(3)，他们的得分都等于22。也非常有默契。假设你朋友在节目现场。那么请你帮他/她算一算有多少种站法能够迅速有机会找到那个默契的她/他（參数不合法返回-1）。
执行时间限制:	无限制
内存限制	无限制
输入:	第一行一个整数n，代表善男信女的对数。 第二行有一批整数N。代表地上的数字。注意：假设N不等于2*n，输出-1。
输出:	输出共同拥有几种站法。 输入数据不合法，输出-1。
例子输入:	3 3 6 2 4 5 2
例子输出:	2

编程思路：

        我理解的题意。是算一对男女的默契度。

依据题意，男方和女方都有可能出如今2n个格子的随意一个中。

        先分别穷举计算男/女方在这2n个格子中的随意一个格子时。他/她的得分；然后用一个双重循环。外循环遍历男方的2n个可能的位置，内循环遍历女方的2n个可能的位置。当男女两方的得分同样时，可能的站法计数加一。

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LATTICE_MAX_NUM 1000

// 计算男方站在某格子上时的分数
int score_calc_man(int *pLatticeList, int nPos)
{
    int i, nScore=0;

    for(i=0; i<=nPos; i++)
        nScore = nScore += pLatticeList[i];

    return nScore;
}

// 计算女方站在某格子上时的分数
int score_calc_lady(int *pLatticeList, int nPos, int nListSzie)
{
    int i, nScore=0;

    for(i=nPos; i<nListSzie; i++)
        nScore = nScore += pLatticeList[i];

    return nScore;
}

// 计算默契的站法计数
int privity_calc(int *pLatticeList, int nListSzie)
{
    int nManScoreList[LATTICE_MAX_NUM];   // 男方在这2n个格子中的随意一个格子时，他的得分
	int nLadyScoreList[LATTICE_MAX_NUM];  // 女方在这2n个格子中的随意一个格子时。她的得分
	int i,j, nCount=0;

	for(i=0; i<nListSzie; i++)
	{
	    nManScoreList[i]  = score_calc_man(pLatticeList, i);
	    nLadyScoreList[i] = score_calc_lady(pLatticeList, i, nListSzie);
	}

	for(i=0; i<nListSzie; i++)
	{
	    for(j=0; j<nListSzie; j++)
	    {
	        if(nLadyScoreList[j] == nManScoreList[i])
                nCount++;
	    }
	}

	return nCount;
}

int main(void)
{
    int nCoupleCount;  //多少对男女
	int nLatticeList[LATTICE_MAX_NUM]; //格子里的数值
	int nListSzie = 0; //多少个格子
	int i,nTemp;
	char szInput[4096];
	char *pTemp;

	// 读入男女对数
	scanf("%d", &nCoupleCount);
	if(nCoupleCount<1 || nCoupleCount>500) // 输入合法性判定，1≤n≤500
	{
		printf("%d", -1);
		return -1;
	}

	// 读入格子里的数值
	fflush(stdin);  //务必清空输入缓冲区。否则后面的fgets,gets会直接获取前一个scanf遗留的换行符。而不会又一次等待输入
	fgets(szInput, sizeof(szInput), stdin);  //用 gets(szInput) 面临溢出的危急

	pTemp = szInput;
	nListSzie = 0;
	for(i=0; szInput[i]!=''; i++)
	{
		if(szInput[i]==' ')
		{
			szInput[i]='';
			nTemp = atoi(pTemp);
			if (nTemp<1 || nTemp>500) // 输入合法性判定，1≤Ai≤500
			{
				printf("%d", -1);
				return -1;
			}
			nLatticeList[nListSzie++] = nTemp;
			pTemp = szInput+i+1;
		}
	}
	nTemp = atoi(pTemp);
    if (nTemp<1 || nTemp>500) // 输入合法性判定。1≤Ai≤500
    {
        printf("%d", -1);
        return -1;
    }
    nLatticeList[nListSzie++] = nTemp;

	if(nListSzie != nCoupleCount*2) // 输入合法性判定，N等于2*n
	{
		printf("%d", -1);
		return -1;
	}

	printf("%d", privity_calc(nLatticeList, nListSzie));

	return 0;
}

3、洞穴逃生

描写叙述:	精灵王子爱好冒险，在一次探险历程中。他进入了一个神奇的山洞。在洞穴深处，精灵王子不小心触动了洞穴内暗藏的机关，整个洞穴将非常快塌陷，精灵王子必须尽快逃离洞穴。 精灵王子的跑步速度为17m/s，以这种速度可能是无法逃出洞穴的。庆幸的是精灵王子拥有闪烁法术，可在1s内移动60m。只是每次使用闪烁法术都会消耗魔法值10点。精灵王子的魔法值恢复的速度为4点/s。仅仅有处在原地歇息状态时才干恢复。 如今已知精灵王子的魔法初值M，他所在洞穴中的位置与洞穴出口之间的距离S，距离洞穴塌陷的时间T。 你的任务是写一个程序帮助精灵王子计算怎样在最短的时间内逃离洞穴。 若能逃出，输出"Yes"，并输出逃出所用的最短时间。若不能逃出。则输出"No"，同一时候输出精灵王子在剩下的时间内能走的最远距离。注意字母大写和小写。注意:精灵王子跑步、闪烁或歇息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。 注：M、S、T均是大于等于0的整数。由输入保证取值合法性，考生不用检查。 提醒： 假设输入的S为0，则说明本身已经在出口。输出应为：Yes 0 假设输入的T为0（且S不为0），则说明已经没有时间了，输出应为：No 0
执行时间限制:	无限制
内存限制	无限制
输入:	M S T
输出:	Yes 逃出洞穴所用的最短时间 或 No 在洞穴塌陷前能逃跑的最远距离
例子输入:	10 50 5
例子输出:	Yes 1

编程思路：

        贪心思想，每一秒都选择能够走最远的距离的方法。所以我们每次採用两种方法来前进。最后选择能走最远的那个方法。

代码实现：

可參见：http://blog.csdn.net/xiaozhuaixifu/article/details/25302069