2021年美团程序员面试题

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

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;

}

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

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

 第一名的最坏成绩是所有球队之间都是平，但是它与其他三支球队之间的比赛累积进球最多的。所以第二名的最坏成绩最差是三平，而且球队累积进球第二多。所以最差是三分。

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

 1-999,999：10的5次方 * 6=600,000
1,000,000 ： 1次

加起来一共600,001次

 请找出下面代码中的所有错误
说明：以下代码是把一个字符串倒序，如“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;

 }

 方法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：

main()

{

   char str[]="hello,world";

   int len=strlen(str);

   char t;

   for(int i=0; i   {

    t=str[i];

    str[i]=str[len-i-1]; str[len-i-1]=t;

   }

   printf("%s",str);

   return 0;

}

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

Int bisearch(char**arr, int b, int e, char*v){

    Int minIndex = b, maxIndex = e, midIndex;

    while(minIndex

        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;

    }

}

 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;
}

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

public class Question2 {

    private static void reverseCharArr(char[] arr, int left, int right) {

        if (arr == null || left > right) return;

        while (left < right) {

            char tmp = arr[left];

            arr[left] = arr[right];

            arr[right] = tmp;

            left++;

            right--;

        }

    }

    public static void main(String[] args) {

        System.out.println(isRotate("ABCD", "DABC"));

    }

    private static String rotate(String str, int i) {

        if (str == null || i > str.length()) return null;

        char arr[] = str.toCharArray();

        reverseCharArr(arr, 0, i-1);

        reverseCharArr(arr, i, arr.length-1);

        reverseCharArr(arr, 0, arr.length-1);

        return new String(arr);

    }

    public static boolean isRotate(String s1, String s2) {

        if (s1 == null || s2 == null || s2.length() != s1.length()) return false;

        int indexOfFirst = s2.indexOf(s1.charAt(0));

        if (indexOfFirst == -1) return false;

        System.out.println(indexOfFirst);

        String tmp = rotate(s2, indexOfFirst);

        System.out.println(tmp);

        if (tmp.equals(s1)) {

            return true;

        }

        return  false;

    }

}