首页 > 【三七互娱】【后端开发工程师】【2022届8.24笔试】
头像
mu_luo
编辑于 2021-08-25 09:56
+ 关注

【三七互娱】【后端开发工程师】【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;
    }
};





全部评论

(5) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐