刚做完的OA2， 很不幸遇到了critical edge那道题，题⽬⼤概是给了一堆roads,
然后判断哪条road是critical edge。 之前看到面经还专门网上去查了算法，并且⾃己写了一遍做了测试，然鹅OA⾥面给的输入是自定义的pairInt导致
转换还挺麻烦的，那道题最后花了很⻓时间去debug但是还是test case⾥少几条边。。。最 后佛掉了。不知道这种情况亚麻最后还会不会给VO，⼼心态爆炸，估计与亚麻⽆缘吧。第⼀道题是一个two sum find all unique pair.
贴一个别人的面经
亚麻OA2， 附带需要注意的edge case
- 给两个map，第⼀个是 string 人名 ：
vector<string>书， 第二个是string 类型 ：vector<string>书
需要返回⼀个map， string 人名 ：vector<string>最喜欢看的类型
// map1 {“Tom” : [“booka”, “bookb”]; 'Jack" : [“booka”,“bookc”,“bookd”];}
// map2 {“happy” : [“booka”, “bookd”]; “sad” : [“bookb”,“bookc”];}
// res { “Tom” : [“happy”, “sad”]; “Jack” : [“happy”];}
这⾥jack看了A C D,但是A D都是happy，两票，C是sad，一票，所以只有happy最喜欢的类型是happy。
需要注意的edge case有三种。 第⼀种是map1是空的，直接返回⼀个空map。
第⼆种情况是map2是空的，这个时候要把人名加进去，但是每个人名的value是个空vector。第三种情况是 map1只有人名，value里的vector是空，这个时候需要把人名存进去，value是空的。
之前看面经⾃己作的时候没注意第三个情况， 导致17个test有两个没过，知道最后只剩下5分钟终于弄出来了，玩的真是心跳。。。
https://repl.it/repls/BusyLowClimate
这个是我⾃己写的，写的挺烂的，不过可以参考参考，有什么更好的方法也可以讨论。
#include <iostream>
#include <vector>
#include <list>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;
unordered_map<string, vector<string> > amzoa(unordered_map<string, vector<string> > map1, unordered_map<string, vector<string> > map2) {
// map1 {"Tom" : ["booka", "bookb"]; 'Jack" : ["booka","bookc","bookd"];}
// map2 {"happy" : ["booka", "bookd"]; "sad" : ["bookb","bookc"];}
// res { "Tom" : ["happy", "sad"]; "Jack" : ["happy"];}
unordered_map<string, string> temp;
unordered_map<string, vector<string>> res;
if (map2.empty()) {
for (auto it = map1.begin(); it != map1.end(); it++) {
res[it->first] = {};
}
return res;
}
if (map1.empty()) return res;
for (auto it1 = map2.begin(); it1 != map2.end(); it1++) {
for (int i = 0; i < it1->second.size(); i++) {
temp[it1->second[i]] = it1->first;
}
}
/*
for(auto it1 = temp.begin(); it1 != temp.end(); it1++){
cout << it1->first << " : " << it1->second << endl;
}
*/
//temp
/*
booka : happy
bookb : sad
bookc : sad;
bookd : happy
*/
unordered_map<string, unordered_map<string,int>> count;
for (auto it2 = map1.begin(); it2 != map1.end(); it2++) {
for (int i = 0; i < it2->second.size(); i++) {
auto it = temp.find(it2->second[i]);
if (it == temp.end()) continue;
count[it2->first][it->second]++;
}
}
/*
for (auto it1 = count.begin(); it1 != count.end(); it1++) {
cout << it1->first << " : ";
for (auto it2 = it1->second.begin(); it2 != it1->second.end(); it2++) {
cout << it2->first << " : " << it2->second << endl;
}
cout << endl;
}
*/
//count
/*
Tom : Happy : 2
: sad :2
Jack : happy : 2
: sad : 1
*/
for (auto it3 = count.begin(); it3 != count.end(); it3++) {
int maxCount = 0;
for (auto it4 = it3->second.begin(); it4 != it3->second.end(); it4++) {
maxCount = max(maxCount, it4->second);
}
if(it3->second.empty()){
res[it3->first].push_back({});
continue;
}
for (auto it4 = it3->second.begin(); it4 != it3->second.end(); it4++) {
if (it4->second == maxCount) {
res[it3->first].push_back(it4->first);
maxCount = it4->second;
}
}
}
return res;
}
void helper(int u, vector<bool> &visited, vector<pair<int,int>> &res, list<int> *adj, vector<int> &disc, vector<int> &low, vector<int> &parent) {
static int time = 0;
visited[u] = true;
disc[u] = low[u] = ++time;
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); i++) {
int v = *i;
if (!visited[v]) {
parent[v] = u;
helper(v, visited, res, adj, disc, low, parent);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) {
res.push_back(make_pair(u, v));
}
}
else if (v != parent[u]) {
low[u] = min(low[u], disc[v]);
}
}
}
vector<pair<int, int>> criticalConnection(int numOfServers, int numOfConnections,vector<pair<int, int>> connections) {
list<int> *adj = new list<int>[numOfServers+1];
for (int i = 0; i < connections.size(); i++) {
adj[connections[i].first].push_back(connections[i].second);
adj[connections[i].second].push_back(connections[i].first);
}
vector<bool> visited(numOfServers+1, false);
vector<int> disc(numOfServers+1, 0);
vector<int> low(numOfServers+1, 0);
vector<int> parent(numOfServers+1, 0);
vector<pair<int, int>> res;
for (int i = 0; i < numOfServers; i++) {
if (!visited[i]) {
helper(i, visited, res, adj, disc, low, parent);
}
}
return res;
}
int main() {
unordered_map<string, vector<string>> map1{ {"Tom", {"book1", "book2","book3","book4"}}, {"Jack", {"book5", "book6", "book7"}} };
unordered_map<string, vector<string>> map2{ {"Horror", {"book1","book3"}}, {"Histor", {"book5", "book6"}}, {"Action", {"book7"}}, {"Romance", {"book2", "book4"}} };
//unordered_map<string, vector<string>> map2;
unordered_map<string, vector<string>> res = amzoa(map1, map2);
for (auto it1 = res.begin(); it1 != res.end(); it1++) {
cout << it1->first << " ";
for (int i = 0; i < it1->second.size(); i++) {
cout << it1->second[i] << " ";
}
cout << endl;
}
vector<pair<int, int>> ama{ {1,2},{1,3},{3,4},{1,4}};
vector<pair<int, int>> res4 = criticalConnection(4, 4, ama);
cout << "Edges : " << endl;
for (int i = 0; i < res4.size(); i++) {
cout << res4[i].first << res4[i].second << endl;
}
}
- 蠡⼝口武漆贰