亚麻面经题求解

题目如下图：




请教地里的大牛们，这题该怎么

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

烦版主把此帖移到高频题板块。。。

感觉像topological search

1. // Amazon OA
   
2. // fullfil the maximum number of moving requests
   
3. // ["alex", 1, 2]  --- alex wants to move from blg-1 to blg-2
   
4. // ["ben", 2, 1]   --- ben wants to move from blg-2 to blg-1
   
5. typedef map<int, vector<pair<int, string>>> t_g;
   
6. void dfs(t_g& g, pair<int, string>& e, int target, unordered_set<string>& visited, vector<pair<int, string>>& cur, vector<pair<int, string>>& longest) {
   
7.     if (visited.find(to_string(e.first) + e.second) != visited.end()) return;
   
8. 
   
9.     cur.push_back(e), visited.insert(to_string(e.first) + e.second);
   
10.     if (e.first == target) {
    
11.         if (cur.size() > longest.size()) longest = cur;     // keep the longest, will mark visited later
    
12.     } else {
    
13.         for (auto& n : g[e.first]) {
    
14.             dfs(g, n, target, visited, cur, longest);       // brute-froce try every cycle
    
15.         }
    
16.     }
    
17.     cur.pop_back(), visited.erase(to_string(e.first) + e.second);
    
18. }
    
19. 
    
20. vector<vector<string>> maxMoivingRequest(vector<vector<string>>& requests) {
    
21.     t_g g;
    
22.     for (auto& r : requests) g[stoi(r[1])].push_back({stoi(r[2]), r[0]});
    
23.    
    
24.     vector<vector<string>> ans;
    
25.     unordered_set<string> visited;
    
26.     for (auto& kv : g) {
    
27.         for (auto& e : kv.second) {
    
28.             auto start = to_string(e.first) + e.second;
    
29.             if (visited.find(start) != visited.end()) continue;
    
30. 
    
31.             vector<pair<int, string>> path, longest;
    
32.             dfs(g, e, kv.first, visited, path, longest);
    
33.             if (!longest.empty()) {
    
34.                 ans.push_back(vector<string>{});
    
35.                 for (auto& e : longest) {
    
36.                     visited.insert(to_string(e.first) + e.second), ans.back().push_back(e.second);
    
37.                 }
    
38.             }
    
39.         }
    
40.     }
    
41.     return ans;
    
42. }

复制代码

这题啰嗦的地方是找出最长的环，贴一个暴力DFS的解法O（VE）time，没有仔细测试，请大伙指正。

补充内容 (2019-6-29 12:00):
发现我这个方法有一个case没有考虑到，忽略吧

建图，然后dfs每次找最大的环，找到一个环以后就把人名用set标记出来。从剩下的继续找环，直到所有成员访问过至少一遍。
两个set，一个用来标记人名，每次dfs以后进行更新，另一个用来标记建筑物，放在dfs的函数里使用