美团点评研发工程师笔试卷-2012年

1、请找出下面代码中的所有错误。

说明：以下代码是把一个字符串倒序，如“abcd”倒序后变为“dcba” 

#include"string.h"
main()
　　{
　　 char*src="hello,world";
　　 char* dest=NULL;
　　 int len=strlen(src);
　　 dest=(char*)malloc(len);
　   char* d=dest;
　　 char* s=src[len];
　　 while(len--!=0)
　　     d++=s--;
　　 printf("%s",dest);
　　 return 0;
　}

2、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，用程序实现。

3、有一个随机数发生器，以概率P产生0，概率(1-P)产生1，请问能否利用这个随机数发生器，构造出新的发生器，以1/2的概率产生0和1。请写明结论及推理过程。

4、4个足球队打小组单循环，计分方式：胜3分平1分负0分，如果计分相同，则净胜球多的队伍排名靠前，如果净胜球还一样，则进球多的球队排名靠前。小组前两名出线。问可能出线的最低分数是多少。请说明推理过程。 备注：单循环赛是指所有参加比赛的队两两之间都比赛一次，最后按各队在全部比赛中的积分，得失分率排列名次。

5、从1到1000000的所有自然数，数字“1”一共出现了多少次？例：自然数101中，数字“1”出现了2次，自然数1011中，数字“1”出现了3次，请写明计算过程及结果。

6、以下代码功能：找出一个有序(字典序)字符串数组arr中值等于字符串v的元素的符号，如果有多个元素满足这个条件，则返回其中序号最大的。请找出下面代码中所有错误，直接在代码右侧空白处修改 。

Int bisearch(char**arr, int b, int e, char*v){
    Int minIndex = b, maxIndex = e, midIndex;
    while(minIndex<maxindex){
        midIndex=(minIndex+maxIndex)/2;
        if(strcmp(arr[midIndx],v<=0)){
            minIndex = midIndex;
        }else{
            maxIndex=minIndex;
        }
   }
        
    if(!strcmp(arr[maxIndex],v)){
        return maxIndex;
    }else{
        return -1;
    }
}

7、字符串ABCD，可以由字符串BCDA或者CDAB通过循环移位而得到。请编程实现以下检测：字符串S1是否可以由字符串S2通 过循环移位而得到。 语言不限（推荐C/C++,不推荐写伪码）

参考答案

1、如下：

  int main()
　{
　　char* src = "hello,world";
　　int len = strlen(src);
　　char* dest = (char*)malloc(len+1);//要为\0分配一个空间
　　char* d = dest;
　　char* s = &src[len-1];//指向最后一个字符
　　while( len-- != 0 )
　　*d++=*s--;
　　*d = 0;//尾部要加\0
　　printf("%s\n",dest);
　　free(dest);// 使用完，应当释放空间，以免造成内存汇泄露
　　return 0;
　}

2、参考代码：

typedef struct node {
    struct node *next;
    int data;
} node;
void createList(node **head, int data)
{
    node *pre, *cur, *new;
    pre = NULL;
    cur = *head;
    while (cur != NULL) {
        pre = cur;
        cur = cur->next;
    }
    new = (node *)malloc(sizeof(node));
    new->data = data;
    new->next = cur;
    if (pre == NULL)
    *head = new;
    else
    pre->next = new;
}
void printLink(node *head)
{
    while (head->next != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("%dn", head->data);
}
int linkLen(node *head)
{
    int len = 0;
    while (head != NULL) {
        len ++;
        head = head->next;
    }
    return len;
}
node* reverseK(node *head, int k)
{
    int i, len, time, now;
    len = linkLen(head);
    if (len < k) {
        return head;
        } else {
        time = len / k;
    }
    node *newhead, *prev, *next, *old, *tail;
    for (now = 0, tail = NULL; now < time; now ++) {
        old = head;
        for (i = 0, prev = NULL; i < k; i ++) {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        if (now == 0) {
            newhead = prev;
        }
        old->next = head;
        if (tail != NULL) {
            tail->next = prev;
        }
        tail = old;
    }
    if (head != NULL) {
        tail->next = head;
    }
    return newhead;
}
int main(void)
{
    int i, n, k, data;
    node *head, *newhead;
    while (scanf("%d %d", &n, &k) != EOF) {
        for (i = 0, head = NULL; i < n; i ++) {
            scanf("%d", &data);
            createList(&head, data);
        }
        printLink(head);
        newhead = reverseK(head, k);
        printLink(newhead);
    }
    return 0;
}

3、这道题想等概率产生0、1，就需要找到两个独立事件，这个两个独立事件发生的概率相同，已知随机数生成器可以以p产生0，以1-p产生1，所以有下面4个独立事件，用随机数生成器产生00，01，10，11，各自的概率分别为p*p，p*(1-p)，(1-p)*p，(1-p)*(1-p)可以发现生成01，10的概率相同，因此只保留这两种情况敏感词舍弃，然后将01映射为0，10映射为1，则等概率0，1随机数生成器可得到。

4、设这四个队分别为A，B，C，D，C（2,4）一共要进行6场比赛，如果A赢了3场，B和C、D3场打平，则A和B、C、D中积分最高的队一起晋级，所以最低得分为2分。0分是不可能晋级的，因为0分意味着其他3个队的积分都在3以上，1分也是不可能晋级的，因为1分意味着输了两场比赛，则必有两个对的得分在3以上。 

5、考虑六位字符000000-999999，共有字符 6位*1000 000个数=6 000 000个字符。0-9这是个字符等概率出现，因此0-9的个数都为6 000 000/10=600 000个。由于前导0不影响1-9的个数，因此自然数0-999 999中，1-9出现的次数均为6 000 000。加上1000000中的那个1，因此最终答案为600 001。 

6、如下：

int BinarySearch(char **ar,int begin,int end,char *v)
{
    int result=-1;
    while(begin <= end)
    {
        int mid=begin+(end-begin)/2;
        if(strcmp(ar[mid],v) > 0)
            end=mid-1;
        else if(strcmp(ar[mid],v) < 0)
            begin=mid+1;
        else
        {
            if(result < mid)
                result=mid;
            begin=mid+1;
        }
    }
    return result;
}

7、参考代码：

bool cmpstr(string s1,string s2) 
{ 
    if (s1.size()!=s2.size())  
        return false; 
    string s3; 
    s3=s1+s1; 
    if(s3.find_first_of(s2,0)!=string::npos) 
        return true; 
    else  
        return false; 
} 

void main(void)  
{   
    string str1="ABCDEFG",str2="CDEFGAB"; 
    if(cmpstr(str1,str2)) 
        cout<<"匹配成功"<<endl; 
    else 
    cout<<"匹配失败"<<endl;    
}