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

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

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

第一题

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

典型的数学概率题(好吧，说明数学还是很重要滴，大家去笔试面前还是巩固一下概率比较好，恩)，这里假设无穷多次后正面朝上的比例为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;
}

更多精彩内容请看下一页：