【笔试开放时间】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; } };
全部评论
(5) 回帖