华为OD机试 - 统计员工影响力分数（Python/JS/C/C++ 新系统 200分）

华为OD机试 新系统 统一考试题库清单持续收录中以及考点说明Python/JS/C/C。专栏导读本专栏收录于《华为OD机试真题Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述假设你是大型科技公司的数据分析师负责分析公司内部员工的社交网络。你需要编写一个函数来计算每个员工的影响力分数。影响力分数定义为该员工直接和间接影响的员工数量。二、输入描述n员工总数。employess:一个二维列表表示员工的社交网络关系。例如employees[i]是一个包含员工 i 直接影响的员工ID的列表。备注employees列表中* 表示没有直接影响到的员工员工总数小于20自身不算分数。三、输出描述influenceScores一个整数数组表示每个员工的影响力分数。四、测试用例测试用例11、输入4123*2、输出3 2 1 03、说明0 - 1 - 2 - 3所以 0 能影响 1、2、3共 3 人1 能影响 2、3共 2 人2 能影响 3共 1 人3 不能影响任何人得 0测试用例21、输入51 234**2、输出4 1 1 0 03、说明0 直接影响 1、2间接还能影响 3、4共 4 人1 影响 3共 1 人2 影响 4共 1 人3、4 均无影响五、解题思路这道题本质上是一个有向图的可达性统计问题。1、建模把每个员工看成图中的一个节点。如果员工 i 直接影响员工 j就建立一条从 i - j 的有向边。这样题目就转化为对图中的每个节点求从它出发可以到达多少个其他节点。2、求解方式对每个员工 i执行一次 DFS或 BFS能直接到达的员工计入影响力能通过别人继续到达的员工也计入影响力使用 visited 数组避免重复访问防止环导致死循环最后统计 visited 中为 true 的个数即可。六、Python算法源码importsys# 深度优先搜索从当前员工出发找到所有可影响到的员工defdfs(node,graph,visited):fornxtingraph[node]:ifnotvisited[nxt]:visited[nxt]Truedfs(nxt,graph,visited)defmain():linessys.stdin.read().splitlines()ifnotlines:return# 读取员工总数nint(lines[0].strip())# 邻接表graph[i] 表示员工 i 直接影响到的员工graph[[]for_inrange(n)]# 读取每个员工的直接影响关系foriinrange(n):linelines[i1].strip()ifi1len(lines)else# * 或空行表示没有直接影响对象ifnotlineorline*:continueforsinline.split():vint(s)# 做边界保护并排除自己影响自己if0vnandv!i:graph[i].append(v)ans[]# 对每个员工分别进行 DFSforiinrange(n):visited[False]*n dfs(i,graph,visited)# True 的个数就是影响力分数ans.append(str(sum(visited)))# 按题意输出sys.stdout.write( .join(ans))if__name____main__:main()七、JavaScript算法源码constfsrequire(fs);constinputfs.readFileSync(0,utf8).split(/\r?\n/);if(input.length0input[0].trim()!){// 员工总数constnNumber(input[0].trim());// 邻接表graph[i] 表示员工 i 直接影响到的员工constgraphArray.from({length:n},()[]);// 构建图for(leti0;in;i){constline(input[i1]||).trim();// * 或空行表示没有直接影响任何人if(!line||line*){continue;}constarrline.split(/\s/);for(constsofarr){constvNumber(s);// 边界保护并排除自己影响自己if(v0vnv!i){graph[i].push(v);}}}// 深度优先搜索functiondfs(node,visited){for(constnxtofgraph[node]){if(!visited[nxt]){visited[nxt]true;dfs(nxt,visited);}}}constans[];// 对每个员工计算影响力for(leti0;in;i){constvisitedArray(n).fill(false);dfs(i,visited);// 统计能影响到的人数constcountvisited.filter(Boolean).length;ans.push(String(count));}// 按题意输出process.stdout.write(ans.join( ));}八、C算法源码#includestdio.h#includestring.h#includestdlib.h#defineMAXN25#defineMAXLINE512// graph[i][k] 表示员工 i 直接影响到的第 k 个员工intgraph[MAXN][MAXN];// sizes[i] 表示员工 i 的直接影响人数intsizes[MAXN];// 员工总数intn;/** * 深度优先搜索 * 功能从 node 出发标记所有可影响到的员工 */voiddfs(intnode,intvisited[]){for(inti0;isizes[node];i){intnxtgraph[node][i];if(!visited[nxt]){visited[nxt]1;dfs(nxt,visited);}}}intmain(){// 读取员工总数if(scanf(%d,n)!1){return0;}// 吃掉换行符方便后续 fgets 读整行getchar();charline[MAXLINE];// 构图for(inti0;in;i){sizes[i]0;if(!fgets(line,sizeof(line),stdin)){line[0]\0;}// 去掉行末换行符line[strcspn(line,\r\n)]\0;// * 或空行表示没有直接影响任何人if(strlen(line)0||strcmp(line,*)0){continue;}// 按空格拆分char*tokenstrtok(line, );while(token!NULL){intvatoi(token);// 边界保护并排除自己影响自己if(v0vnv!i){graph[i][sizes[i]]v;}tokenstrtok(NULL, );}}// 对每个员工做一次 DFSfor(inti0;in;i){intvisited[MAXN]{0};dfs(i,visited);intcount0;for(intj0;jn;j){countvisited[j];}if(i0){printf( );}printf(%d,count);}return0;}九、C算法源码#includebits/stdc.husingnamespacestd;/** * 深度优先搜索 * 从当前员工 node 出发找到所有可影响到的员工 */voiddfs(intnode,constvectorvectorintgraph,vectorintvisited){for(intnxt:graph[node]){if(!visited[nxt]){visited[nxt]1;dfs(nxt,graph,visited);}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string firstLine;if(!getline(cin,firstLine)||firstLine.empty()){return0;}// 员工总数intnstoi(firstLine);// 邻接表vectorvectorintgraph(n);// 读取每个员工的直接影响关系for(inti0;in;i){string line;if(!getline(cin,line)){line;}// * 或空行表示没有直接影响任何人if(line.empty()||line*){continue;}stringstreamss(line);intv;// 解析该行所有员工编号while(ssv){// 边界保护并排除自己影响自己if(v0vnv!i){graph[i].push_back(v);}}}// 计算每个员工的影响力分数for(inti0;in;i){vectorintvisited(n,0);dfs(i,graph,visited);intcountaccumulate(visited.begin(),visited.end(),0);if(i0){cout ;}coutcount;}return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。