去哪儿网2017春招在线笔试
2023-03-14 09:48:22 时间
第一题,给二叉树的先序遍历和中序遍历,求层序遍历。
这个。。。大二做的。。。
根据先序和中序的性质,先序第一个节点一定是根,在中序中找到根的位置,左边的就是左子树,右边的就是右子树,递归就好。
递归建好树 层先遍历需要通过队列实现。
#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就好了。。。
(图片偷自:http://blog.csdn.net/kgdysg/article/details/68948893)
#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; }
相关文章
- 微软 Edge 浏览器开通官方微博
- Windows 10十全补丁放出:方便升级Windows 11、修复致命崩溃Bug
- 心心念的应用,让 Linux 新手在 Ubuntu 上轻松玩游戏
- 16个核心概念带你入门 Kubernetes
- 微软赞许Windows 11系统:比以前的系统成功
- 这些 Linux 的“自动化”技巧,教你轻松完成任务
- 苦等多时!微软正式确认Windows 11大更新:可运行安卓应用
- Linux 上怎么配置 Ntp 时间同步
- Linux基础命令,你不得不会的内容
- 远离勒索软件,就用Windows 10自带的勒索软件保护,简单安全
- Linus:Linux 太垃圾了,我把它删了,建议你用 Windows XP
- 发售三个月 微软对Windows 11感到“高兴”:比以前的系统成功
- 谷歌Chrome浏览器要淘汰Cookie 推出全新“隐私沙箱”技术
- 移植案例与原理 - Utils子系统之file文件操作部件
- Vim 一直学不会?试试这个 "真香" 神器
- Windows 10获1月可选更新:帮用户迁移到Windows 11
- Linux 黑话解释:什么是上游和下游?
- Brave vs. Google Chrome:哪个浏览器更适合你?
- 微软 Windows 11/10 Edge 浏览器 Canary 新增侧边栏菜单:网速测试、游戏、Microsoft 365...
- Chrome 浏览器要淘汰 Cookie,谷歌又推出新的“隐私沙箱”技术 Topics