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了。對于具體實現我就不多寫了。
 

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈