0928Airbnb笔试100+100
这次笔试一共两道题，lc medium级别，两道题都过了，不过后面看牛友考前收到官方短信说不能切出去本地用IDE，我没收到，然后用IDE做的，大概率被判作弊凉了，真是倒霉gg
1,第一题 100%
大意是在有向无环图中，对每个节点来说，有多少个节点（包括他自己）可以到达他。
------刚开始直接按照拓扑排序，不太对，因为对节点A来说，另一个节点B可能有多条路到达A，所以节点B被重复计算，所以后面稍微改了下，改成能到达A的所有节点放入set中，直接去重，输出大小+1；
写的有点繁琐，按照字符串去处理的，应该有更好的解法。
map<string, vector<string>> m;
map<string, int> indegree;
map<string, set<string>> rr;
set<string> dian;
void helper(vector<string>& lines){ // 处理字符串
for(auto s : lines){
string root, tmp;
int n = (int)s.size();
int i = 0;
while(i < n && s[i] != ','){
root += s[i++];
}
dian.insert(root);
if(i == n){
continue;
}
i++;
while(i < n){
if(s[i] == ','){
m[root].push_back(tmp); // 图
indegree[tmp]++;
dian.insert(tmp);
tmp = "";
i++;
}else{
tmp += s[i++];
}
}
m[root].push_back(tmp);
indegree[tmp]++;
dian.insert(tmp);
}
}
vector<string> costsOfNodes(vector<string> lines) {
if(lines.empty()) return {};
vector<string> re;
helper(lines);
while(true){
bool f = false;
for(auto tmp : dian){
if(indegree[tmp] != 0) continue;
//rr[tmp].insert(root);
for(auto ss : m[tmp]){
indegree[ss]--; // 入度--
rr[ss].insert(tmp);
for(auto s : rr[tmp]) rr[ss].insert(s);
//rr[ss]++;
}
indegree[tmp] = -1;
f = true;
re.push_back(tmp + "," + to_string(rr[tmp].size() + 1));
}
if(f == false) break;
}
sort(re.begin(), re.end());
return re;
} 第二题，100% lc原题，leetcode166
1，这道题要我们模拟除法，表示出两个数相除的结果，如果有循环，循环节用括号表示，比如1/3=0.(3)
2，注意几点地方，一个是负数，一个是 INT_MIN/-1 可能会溢出
3，剩下的就是模拟除法了，小数点后每一位就是除数不断乘10除以被除数，除数模被除数后，放入set中，当有重复的时候，说明循环节找到了，加上括号即可
=============
#笔试题目##airbnb##题解#