美团网2014校招笔试题及解答(长沙站+哈尔滨站)

作者：寒小阳
时间：2013年9月。
出处：http://blog.csdn.net/han_xiaoyang/article/details/11924701。
声明：版权所有，转载请注明出处，谢谢。

题目是网上找的，答案博主自己做的，有不当之处或者有更好的方法欢迎留言！

第一题

一堆硬币，一个机器人，如果是反的就翻正，如果是正的就抛掷一次，无穷多次后，求正反的比例（哈尔滨站）

典型的数学概率题(好吧，说明数学还是很重要滴，大家去笔试面前还是巩固一下概率比较好，恩)，这里假设无穷多次后正面朝上的比例为x,则反面朝上的比例为1-x；则再投递一次，根据题意，正面朝上的概率的就变成1-x+(1/2*x),，反面朝上的概率变为1/2*x.因为此时已经达到平衡的状态，则该次投递前后概率应该不变，即1-x=1/2*x。解得x为2/3

第二题

k链表翻转。给出一个链表和一个数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，用程序实现。

/*************************************************************************************************
/*首先，博主说明一下，博主不清楚k>链表长度的时候，题目的本意是让我们怎么处理的，博主这里直接没有做任何翻转，将原链表返回了。
**************************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
//定义链表节点
struct Node{
int data;
Node *next;
};
//函数在给定头结点和尾节点的情况下，对整个链表做翻转
void ReverseLinkList(Node *head,Node *end){
if(head==NULL||end==NULL) return;
Node *pre=NULL,*cur=head,*stop=end->next;
while(cur!=stop){
Node* nxt=cur->next;
cur->next=pre;
pre=cur;
cur=nxt;
}
}
//k链表翻转
Node* ReverseKLinkList(Node *head,int k){
if(head==NULL||k<=0) return NULL;
Node *cur=head;
for(int i=0;i<k-1;i++){
cur=cur->next;
if(cur==NULL)
    break;
}
//在链表长度小于k的情形下，直接返回原链表
if(cur==NULL) return head;
Node* begin=cur->next,*end=begin;
Node* pre=head;
ReverseLinkList(head,cur);
while(begin!=NULL){
for(int i=0;i<k-1;i++){
end=end->next;
if(end==NULL)
    break;
}
if(end==NULL){
pre->next=begin;
break;
}
else{
Node *nextbegin=end->next;
ReverseLinkList(begin,end);
pre->next=end;
pre=begin;
begin=end=nextbegin;
}
}
return cur;
}
int main(){
int a[]={0,,1,2,3,4,5,6,7,8,9,10,11};
Node* node[12];
for(int i=0;i<12;i++){
node[i]=new Node;
node[i]->next=NULL;
node[i]->data=a[i];
}
for(int i=0;i<11;i++){
node[i]->next=node[i+1];
}
Node *tmp=ReverseKLinkList(node[0],4);
for(;tmp!=NULL;tmp=tmp->next){
cout<<tmp->data<<endl;
}
system("pause");
return 0;
}

第三题

有ABCD死人要在夜里过一座桥，他们通过这座桥分别需要耗时1,2,5,10分钟，现在只有一只手电，过桥时必须要带着手电，并且同时最多只能两个人一起过桥。请问如何安排能够让四个人尽快都过桥。（长沙站）

如果博主没有记错的话，这是腾讯几年前考过的一道题，一到校招时，就发现各大公司笔试题抄来抄去，好吧，停止吐槽。这种智力题一向是博主这样智力平庸人的硬伤，恩，直接上答案了。

第一步:A(1)和B(2)过桥，A(1)返回Cost：1+2s

第二步:C(5)和D(10)过桥，B(2)返回Cost：10+2s

第三步:A(1)和B(2)过桥Cost：2s

总共耗时3+12+2=17s

第四题

有25匹马，每匹马都以恒定的速度赛跑，当然马与马之间的速度是不相等的，总共有5个赛道，就是说每轮最多只能有5个马同时赛跑。问题是：要确定出跑的最快的前三名马，需要最少多少轮比赛？（长沙站）

不多说了，直接上答案吧。

总共需要7场
1）首先分5组比赛5次
(ABCDE)决出
A1A2A3A4A5
B1B2B3B4B5
C1C2C3C4C5
D1D2D3D4D5
E1E2E3E4E5
2）再比赛1次
A1B1C1D1E1比赛
至少可以淘汰2组
假设A1>B1>C1>D1E1
则最快的必然是A1A2A3B1B2C1中的3批
A1已经确定有
3）则最后一场对A2A3B1B2C1进行比较，选出前2名

第五题

在有团购之前，大家都是现场买门票的，公园的门票是5元；某天售票处开门时没有准备零钱。假设一天来购票的一次有2N个人，其中有N个人有5元零钱，其它N个人只有10元面值的钱；假设每人只买一张票。请问任何人都不必为找零而等待的概率是多少？(长沙站)

这道题，好吧，博主的第一反应是：这是标准的Catalan数的应用吧！（好吧，打算随后拿一篇出来介绍下Catalan数），博主奇怪的是，美团今年的校招题，肿么数学题这么多-_-||

隐隐约约记得这道题貌似《编程之美》上也有，为了将问题简单化，将持有5元的人看成1，持有10元的人看成0，这样，只要满足：在任何0位置之前，1的数目多于0的数目，就能满足要求，则该题求解的为满足要求的排列占全部排列的比例。

1）求2n个1和0的全排列数目：C(2n,n)，即从2n个位置中选取n放置0（或者1）。

2）求取不满足要求的组合数（合法的组合数不好求）：

不满足要求的组合数的特点：总能找到一个位置K，使得0的数目比1的数目多1。那么很明显，k后面的0的数目比1的数目要少1.（为什么要找位置k？因为，我要让前面K个位置0、1排列不管怎么排列都不合法）

此后，我们关注k位置后面的排列：因为k后面的排列中，明显0比1少，那么我们可以将0和1互换（为什么要互换？首先，0、1互换后，两种排列方式的总数目是不变的，其次，互换后的排列中0比1多1个，那么不管怎么排列，都不合法），这样互换后2n个数的排列不管怎么排列都不合法（值得注意的是，互换后的组合排列数目，和互换前的是相同的，因为前面的排列不变且后面排列组合方式的数目一样。

现在来计算互换后排列的数目：互换后排列的数目中0为n+1个，1为n-1个，那么组合数就相当于从2n个位置选取n+1个位置放0，即为C（2n,n+1）

所求结果为(C(2n,n)-C(2n,n+1))/C(2n,n)

第六题

有一个函数“intf(intn)”，请编写一段程序测试函数f(n)是否总是返回0，并添加必要的注释和说明。

这一题博主木有明确的思路，感觉上黑盒测试的话只能从INT_MIN到INT_MAX全部测试了，或者加上随机算法，抽样检测。大家有好的方法欢迎留言。

第七题

用你熟悉的语言编写程序用两个栈(Stack)模拟队列(Queue)的先进先出操作，仅实现add、remove方法即可。（长沙站）

非常非常经典的一道老题了，假设两个栈s1和s2，且都为空。可以认为栈s1提供入队列的功能，栈s2提供出队列的功能。

1）入队列：入栈s1。

2）出队列：如果栈s2不为空，直接弹出栈s2的数据；如果栈s2为空，则依次弹出栈s1的数据，放入栈s2中，再弹出栈s2的数据。

#include <iostream>
#include <stack>
using namespace std;
template<class T>
struct MyQueue
{
    void add(T &t)
    {
        s1.push(t);
    }
    T front()
    {
        if(s2.empty())
        {
            if(s1.size() == 0) throw;
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }
    void remove()
    {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        if(!s2.empty())
            s2.pop();
    }
    stack<T> s1;
    stack<T> s2;
};
int main()
{
    MyQueue<int> mq;
    for(int i=0; i< 10; ++i)
    {
        mq.add(i);
    }
    for(i=0; i< 10; ++i)
    {
        cout<<mq.front()<<endl;
        mq.remove();
    }
    return 0;
}

第八题

编写函数，获取两段字符串的最长公共子串的长度，例如：

S1=GCCCTAGCCAGDE

S2=GCGCCAGTGDE

这两个序列的最长公共字串为GCCAG，也就是说返回值为5.(长沙站)

说实话，一直以来见着的都是让求最长公共子序列，突然让求最长公共字串，反倒有些不习惯了，总觉得考最长公共子序列更合理一点吧，好吧，又看了一遍题，确实是求最长公共子串的长度。

为了说清楚一点，就用上面的例子吧，我们来列一张表，如下：

GCCCTAGCCAGDE

G1000001000100

C0111000110000

G1000001000100

C0111000110000

C0111000110000

A0000010001000

G1000001000100

T0000100000000

G1000001000100

D0000000000010

E0000000000001

则最长公共子串GCCAG为上图中标出的最长斜对角线

博主在下面先写一种最容易看懂的方法，这种方法的空间复杂度还可以再优化，不过这个问题，之后等博主写到最长公共子序列、最长公共字串和最长递增子序列专题的时候再写吧。

#include<stdio.h>
#include<string.h>
#define N 100
 
//LCS问题：即求两个字符串最长公共子串的问题，这里返回了公共字串，如果只求最长公共字串长度的话，之后有个简单的程序，其实就是里面的一部分
char *LCS(char *a,char *b) 
{
int len_a = strlen(a);  //获取字串的长度 
int len_b = strlen(b);
char *p;
int c[N][N] = {0};      //矩阵c记录两串的匹配情况 
int start,end,len,i,j;  //start表明最长公共子串的起始点，end表明最长公共子串的终止点 
end = len = 0;          //len表明最长公共子串的长度 
for(i=0;i<len_a;i++)    //串开始从前向后比较 
{
for(j=0;j<len_b;j++)
{
if(a[i] == b[j])
if(i == 0 || j == 0)
c[i][j] = 1;
else
c[i][j] = c[i-1][j-1] + 1;
if(c[i][j] > len)
{
len = c[i][j];
end = j;
}
}
}
start = end - len + 1;
p = (char *)malloc(len+1); //数组p记录最长公共子串 
for(i=start;i<=end;i++)
p[i-start] = b[i];
p[len] = '\0';
for(j=0;j<len_b;j++)
{
for(i=0;i<len_a;i++)
printf("%2d",c[i][j]); 
printf("\n");
}
return p;
}
int main(int argc,char *argv[])
{
char str1[N],str2[N];
printf("请输入字符串1：");
gets(str1);
printf("请输入字符串2：");
gets(str2);
printf("最长子串为：%s\n",LCS(str1,str2));
return 0;
}

//只求最长公共字串长度
int LCS(char *a,char *b) 
{
int len_a = strlen(a);  //获取字串的长度 
int len_b = strlen(b);
char *p;
int c[N][N] = {0};      //矩阵c记录两串的匹配情况 
int start,end,len,i,j;  //start表明最长公共子串的起始点，end表明最长公共子串的终止点 
end = len = 0;          //len表明最长公共子串的长度 
for(i=0;i<len_a;i++)    //串开始从前向后比较 
{
for(j=0;j<len_b;j++)
{
if(a[i] == b[j])
if(i == 0 || j == 0)
c[i][j] = 1;
else
c[i][j] = c[i-1][j-1] + 1;
if(c[i][j] > len)
{
len = c[i][j];
end = j;
}
}
}
return len;
}

第九题

有100盏灯，从1~100编上号，开始时所有的灯都是关着的。
第一次，把所有编号是1的倍数的灯的开关状态改变一次；
第二次，把所有编号是2的倍数的灯的开关状态改变一次；
第三次，把所有编号是3的倍数的灯的开关状态改变一次；
以此类推，直到把所有编号是100的倍数的灯的开关状态改变一次。
问，此时所有开着的灯的编号。（哈尔滨站）

由于最开始灯是灭的，那么只有经过奇数次改变开关状态的灯是亮的。根据题意可知一个数字有多少约数就要开关多少次，所以最后亮着的灯的数学解释就是：灯的编号有奇数个不同的约数。
一个数的约数按出现的奇偶个数分为以下两种：
q约数是成对出现的，比如8的约数对为：（1，8）、（2，4）。
q约数是单个出现的，比如36的约数对为：（1，36）、（2，18）、（3，12）、（4，9）、（6）。
可以看出6自己单独是36的约数，而不是和别的数连在一起。所以只有平方数才会有奇数个整型约数，才满足本题的要求。从1到100的平方数为：
1，4，9，16，25，36，49，64，81，100。
所以只有这些灯是亮的。