去哪儿网实习生笔试题

去哪儿网实习生笔试题目：.

第一题：

1.由前序遍历和中序遍历构造二叉树。

2.层次遍历二叉树并打印。

#include<iostream>
#include<queue>
using namespace std;

struct TreeNode
{
    TreeNode*left;
    TreeNode*right;
    int val;
    TreeNode(int x):left(NULL),right(NULL),val(x){}
};

TreeNode* builddfs(int a[],int prei,int prej,int b[],int ini,int inj)
{
    if(ini>inj||prei>prej)
    return NULL;
    int target=a[prei];
    int start=ini;
    TreeNode*root=new TreeNode(a[prei]);
    int len=0;
    while(start<=inj&&b[start]!=target) {start++;len++;}
    root->left=builddfs(a,prei+1,len+prei,b,ini,ini+len-1);
    root->right=builddfs(a,len+prei+1,prej,b,start+1,inj);
    return root;
}

void printbfs(TreeNode*root)
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode*front=q.front();
        q.pop();
        cout<<front->val<<" ";
        if(front->left) q.push(front->left);
        if(front->right) q.push(front->right);
    }
}
int main()
{
    int n;
    cin>>n;
    int*pre=new int[n];
    int*in=new int[n];
    for(int i=0;i<n;i++) cin>>pre[i];
    for(int i=0;i<n;i++) cin>>in[i];
    TreeNode*root=builddfs(pre,0,n-1,in,0,n-1);
    printbfs(root);
    delete []pre;
    delete []in;
    return 0;
}

第二题：

a,b,c,d,e,,,,,,x,y,z   的值为  0-25

26进制，由英文字符串求出10进制的值。

#include <iostream>
#include <string>

using namespace std;

long long change(string str)
{
    long long sum=0;
    for(int i=0;i<str.size();i++)
    {
        sum=26*sum+str[i]-'a';
    }
    return sum;
}

int main()
{
    string str;
    while(cin>>str)
    {
        cout<<change(str)<<endl;
    }
    return 0;
}

第三题：编号127 Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

word ladder是一类比较难的题目。用DFS来做。每一步从单词里面拆掉一个字母替换，然后看看改变字母后的单词在不在词典里

#include <iostream>
#include <unordered_set>
#include <string>
#include <queue>
using namespace std;

int ladderlength(string start,string end,unordered_set<string>&dict)
{
    queue<string> path;
    path.push(start);
    int level=1;
    int count=1;
    dict.erase(start);
    while(dict.size()>0&&!path.empty())
    {
        string curword=path.front();
        path.pop();
        count--;
        for(int i=0;i<curword.size();i++)
        {
            string tmp=curword;
            for(char j='a';j<='z';j++)
            {
                if(tmp[i]==j) continue;
                tmp[i]=j;
                if(tmp==end) return level+1;
                if(dict.find(tmp)!=dict.end()) path.push(tmp);
                dict.erase(tmp);
            }
        }
        if(count==0)
        {
            count=path.size();
            level++;
        }
    }
    return 0;
}

int main()
{

    string str1;
    string str2;
    string tmp;
    cin>>str1;
    cin>>str2;
    unordered_set<string> dict;
    while(cin>>tmp)
    {
        dict.insert(tmp);
    }
    cout<< ladderlength(str1,str2,dict)<<endl;
    return 0;
}