【算法】字节跳动编程题-认识的人

zr_hebo 发布于2019-08-23 11:41 / 2069人阅读

摘要：题目描述团队在月日搬入了学清嘉创大厦，为庆祝团队的乔迁之喜，字节君决定邀请整个团队，举办一个大型团建游戏字节跳动大闯关。这个人每个人都向字节君提供了自己认识的人的名字，不包括自己。其他所有人均刻意直接或间接的认识，分在同一组。

题目描述

Bytedance Efficiency Engineering团队在8月20日搬入了学清嘉创大厦，为庆祝团队的乔迁之喜，字节君决定邀请整个EE团队，举办一个大型团建游戏-字节跳动大闯关。可是遇到了一个问题：

EE团队共有n个人，大家都比较害羞，不善于与陌生人交流。这n个人每个人都向字节君提供了自己认识的人的名字，不包括自己。如果A的名单里有B，或B的名单里有A，则代表A与B相互认识。同时，如果A认识B，B认识C，则代表A与C也会很快的认识，毕竟通过B的介绍，两个人就可以很快相互认识的了。

为了大闯关游戏可以更好地团队写作、气氛更活跃，并使得团队中的人可以尽快的相互了解、认识和交流，字节君决定根据这个名单将团队分为m组，每组人数可以不同，但组内的任何一个人都与组内的其他所有人直接或间接的认识和交流。如何确定一个方案，使得团队可以分为m组，并且这个m尽可能地小呢？

输入描述

</>复制代码 
第一行一个整数n，表示有n个人，从1开始编号
接下来n行，分别表示第i个人认识的人的编号k（1<=k<=n），每个人的名单以0代表结束

输出描述

</>复制代码 
一个整数m，代表可以闻的最小的组的个数

示例

输入

输出

</>复制代码 
2

说明

</>复制代码 
1号同学孤独的自己一个组，他谁也不认识，也没有人认识他。其他所有人均刻意直接或间接的认识，分在同一组。

解法思路

采用并查集。
对于图G(V,E)，每个人为一个节点v，如果x号同学和y号同学认识或者间接认识，则(x,y)为图中的一条边。
set数组用来表示这个图，最后计算图set中有多少连通分支。
set[x]=x时，代表x为该连通分支的根节点，有多少根节点就有多少连通分支。

JavaScript实现

</>复制代码 
let n = parseInt(readline());
let arr = new Array();
let set = new Array();
for(let i = 0; i < n; i++){
    let line = readline().split(" ");
    arr[i] = new Array();
    set[i] = i;
    for(let j = 0; j < line.length; j++){
        arr[i][j] = parseInt(line[j]) - 1;
    }
}
for(let i = 0; i < n; i++){
    for(let j = 0; j < arr[i].length-1; j++){
        union(set, i, arr[j]);
    }
}
let count = 0;
for(let i = 0; i < n; i++){
    if(set[i] == i){
        count++;
    }
}
print(count);
//返回x的根节点
function root(set, x){
    if(set[x] != x){
        root(set[x]);
    }else{
        return x;
    }
}
//合并x和y所在的两个连通分支
function union(set, x, y){
    let xroot = root(set, x);
    let yroot = root(set, y);
    if(xroot != yroot){
        set[y] = xroot;
        set[yroot] = xroot;
    }
}

GPU云服务器云服务器面试c语言算法编程题字节跳动字节跳动小程序字节跳动 ucloud

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97306.html

字节跳动Python后端开发岗，已拿offer

摘要：今年岁，毕业之后进入一家小型的互联网公司工作，名字就不说了，算是熟知的，在这家公司呆了两年，直至今年才有了跳槽的想法。在众多大厂中，最终选择了字节跳动。这样的调整，一方面对自己学习有帮助，另一方面让自己应对面试更从容，更顺利。 ...

JasonZhang 2021-11-12 10:36 评论0 收藏0
【算法】字节跳动编程题-双生词

摘要：题目描述双生词双生词是指满足如下条件的两个字符串假设两个字符串分别为和字符串长度相同将字符串收尾绕成环，再选一个位置切开，顺时针或逆时针能够得到字符串容易得到，若与为双生词，则与也为双生词给定一批仅有英文小写字母组成的字符串，询问他们之中是题目描述双生词双生词是指满足如下条件的两个字符串：（假设两个字符串分别为S和S’） 1. 字符串长度相同 2. 将字符串S收尾绕成环，再选一个...

Code4App 2019-08-23 11:43 评论0 收藏0
35岁以后依然被公司抢着要？4面字节跳动，完虐面试官年薪70w，图形化app开发工具

摘要：面试后面试后及时总结，有可能下一个面试官会问你同样的问题。同时面试官也对我的未来技术发展提出了很多建议。总的来说，四面的氛围并没有想象得那么严肃，面试官也说面试得很愉快。 ...

XGBCCC 2021-11-24 09:39 评论0 收藏0
一篇字节跳动前端面经

摘要：为了避免它，只需分配将要使用的必要构造函数。示例对于此示例，就需要保持父构造函数继续正常工作。结论手动设置或更新构造函数可能会导致不同且有时令人困惑的后果。为了防止它，只需在每个特定情况下定义构造函数的角色。 hr小姐姐说一共有1轮笔试 + 3轮技术面 + 1轮hr面，面试地点在中关村天使大厦，岗位是1-3年前端笔试笔试分为多选简答判断手写代码四部分，下面只写了印象比较深的几...

caige 2019-08-26 10:29 评论0 收藏0