【算法】字節(jié)跳動編程題-認識的人

zr_hebo 發(fā)布于2019-08-23 11:41 / 2026人閱讀

摘要：題目描述團隊在月日搬入了學清嘉創(chuàng)大廈，為慶祝團隊的喬遷之喜，字節(jié)君決定邀請整個團隊，舉辦一個大型團建游戲字節(jié)跳動大闖關。這個人每個人都向字節(jié)君提供了自己認識的人的名字，不包括自己。其他所有人均刻意直接或間接的認識，分在同一組。

題目描述

Bytedance Efficiency Engineering團隊在8月20日搬入了學清嘉創(chuàng)大廈，為慶祝團隊的喬遷之喜，字節(jié)君決定邀請整個EE團隊，舉辦一個大型團建游戲-字節(jié)跳動大闖關。可是遇到了一個問題：

EE團隊共有n個人，大家都比較害羞，不善于與陌生人交流。這n個人每個人都向字節(jié)君提供了自己認識的人的名字，不包括自己。如果A的名單里有B，或B的名單里有A，則代表A與B相互認識。同時，如果A認識B，B認識C，則代表A與C也會很快的認識，畢竟通過B的介紹，兩個人就可以很快相互認識的了。

為了大闖關游戲可以更好地團隊寫作、氣氛更活躍，并使得團隊中的人可以盡快的相互了解、認識和交流，字節(jié)君決定根據(jù)這個名單將團隊分為m組，每組人數(shù)可以不同，但組內(nèi)的任何一個人都與組內(nèi)的其他所有人直接或間接的認識和交流。如何確定一個方案，使得團隊可以分為m組，并且這個m盡可能地小呢？

輸入描述

第一行一個整數(shù)n，表示有n個人，從1開始編號

接下來n行，分別表示第i個人認識的人的編號k（1<=k<=n），每個人的名單以0代表結束

輸出描述

一個整數(shù)m，代表可以聞的最小的組的個數(shù)

示例

輸入

輸出

說明

1號同學孤獨的自己一個組，他誰也不認識，也沒有人認識他。其他所有人均刻意直接或間接的認識，分在同一組。

解法思路

采用并查集。
對于圖G(V,E)，每個人為一個節(jié)點v，如果x號同學和y號同學認識或者間接認識，則(x,y)為圖中的一條邊。
set數(shù)組用來表示這個圖，最后計算圖set中有多少連通分支。
set[x]=x時，代表x為該連通分支的根節(jié)點，有多少根節(jié)點就有多少連通分支。

JavaScript實現(xiàn)

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的根節(jié)點
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語言算法編程題字節(jié)跳動字節(jié)跳動小程序字節(jié)跳動 ucloud

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/97306.html

字節(jié)跳動Python后端開發(fā)崗，已拿offer

摘要：今年歲，畢業(yè)之后進入一家小型的互聯(lián)網(wǎng)公司工作，名字就不說了，算是熟知的，在這家公司呆了兩年，直至今年才有了跳槽的想法。在眾多大廠中，最終選擇了字節(jié)跳動。這樣的調(diào)整，一方面對自己學習有幫助，另一方面讓自己應對面試更從容，更順利。 ...

JasonZhang 2021-11-12 10:36 評論0 收藏0
【算法】字節(jié)跳動編程題-雙生詞

摘要：題目描述雙生詞雙生詞是指滿足如下條件的兩個字符串假設兩個字符串分別為和字符串長度相同將字符串收尾繞成環(huán)，再選一個位置切開，順時針或逆時針能夠得到字符串容易得到，若與為雙生詞，則與也為雙生詞給定一批僅有英文小寫字母組成的字符串，詢問他們之中是題目描述雙生詞雙生詞是指滿足如下條件的兩個字符串：（假設兩個字符串分別為S和S’） 1. 字符串長度相同 2. 將字符串S收尾繞成環(huán)，再選一個...

Code4App 2019-08-23 11:43 評論0 收藏0
35歲以后依然被公司搶著要？4面字節(jié)跳動，完虐面試官年薪70w，圖形化app開發(fā)工具

摘要：面試后面試后及時總結，有可能下一個面試官會問你同樣的問題。同時面試官也對我的未來技術發(fā)展提出了很多建議。總的來說，四面的氛圍并沒有想象得那么嚴肅，面試官也說面試得很愉快。 ...

XGBCCC 2021-11-24 09:39 評論0 收藏0
一篇字節(jié)跳動前端面經(jīng)

摘要：為了避免它，只需分配將要使用的必要構造函數(shù)。示例對于此示例，就需要保持父構造函數(shù)繼續(xù)正常工作。結論手動設置或更新構造函數(shù)可能會導致不同且有時令人困惑的后果。為了防止它，只需在每個特定情況下定義構造函數(shù)的角色。 hr小姐姐說一共有1輪筆試 + 3輪技術面 + 1輪hr面，面試地點在中關村天使大廈，崗位是1-3年前端筆試筆試分為多選簡答判斷手寫代碼四部分，下面只寫了印象比較深的幾...

caige 2019-08-26 10:29 評論0 收藏0