<input id="iys2c"></input>
  • <menu id="iys2c"></menu>
  • <input id="iys2c"></input>
    <input id="iys2c"><acronym id="iys2c"></acronym></input>
  • <menu id="iys2c"></menu>
    <menu id="iys2c"></menu>
  • <input id="iys2c"></input>
    <input id="iys2c"><acronym id="iys2c"></acronym></input>
  • <menu id="iys2c"><u id="iys2c"></u></menu>
    <menu id="iys2c"><u id="iys2c"></u></menu><input id="iys2c"><u id="iys2c"></u></input>
  • <input id="iys2c"></input>
  • 2021年美團程序員面試題

    小編:管理員 701閱讀 2021.06.25

    第1題:


     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;

    }


    第2題:


     有一個隨機數發生器,以概率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隨機數生成器可得到


    第3題:


     4個足球隊打小組單循環,計分方式:勝3分平1分負0分,如果計分相同,則凈勝球多的隊伍排名靠前,如果凈勝球還一樣,則進球多的球隊排名靠前。小組前兩名出線。問可能出線的最低分數是多少。請說明推理過程。 備注:單循環賽是指所有參加比賽的隊兩兩之間都比賽一次,最后按各隊在全部比賽中的積分,得失分率排列名次。



     第一名的最壞成績是所有球隊之間都是平,但是它與其他三支球隊之間的比賽累積進球最多的。所以第二名的最壞成績最差是三平,而且球隊累積進球第二多。所以最差是三分。


    第4題:


     從1到1000000的所有自然數,數字“1”一共出現了多少次?例:自然數101中,數字“1”出現了2次,自然數1011中,數字“1”出現了3次,請寫明計算過程及結果。



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

    加起來一共600,001次


    第5題:


     請找出下面代碼中的所有錯誤
    說明:以下代碼是把一個字符串倒序,如“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;

    }


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

        }

    }

       




     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題:


     字符串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;

        }

     

     

    }


    關聯標簽:
    成年片黄色电影大全 - 视频 - 在线观看 - 影视资讯 - 爱赏网