当前位置：首页 > news >正文

华为OD机试 - 统计员工影响力分数（Java 新系统 200分）

news 2026/4/15 4:35:22

华为OD机试新系统题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

假设你是大型科技公司的数据分析师，负责分析公司内部员工的社交网络。你需要编写一个函数来计算每个员工的影响力分数。影响力分数定义为该员工直接和间接影响的员工数量。

二、输入描述

n：员工总数。

employess:一个二维列表，表示员工的社交网络关系。例如employees[i]是一个包含员工 i 直接影响的员工ID的列表。

备注

employees列表中，* 表示没有直接影响到的员工；员工总数小于20；自身不算分数。

三、输出描述

influenceScores，一个整数数组，表示每个员工的影响力分数。

四、测试用例

测试用例1：

1、输入

4
1
2
3
*

2、输出

3 2 1 0

3、说明

0 -> 1 -> 2 -> 3，所以 0 能影响 1、2、3，共 3 人

1 能影响 2、3，共 2 人

2 能影响 3，共 1 人

3 不能影响任何人，得 0

测试用例2：

1、输入

5
1 2
3
4
*
*

2、输出

4 1 1 0 0

3、说明

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 的个数即可。

六、Java算法源码

publicclassOdTest{/** * 深度优先搜索 * 功能：从当前员工 node 出发，找到所有直接或间接能影响到的员工 * * @param node 当前员工编号 * @param graph 邻接表，graph[i] 存储员工 i 直接影响到的员工 * @param visited 标记数组，visited[j] = true 表示员工 j 已经被当前起点员工影响到 */privatestaticvoiddfs(intnode,List<Integer>[]graph,boolean[]visited){// 遍历当前员工直接影响的所有员工for(intnext:graph[node]){// 如果该员工还没有被访问过，说明是新影响到的员工if(!visited[next]){visited[next]=true;// 继续向下搜索，寻找 next 间接影响到的人dfs(next,graph,visited);}}}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);// 读取员工总数 nintn=Integer.parseInt(sc.nextLine().trim());// 使用邻接表存储社交网络关系// graph[i] 表示员工 i 直接影响的员工集合List<Integer>[]graph=newArrayList[n];for(inti=0;i<n;i++){graph[i]=newArrayList<>();}// 逐行读取每个员工的直接影响关系for(inti=0;i<n;i++){Stringline=sc.hasNextLine()?sc.nextLine().trim():"";// "*" 或空行表示该员工没有直接影响任何人if(line.length()==0||"*".equals(line)){continue;}// 按空格拆分出所有员工编号String[]parts=line.split("\\s+");for(Stringpart:parts){if(part.length()==0){continue;}intv=Integer.parseInt(part);// 做一个简单健壮性保护：// 1. 员工编号必须在 0 ~ n-1 范围内// 2. 自己影响自己不计入图中if(v>=0&&v<n&&v!=i){graph[i].add(v);}}}// 结果数组，ans[i] 表示员工 i 的影响力分数int[]ans=newint[n];// 对每个员工分别做一次 DFSfor(inti=0;i<n;i++){// visited[j] = true 表示从员工 i 出发可以影响到员工 jboolean[]visited=newboolean[n];// 从员工 i 开始搜索dfs(i,graph,visited);// 统计可达员工数量intcount=0;for(booleanv:visited){if(v){count++;}}ans[i]=count;}// 按要求输出，数字之间用空格分隔，不输出多余提示信息for(inti=0;i<n;i++){if(i>0){System.out.print(" ");}System.out.print(ans[i]);}sc.close();}}