字节跳动笔试第二题题解(2021-03-14)

字节跳动笔试第二题
一个病毒不具有攻击性,但是可能分裂出具有攻击性的病毒
现给母细胞编号为0,其分裂的后代依次编号
几代以后,出现几个变异体
需要找出这几个变异体最近的共同祖先(祖先不具有攻击性)

输入:
正整数N代表分裂过程中具有编号的病毒数量
正整数m代表分裂次数
m行,每行第一个数字代表分裂前的祖先编号,第二个数字代表分类数量,后面若干个数字代表分裂后的后代编号
正整数k,后接k个编号代表有攻击性的病毒
输出:
一个数字,具有攻击性的病毒的公共祖先

原案例我不记得了,这个是我临时构造的
案例
input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
2 12 9
output:
1

解法:
构造一种数据结构
其中包含两个数字,第一个是自身编号,第二个是上级祖先编号
用哈希表构建一个关系表,里面存放映射关系
用一个数组virus存放具有攻击性的病毒的编号
第一轮对数组virus寻找依次祖先,自身赋值为祖先的编号(如果是0直接返回),找出编号最小的作为共同祖先,假设变量common表示
对virus数组依次遍历,对小于common的元素继续寻找祖先,如果找到比common更小的元素,则将common赋予该值
直到所有的元素都是common,此时的common就是我们要的答案

补充:
建议先用树结构把整个关系表画出来
时间复杂度:O(N)
空间复杂度:O(N)
本题采用了哈希表unorded_map的数据结构,如果用一个vector<pair<int, int>>来记录关系表,会增加时间复杂度

更多案例:
案例2:
input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
2 9 11
output:
0

案例3:
input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
2 7 12
output:
4

案例4:
input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
3 7 13 10
output:
0
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

void FindCommonAncestor(void) {
    int n, m;
    while (cin >> n >> m) {
        unordered_map<int, int> relationship;
        for (int i = 0; i < m; i++) {
            int parent, num;
            cin >> parent >> num;
            for (int j = 0; j < num; j++) {
                int child;
                cin >> child;
                relationship[child] = parent;
            }
        }
        int virusNum;
        cin >> virusNum;
        vector<int> virus(virusNum);
        for (auto &v : virus) {
            cin >> v;
            //第一次寻找祖先
            v = relationship[v];
        }
        int common = *min_element(virus.begin(), virus.end());
        while (count(virus.begin(), virus.end(), common) != virus.size()) {
            for (auto& v : virus) {
                if (v > common)
                    v = relationship[v];
            }
            common = *min_element(virus.begin(), virus.end());
        }
        cout << common << endl;
    }
}

int main() {
    //笔试第二题
    FindCommonAncestor();
    return 0;
}
欢迎批评和指正

#字节跳动##题解#
全部评论
撸了个Python版本 def find_common_an():     unordered_map = {}     _ = input()     counts = int(input())     for i in range(counts):         num_list = [int(i) for i in input().split()]         par = num_list[0]         cnt = num_list[1]         for j in range(cnt):             unordered_map[num_list[j+2]] = par     virus_list = [int(i) for i in input().split()]     v_l = virus_list[1:]     common = min(v_l)     while v_l.count(common) != len(v_l):         for i in range(len(v_l)):             if v_l[i] > common:                 v_l[i] = unordered_map[v_l[i]]             else:                 common = v_l[i]     print(common) find_common_an()
点赞 回复
分享
发布于 2021-03-18 22:24

相关推荐

2 2 评论
分享
牛客网
牛客企业服务