2014年阿里巴巴校园招聘两道算法题

昨天阿里巴巴校园招聘在线测试，总的来说算法题比较简单，至于前面的选择题不是本人的强项，个人感觉比较难。下面我们说说两道算法题：

第一题大意是有一个quary和text要求找出两者匹配最长的字符串的长度：例如：quary“abcdef”，text“sabcd”那么最长匹配即为abcd，所以返回4就OK。对于本题的解法个人感觉和LCS差不多，只需进行小小的改进就OK了，如果两者的对应为相同动态方程就按照LCS来做，如果不同直接赋值0就OK了。下面给出具体解法（比较简单）。
 

1. 01.#include<stdio.h>    
2. 02.#include <stdlib.h>    
3. 03.#include <string.h>    
4. 04.   
5. 05.   
6. 06.int find_max_len(const char *quary,const char *text)   
7. 07.{   
8. 08.    if(quary == NULL || text ==  NULL)   
9. 09.    {   
10. 10.        return 0;   
11. 11.    }   
12. 12.   
13. 13.    int len1 = strlen(quary);   
14. 14.    int len2 = strlen(text);   
15. 15.    int **temp = NULL;   
16. 16.    int i,j;   
17. 17.    for(i = 0; i < len1 + 1; i++)   
18. 18.    {   
19. 19.        temp = (int **)malloc(sizeof(int **)*(len1+1));   
20. 20.            memset(temp, 0,sizeof(int **)*(len1+1));   
21. 21.    }   
22. 22.   
23. 23.    for(j = 0; j < len1 + 1; j++)   
24. 24.    {   
25. 25.        temp[j] = (int *)malloc(sizeof(int *)*(len2 + 1));   
26. 26.        memset(temp[j],0, sizeof(int *)*(len2 +1));   
27. 27.    }   
28. 28.   
29. 29.    for(i = 1; i < len1+1; i++)   
30. 30.    {   
31. 31.        for(j = 1; j < len2+ 1; j++)   
32. 32.        {   
33. 33.            if(quary[i-1] == text[j-1])   
34. 34.            {   
35. 35.                temp[i][j] = temp[i-1][j-1] + 1;   
36. 36.            }   
37. 37.            else   
38. 38.            {   
39. 39.                temp[i][j] = 0;   
40. 40.            }   
41. 41.        }   
42. 42.    }   
43. 43.    int Max = 0;   
44. 44.    for( i = 0; i < len1+1; i++)   
45. 45.    {   
46. 46.        for(j = 0; j < len2+1; j++)   
47. 47.        {   
48. 48.            if(Max < temp[i][j])   
49. 49.            {   
50. 50.                Max = temp[i][j];   
51. 51.            }   
52. 52.            printf("%d ", temp[i][j]);   
53. 53.        }   
54. 54.   
55. 55.        printf("\n");   
56. 56.    }   
57. 57.   
58. 58.    return Max;   
59. 59.}   
60. 60.   
61. 61.int main()   
62. 62.{   
63. 63.    const char*quary = "abcdefg";   
64. 64.    const char *text = "sbcd";   
65. 65.    printf("%d\n",find_max_len(quary, text));   
66. 66.    return 0;   
67. 67.}   

对与第二道题大意是：给定一个二叉树每个节点都是数字，找出其中两个差值最大的绝对值（如果我没有理解错误就是这个意思）要求算法高效。个人该觉该题最起码得遍历一下该数，要求高效那么就不要递归遍历，改成非递归即可。对于非递归遍历方法比较多，分层，前序，后序等，辅助空间采用队列或者栈等。个人感觉使用按层+queue最为简单，在找出最大，最小值就OK了。对于具体实现我就不多写了。