首页 > 代码库 > 去哪儿网2017春招在线笔试
去哪儿网2017春招在线笔试
第一题，给二叉树的先序遍历和中序遍历，求层序遍历。
这个。。。大二做的。。。
根据先序和中序的性质，先序第一个节点一定是根，在中序中找到根的位置，左边的就是左子树，右边的就是右子树，递归就好。
递归建好树 层先遍历需要通过队列实现。
#include <bits/stdc++.h>using namespace std;struct bi_tree { int val; bi_tree *left, *right;};bi_tree *build_tree(int a[], int b[], int n) { bi_tree *root = new bi_tree(); root->val = a[0]; for (int i = 0; i < n; ++i) { if (b[i] == a[0]) { // root if (i == 0) { // left child tree is null root->left = nullptr; } else { root->left = build_tree(a+1, b, i); } if (i == n - 1) { // right child tree is null root->right = nullptr; } else { root->right = build_tree(a+i+1, b+i+1, n-i-1); } } } return root;}void print(bi_tree *root) { queue<bi_tree *> que; que.push(root); bool fir = true; while (que.size()) { bi_tree *now = que.front(); que.pop(); if (fir) fir = false; else printf(" "); printf("%d", now->val); if (now->left) que.push(now->left); if (now->right) que.push(now->right); }}int main(){ int n; int a[1000], b[1000]; cin >> n; for (int i = 0; i < n; ++i) scanf("%d", a+i); for (int i = 0; i < n; ++i) scanf("%d", b+i); bi_tree *root = build_tree(a, b, n); print(root); return 0;}
第二题，进制转化
这个。。。。大水了。。。
#include <bits/stdc++.h>using namespace std;char str[1000];int main(){ while (cin >> str) { long long ans = 0; int n = strlen(str); for(int i = 0; i < n; ++i) { ans = ans * 26 + str[i] - ‘a‘; } cout << ans << endl; } return 0;}
第三题，单词变换
两个单词如果只有一个字母不相同，那么他们之间的路径为1，否则为无限大，然后求最短路就好了。。。。
虽然没写数据范围，但根据我去年做去哪儿笔试的经验。。。。肯定不会很大。。。。。所以随便Floyd就好了。。。
#include <bits/stdc++.h>using namespace std;string s, t;string dir[1000];int graph[1000][1000];bool cmp(string a, string b) { int cnt = 0; for (int i = 0; i < a.length(); ++i) { if (a[i] != b[i]) { if (cnt == 0) cnt++; else return false; } } return true;}int main(){ // freopen("in.txt", "r", stdin); cin >> s >> t; int n = 0; int e; for (; cin >> dir[n]; n++) { if (dir[n] == t) e = n; } dir[n++] = s; for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { if (i == j) graph[i][j] = 0; else if ( cmp(dir[i], dir[j]) ) graph[i][j] = graph[j][i] = 1; else graph[i][j] = graph[j][i] = 1000000; } } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = graph[i][k] + graph[k][j]; } } } } printf("%d", graph[n-1][e]+1); return 0;}
去哪儿网2017春招在线笔试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。