美團網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;
}

更多精彩內容請看下一頁：http://www.linuxidc.com/Linux/2013-09/90680p2.htm