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?
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- 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("%d\n", 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;
- }
5、利用两个stack模拟queue
解答:剑指offer上的原题,九度oj有专门的练习,这里贴一下我的ac代码
[cpp] view plaincopyprint?
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- typedef struct stack {
- int top;
- int seq[100000];
- } stack;
-
- /**
- * 入队操作
- *
- * T = O(1)
- *
- */
- void pushQueue(stack *s1, int data)
- {
- s1->seq[s1->top ++] = data;
- }
-
- /**
- * 出队操作
- *
- * T = O(n)
- *
- */
- void popQueue(stack *s1, stack *s2)
- {
- if (s2->top > 0) {
- printf("%d\n", s2->seq[-- s2->top]);
- } else {
- while (s1->top > 0) {
- s2->seq[s2->top ++] = s1->seq[-- s1->top];
- }
-
- if (s2->top > 0)
- printf("%d\n", s2->seq[-- s2->top]);
- else
- printf("-1\n");
- }
-
- }
-
-
- int main(void)
- {
- int data, n;
- stack *s1, *s2;
- char str[5];
-
- while (scanf("%d", &n) != EOF) {
- // 初始化
- s1 = (stack *)malloc(sizeof(stack));
- s2 = (stack *)malloc(sizeof(stack));
- s1->top = s2->top = 0;
-
- while (n --) {
- scanf("%s", str);
-
- if (strcmp(str, "PUSH") == 0) { // 入队列
- scanf("%d", &data);
- pushQueue(s1, data);
- } else { // 出队列
- popQueue(s1, s2);
- }
- }
-
- free(s1);
- free(s2);
- }
-
- return 0;
- }
6、一个m*n的矩阵,从左到右从上到下都是递增的,给一个数elem,求是否在矩阵中,给出思路和代码
解答:杨氏矩阵,简单题目
[cpp] view plaincopyprint?
- #include <stdio.h>
- #include <stdlib.h>
-
- /**
- * 有序矩阵查找
- *
- * T = O(n + n)
- *
- */
- void findKey(int **matrix, int n, int m, int key)
- {
- int row, col;
-
- for (row = 0, col = m - 1; row < n && col >= 0;) {
- if (matrix[row][col] == key) {
- printf("第%d行,第%d列\n", row + 1, col + 1);
- break;
- } else if (matrix[row][col] > key) {
- col -= 1;
- } else {
- row += 1;
- }
- }
- printf("不存在!\n");
- }
-
- int main(void)
- {
- int i, j, key, n, m, **matrix;
-
- // 构造矩阵
- scanf("%d %d", &n, &m);
- matrix = (int **)malloc(sizeof(int *) * n);
- for (i = 0; i < n; i ++)
- matrix[i] = (int *)malloc(sizeof(int) * m);
-
- for (i = 0; i < n; i ++) {
- for (j = 0; j < m; j ++)
- scanf("%d", &matrix[i][j]);
- }
-
- // 查询数据
- while (scanf("%d", &key) != EOF) {
- findKey(matrix, n, m, key);
- }
-
- return 0;
- }
7、编写函数,获取两段字符串的最长公共子串的长度,例如:
S1 = GCCCTAGCCAGDE
S2 = GCGCCAGTGDE
这两个序列的最长公共字串为GCCAG,也就是说返回值为5
解答:简单的动态规划题目,设dp[i][j]表示以s1[i]和s2[j]结尾的最长公共子串的长度,则状态转移方程为:
代码如下:
[cpp] view plaincopyprint?
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- #define N 100
-
- int dp[N][N];
-
- void lcsLen(char *s1, char *s2, int len1, int len2)
- {
- int i, j, max, index;
-
- memset(dp, 0, sizeof(dp));
-
- max = index = 0;
-
- for (i = 1; i <= len1; i ++) {
- for (j = 1; j <= len2; j ++) {
- if (s1[i] == s2[j]) {
- dp[i][j] = dp[i - 1][j - 1] + 1;
-
- if (dp[i][j] > max) {
- max = dp[i][j];
- index = i - max + 1;
- }
- } else {
- dp[i][j] = 0;
- }
- }
- }
-
- printf("最大长度为%d\n", max);
-
- for (i = 0; i < max; i ++) {
- printf("%c ", s1[i + index]);
- }
- printf("\n");
- }
-
-
- int main(void)
- {
- char s1[N], s2[N];
- int i, len1, len2;
-
- while (scanf("%d %d", &len1, &len2) != EOF) {
- for (i = 1; i <= len1; i ++) {
- scanf("%c", &s1[i]);
- }
- for (i = 1; i <= len2; i ++) {
- scanf("%c", &s2[i]);
- }
-
- lcsLen(s1, s2, len1, len2);
-
- }
-
- return 0;
- }
8、有一个函数“int f(int n)”,请编写一段程序测试函数f(n)是否总是返回0,并添加必要的注释和说明
解答:博主对测试一向没有太大的兴趣,这道题让我考虑就是int从-2147483648-2147483647去遍历f的返回值,flag为标志位,不写代码了,太简单