2014美团网笔试题目(总结)

http://blog.csdn.net/wzy_1988/article/details/12438143

前言

总结一下美团网笔试题目,明天可能去参加美团笔试

题目

1、一堆硬币,一个机器人,如果是反的就翻正,如果是正的就抛掷一次,无穷多次后,求正反的比例

解答:是不是题目不完整啊,我算的是3:1

2、一个汽车公司的产品,甲厂占40%,乙厂占60%,甲的次品率是1%,乙的次品率是2%,现在抽出一件汽车时次品,问是甲生产的可能性

解答:典型的贝叶斯公式,p(甲|废品) = p(甲 && 废品) / p(废品) = (0.4 × 0.01) /(0.4 × 0.01 + 0.6 × 0.02) = 0.25

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

解答:非递归可运行代码

[cpp] view plaincopyprint?

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. typedef struct node {  
  5. struct node *next;  
  6. int data;  
  7. } node;  
  8. void createList(node **head, int data)  
  9. {  
  10.     node *pre, *cur, *new;  
  11.     pre = NULL;  
  12.     cur = *head;  
  13. while (cur != NULL) {  
  14.         pre = cur;  
  15.         cur = cur->next;  
  16.     }  
  17. new = (node *)malloc(sizeof(node));  
  18. new->data = data;  
  19. new->next = cur;  
  20. if (pre == NULL)      
  21.         *head = new;  
  22. else
  23.         pre->next = new;       
  24. }  
  25. void printLink(node *head)  
  26. {  
  27. while (head->next != NULL) {  
  28.         printf("%d ", head->data);  
  29.         head = head->next;  
  30.     }  
  31.     printf("%d\n", head->data);  
  32. }  
  33. int linkLen(node *head)  
  34. {  
  35. int len = 0;  
  36. while (head != NULL) {  
  37.         len ++;  
  38.         head = head->next;  
  39.     }  
  40. return len;  
  41. }  
  42. node* reverseK(node *head, int k)  
  43. {  
  44. int i, len, time, now;  
  45.     len = linkLen(head);  
  46. if (len < k) {  
  47. return head;  
  48.     } else {  
  49.         time = len / k;  
  50.     }  
  51.     node *newhead, *prev, *next, *old, *tail;  
  52. for (now = 0, tail = NULL; now < time; now ++) {  
  53.         old = head;  
  54. for (i = 0, prev = NULL; i < k; i ++) {  
  55.             next = head->next;  
  56.             head->next = prev;  
  57.             prev = head;  
  58.             head = next;  
  59.         }  
  60. if (now == 0) {  
  61.             newhead = prev;  
  62.         }  
  63.         old->next = head;  
  64. if (tail != NULL) {  
  65.             tail->next = prev;  
  66.         }  
  67.         tail = old;  
  68.     }  
  69. if (head != NULL) {  
  70.         tail->next = head;  
  71.     }  
  72. return newhead;  
  73. }  
  74. int main(void)  
  75. {  
  76. int i, n, k, data;  
  77.     node *head, *newhead;  
  78. while (scanf("%d %d", &n, &k) != EOF) {   
  79. for (i = 0, head = NULL; i < n; i ++) {  
  80.             scanf("%d", &data);  
  81.             createList(&head, data);  
  82.         }  
  83.         printLink(head);  
  84.         newhead = reverseK(head, k);      
  85.         printLink(newhead);  
  86.     }  
  87. return 0;  
  88. }  

5、利用两个stack模拟queue

解答:剑指offer上的原题,九度oj有专门的练习,这里贴一下我的ac代码

[cpp] view plaincopyprint?

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. typedef struct stack {  
  5. int top;  
  6. int seq[100000];  
  7. } stack;  
  8. /**
  9.  * 入队操作
  10.  *
  11.  * T = O(1)
  12.  *
  13.  */
  14. void pushQueue(stack *s1, int data)  
  15. {  
  16.     s1->seq[s1->top ++] = data;  
  17. }  
  18. /**
  19.  * 出队操作
  20.  *
  21.  * T = O(n)
  22.  *
  23.  */
  24. void popQueue(stack *s1, stack *s2)  
  25. {  
  26. if (s2->top > 0) {  
  27.         printf("%d\n", s2->seq[-- s2->top]);  
  28.     } else {  
  29. while (s1->top > 0) {  
  30.             s2->seq[s2->top ++] = s1->seq[-- s1->top];  
  31.         }  
  32. if (s2->top > 0)   
  33.             printf("%d\n", s2->seq[-- s2->top]);  
  34. else
  35.             printf("-1\n");  
  36.     }  
  37. }  
  38. int main(void)  
  39. {  
  40. int data, n;  
  41.     stack *s1, *s2;  
  42. char str[5];  
  43. while (scanf("%d", &n) != EOF) {  
  44. // 初始化  
  45.         s1 = (stack *)malloc(sizeof(stack));  
  46.         s2 = (stack *)malloc(sizeof(stack));  
  47.         s1->top = s2->top = 0;  
  48. while (n --) {  
  49.             scanf("%s", str);  
  50. if (strcmp(str, "PUSH") == 0) { // 入队列
  51.                 scanf("%d", &data);  
  52.                 pushQueue(s1, data);  
  53.             } else {    // 出队列
  54.                 popQueue(s1, s2);  
  55.             }  
  56.         }  
  57.         free(s1);  
  58.         free(s2);  
  59.     }  
  60. return 0;  
  61. }  

6、一个m*n的矩阵,从左到右从上到下都是递增的,给一个数elem,求是否在矩阵中,给出思路和代码

解答:杨氏矩阵,简单题目 

[cpp] view plaincopyprint?

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /**
  4.  * 有序矩阵查找
  5.  *
  6.  * T = O(n + n)
  7.  *
  8.  */
  9. void findKey(int **matrix, int n, int m, int key)  
  10. {  
  11. int row, col;  
  12. for (row = 0, col = m - 1; row < n && col >= 0;) {  
  13. if (matrix[row][col] == key) {  
  14.             printf("第%d行,第%d列\n", row + 1, col + 1);  
  15. break;  
  16.         } else if (matrix[row][col] > key) {  
  17.             col -= 1;  
  18.         } else {  
  19.             row += 1;  
  20.         }  
  21.     }  
  22.     printf("不存在!\n");  
  23. }  
  24. int main(void)  
  25. {  
  26. int i, j, key, n, m, **matrix;  
  27. // 构造矩阵
  28.     scanf("%d %d", &n, &m);  
  29.     matrix = (int **)malloc(sizeof(int *) * n);  
  30. for (i = 0; i < n; i ++)  
  31.         matrix[i] = (int *)malloc(sizeof(int) * m);  
  32. for (i = 0; i < n; i ++) {  
  33. for (j = 0; j < m; j ++)  
  34.             scanf("%d", &matrix[i][j]);  
  35.     }  
  36. // 查询数据
  37. while (scanf("%d", &key) != EOF) {  
  38.         findKey(matrix, n, m, key);       
  39.     }  
  40. return 0;  
  41. }  

7、编写函数,获取两段字符串的最长公共子串的长度,例如: S1 = GCCCTAGCCAGDE S2 = GCGCCAGTGDE 这两个序列的最长公共字串为GCCAG,也就是说返回值为5

解答:简单的动态规划题目,设dp[i][j]表示以s1[i]和s2[j]结尾的最长公共子串的长度,则状态转移方程为:

代码如下:

[cpp] view plaincopyprint?

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define N 100
  5. int dp[N][N];  
  6. void lcsLen(char *s1, char *s2, int len1, int len2)  
  7. {  
  8. int i, j, max, index;  
  9.     memset(dp, 0, sizeof(dp));  
  10.     max = index = 0;  
  11. for (i = 1; i <= len1; i ++) {  
  12. for (j = 1; j <= len2; j ++) {  
  13. if (s1[i] == s2[j]) {  
  14.                 dp[i][j] = dp[i - 1][j - 1] + 1;  
  15. if (dp[i][j] > max) {  
  16.                     max = dp[i][j];  
  17.                     index = i - max + 1;  
  18.                 }  
  19.             } else {  
  20.                 dp[i][j] = 0;  
  21.             }  
  22.         }  
  23.     }  
  24.     printf("最大长度为%d\n", max);  
  25. for (i = 0; i < max; i ++) {  
  26.         printf("%c ", s1[i + index]);  
  27.     }  
  28.     printf("\n");  
  29. }  
  30. int main(void)  
  31. {  
  32. char s1[N], s2[N];  
  33. int i, len1, len2;  
  34. while (scanf("%d %d", &len1, &len2) != EOF) {  
  35. for (i = 1; i <= len1; i ++) {  
  36.             scanf("%c", &s1[i]);  
  37.         }  
  38. for (i = 1; i <= len2; i ++) {  
  39.             scanf("%c", &s2[i]);  
  40.         }  
  41.         lcsLen(s1, s2, len1, len2);  
  42.     }  
  43. return 0;  
  44. }  

8、有一个函数“int f(int n)”,请编写一段程序测试函数f(n)是否总是返回0,并添加必要的注释和说明

解答:博主对测试一向没有太大的兴趣,这道题让我考虑就是int从-2147483648-2147483647去遍历f的返回值,flag为标志位,不写代码了,太简单

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

如何使用tableaux进行逻辑计算

原文作者:Miguel Diaz Kusztrich

93280
来自专栏aCloudDeveloper

算法导论第十九章 斐波那契堆

  《算法导论》第二版中在讨论斐波那契堆之前还讨论了二项堆,但是第三版中已经把这块的内容放到思考题中,究极原因我想大概是二项堆只是个引子,目的是为了引出斐波那契...

34380
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

33150
来自专栏swag code

编程:判断一个数是否是奇数?(93.7%的人会写错)

看似是对的,但是每执行四次(四分之一错误)便会有一个错误的结果(用数据说话)。考虑到负奇数的情况,它除以2的结果就不会是1。因此,返回值是false,而这样是不...

9940
来自专栏数说工作室

【SAS Says】基础篇:6. 开发数据(二)

如果你管着一份10000条的客户数据,有一天,老板拿着一个500人的表告诉你,这表上的500位客户的信息发生了变动,而且变动的变量很不规律,如客户102是收入发...

43830
来自专栏潇涧技术专栏

Python Algorithms - C5 Traversal

Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点。对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit)。遍...

10310
来自专栏take time, save time

你所能用到的无损压缩编码(二)

     上个月项目荷兰大佬要检查,搞的我想写的东西不断推迟,现在检查完了,我决定继续把我想写的这整个一个系列写完,上一次写的是最简单的无损编码行程编码,这一次...

37890
来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

27530
来自专栏数据小魔方

sparklines迷你图系列15——Composition(BoxPlot)

今天要跟大家分享的是sparklines迷你图系列14——BoxPlot。 箱线图是用于呈现数据分布形态(功能类似直方图)的一种图表,对于连续型数据,箱线图可以...

31140
来自专栏简书专栏

Python数据科学库-小测验

答:np.arange、np.array、np.ones、np.zeros、np.full

20110

扫码关注云+社区

领取腾讯云代金券