去哪儿网2014笔试算法题汇总

1.写一个函数，转换相对路径为绝对路径，比如：/home/abs/../temp/new/../,输出路径为：/home/temp。

参考代码：

1. //写一个函数，转换相对路径为绝对路径，比如：/home/abs/../temp/new/../,输出路径为：/home/temp。   
   
2. int RP2AP(const char* pInStr, char* pOutStr)  
   
3. {  
   
4.     if (pInStr==NULL || pOutStr==NULL) return 0;  
   
5.   
    
6.     string str = pInStr;  
   
7.     string strTemp;  
   
8.     vector<string> vec_str;  
   
9.     string strOut=””;  
   
10.   
     
11.     int nPos1;  
    
12.     int nPos2;  
    
13.   
     
14.     nPos1 = str.find(“/”, 0);  
    
15.     if (nPos1<0)  
    
16.     {  
    
17.         return -1;  
    
18.     }  
    
19.   
     
20.     while(1)  
    
21.     {  
    
22.         nPos2 = str.find(“/”, nPos1+1);  
    
23.         if (nPos2>nPos1)  
    
24.         {  
    
25.             strTemp = str.substr(nPos1, nPos2-nPos1);  
    
26.             //如果不是/..，就放入vector里   
    
27.             if (strTemp!=”/..”)  
    
28.                 vec_str.push_back(strTemp);  
    
29.             else//弹出上一个   
    
30.             {  
    
31.                 vec_str.reserve(vec_str.size());  
    
32.                 vec_str.pop_back();  
    
33.                 vec_str.reserve(vec_str.size());  
    
34.             }  
    
35.             nPos1 = nPos2;  
    
36.         }  
    
37.         else  
    
38.         {  
    
39.             break;  
    
40.         }  
    
41.     }  
    
42.   
     
43.     //循环赋值累加   
    
44.     for (int i=0; i<vec_str.size(); i++)  
    
45.     {  
    
46.         strOut +=vec_str[i];  
    
47.     }  
    
48.       
     
49.     //这里用strOut.c_str()，要安全一些，有的环境不这样写编译都不过。   
    
50.     memcpy(pOutStr, strOut.c_str(), strOut.size());  
    
51.   
     
52.     return 1;  
    
53. }  
    
54.   
     
55. int main()      
    
56. {      
    
57.     int n = 10;         
    
58.     //char a[] = “/home/abs/../temp/new/../”;   
    
59.     char a[] = “/home/abs/temp/new/../”;   
    
60.   
     
61.     char b[256];  
    
62.       
     
63.     memset(b, 0, 256);  
    
64.     int nRet = RP2AP(a, b);  
    
65.   
     
66.     if (nRet ==1 )  
    
67.         cout << b << endl;  
    
68.   
     
69.     system(“pause”);      
    
70.     return 0;      
    
71. }   //写一个函数，转换相对路径为绝对路径，比如：/home/abs/../temp/new/../,输出路径为：/home/temp。
    

int RP2AP(const char* pInStr, char* pOutStr)

{

    if (pInStr==NULL || pOutStr==NULL) return 0;

 

    string str = pInStr;

    string strTemp;

    vector<string> vec_str;

    string strOut=””;

 

    int nPos1;

    int nPos2;

 

    nPos1 = str.find(“/”, 0);

    if (nPos1<0)

    {

        return -1;

    }

 

    while(1)

    {

        nPos2 = str.find(“/”, nPos1+1);

        if (nPos2>nPos1)

        {

            strTemp = str.substr(nPos1, nPos2-nPos1);

            //如果不是/..，就放入vector里

            if (strTemp!=”/..”)

                vec_str.push_back(strTemp);

            else//弹出上一个

            {

                vec_str.reserve(vec_str.size());

                vec_str.pop_back();

                vec_str.reserve(vec_str.size());

            }

            nPos1 = nPos2;

        }

        else

        {

            break;

        }

    }

 

    //循环赋值累加

    for (int i=0; i<vec_str.size(); i++)

    {

        strOut +=vec_str[i];

    }

    

    //这里用strOut.c_str()，要安全一些，有的环境不这样写编译都不过。

    memcpy(pOutStr, strOut.c_str(), strOut.size());

 

    return 1;

}

 

int main()

{

int n = 10;

    //char a[] = “/home/abs/../temp/new/../”;

    char a[] = “/home/abs/temp/new/../”;

 

    char b[256];

    

    memset(b, 0, 256);

    int nRet = RP2AP(a, b);

 

    if (nRet ==1 )

        cout << b << endl;

 

system(“pause”);

return 0;

}

 

2.一个10*10的矩阵（可以理解为棋盘），随时生成一组数据填入矩阵，任何一个位置的数字除4进行计算，按余数着色，余数为0着色为red，1为blue，2为green，3为black，可以理解为生成4中颜色的棋子放入棋盘，如果存在其中同色五星连珠的情况（规则通五子棋），找出任意一组，输出5个棋子的位置下标值。

3.

有两个文件context.txt和words.conf,请尝试将他们合并成为一段文字，并打印出来。

这两个文件内容如下：

context.txt

“并不是每个人都需要$(qunar)自己的粮食，$(flight.1)每个人都需要做自己穿的$(flight.2)，我们说着别人发明的$(hotel)，使用别人发明的数学……我们一直在$(tuan)别人的成果。使用人类的已有经验和知识$(travel.1)来进行，是一件$(travel.2)的事情” 

 

word.conf

flight=也不是：衣服

qunar=种植

hotel=语言

tuan=使用

travel=发明创造：很了不起

4.

一个文件里有10万个随机正整数，按照以下规则能组合出一份新的数据：

A． 如果当前数字能被3整除，那么它和文件中所有数字（包括自己）两两相加后生成一组数字替代自己的位置。

B． 如果不能被3整除，则它只需要乘以二，生成一个数字替代自己的位置。

例如：[3,7,6] 会组合出[6,10,9,14,9,13,12]

再如：[5,12,9,6,2]会组合出[10,17,24,21,18,14,14,21,18,15,11,11,18,15,12,8,4]

 
 

写一个程序找出并打印出新数据的最小的前200个数字。请考虑优化算法复杂度。

5.已知字母序列【d, g, e, c, f, b, o, a】，请实现一个函数针对输入的一组字符串 input[] = {“bed”, “dog”, “dear”, “eye”}，按照字母顺序排序并打印。

本例的输出顺序为：dear, dog, eye, bed。

6.有一万个北京单身男女向你提交了基本资料，包括：姓名、性别、年龄、星座，写一段程序尝试找出他们最匹配的一对。