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##题解#