【三七互娱】【后端开发工程师】【2022届8.24笔试】
【笔试开放时间】8月24日 14：00-22：00
真的人麻了，选择题怎么都是java相关的知识点啊，c++不行吗？
还有编程题，怎么是白板编程，根本不知道写得对不对，气死人了。
现在已经过了笔试时间了，放出来笔经，大家有没有交流的
1.由1、3、5、7、9组成的不重复4位数之和
2.操作系统从作业提交到完成这段时间被称为？
3.n个不同元素，n个节点二叉树，有多少种不同方式？
4.几个栈可以实现队列
5.电子邮件传输层使用的协议？
6.C类地址下最多允许的网络数量？ 这道题做错了，不是主机数量，网络号21位好吧
7.java异常？不会
8.软件工程原则
9.中断会保护的但子程序调用不会保护的寄存器？
10.边界值分析属于白盒测试或者黑盒测试吗？
11.状态寄存器是干嘛的
12.编译器的词法分析器
编程题一：
给定N，求1到N的质数之和
解法一：暴力枚举
解法二：筛法求质数
编程题二：leetcode hard原题
routes : [[1,3,7], [3, 5, 6]]
给定巴士循环走的路线，比如routes[0] : [1,3,7] 代表 1 - > 3 - > 7 -> 1 - > 3.....
给定source和target，请问从S到T最少乘坐多少巴士，如果不能到达返回-1；
815. 公交路线
做完由于不能调试，回头leetcode上试一试，应该是做错了，淦class Solution {
private:
unordered_map<int, vector<int>> dict;
unordered_set<int> visited;
int ans{INT_MAX};
void dfs(vector<vector<int>>& routes, int index, int cnt, int target) {
for (int i = 0; i < routes[index].size(); ++i) {
int stop = routes[index][i];
if ( stop == target) {
ans = min(INT_MAX, cnt);
return;
}
const vector<int>& nextStops = dict[stop];
for (int j = 0; j < nextStops.size(); ++j) {
int nextStop = nextStops[j];
if (visited.find(nextStop) != visited.end()) continue;
visited.insert(nextStop);
dfs(routes, nextStop, cnt + 1, target);
visited.erase(nextStop);
}
}
}
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
for (int i = 0; i < routes.size(); ++i)
for (const int num : routes[i])
dict[num].push_back(i);
const vector<int>& beginStops = dict[source];
for (const int stop : beginStops) {
visited.insert(stop);
dfs(routes, stop, 1, target);
visited.erase(stop);
}
return ans == INT_MAX ? -1 : ans;
}
};
然后今早我改成BFS就过了，肝，的确求最短路应该理所应当用bfs啊啊啊，怎么脑抽了用dfs
class Solution {
private:
unordered_map<int, vector<int>> dict;
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
// 用bfs来做就行， 还是有一些不完整的情况啊啊啊啊
if (source == target) return 0;
for (int i = 0; i < routes.size(); ++i)
for (int j = 0; j < routes[i].size(); ++j)
dict[routes[i][j]].push_back(i);
const vector<int>& beginRoutes = dict[source];
int ans = INT_MAX;
for (int i = 0; i < beginRoutes.size(); ++i) {
unordered_set<int> visited;
queue<int> q;
int cnt = 1;
q.push(beginRoutes[i]);
visited.insert(beginRoutes[i]);
bool arrive = false;
while (!q.empty()) {
int sz = q.size();
for (int j = 0; j < sz; ++j) {
const vector<int>& curRoute = routes[q.front()];
q.pop();
for (const int stop : curRoute) {
if (stop == target) {
ans = min(ans, cnt);
arrive = true;
break;
}
const vector<int>& nextRoutes = dict[stop];
for (const int nextRoute : nextRoutes) {
if (visited.find(nextRoute) == visited.end()) {
visited.insert(nextRoute);
q.push(nextRoute);
}
}
}
if (arrive) break;
}
// 剪枝 同时包含了超过最小不用继续了，也包含了arrive的情况
if (ans <= cnt) break;
cnt++;
}
}
return ans == INT_MAX ? -1 : ans;
}
};
