华为OD机试真题---精准核酸检测

题目背景

为了达到新冠疫情精准防控的需要，避免全员核酸检测带来的浪费，需要精准圈定可能被感染的人群。题目通过传染病流调以及大数据分析，给出了每个人之间在时间、空间上是否存在轨迹交叉的信息，要求找出需要进行核酸检测的人员数量。

输入描述

总人数N：表示参与统计的总人数。
确诊病例人员编号：用逗号分隔的确诊病例人员编号列表，数量小于N。
接触矩阵：一个N*N的矩阵，表示每个人员之间是否有接触。0表示没有接触，1表示有接触。

输出描述

输出一个整数，表示需要进行核酸检测的人数（不包括确诊病例自身）。

解题思路

方法一：并查集

初始化并查集：根据总人数N初始化并查集，每个节点初始时都是独立的连通分量。
合并接触关系：遍历接触矩阵，对于matrix[i][j]为1的情况，将i和j所属的连通分量合并。
统计连通分量：遍历并查集，统计每个连通分量中的节点数，即每个接触群体的人数。
计算核酸检测人数：遍历确诊病例人员编号，找到每个确诊病例所属的连通分量，并统计这些连通分量中除了确诊病例外的总人数。

`代码实现`

    /** 方法一：并查集* 初始化并查集：根据总人数N初始化并查集，每个节点初始时都是独立的连通分量。* 合并接触关系：遍历接触矩阵，对于matrix[i][j]为1的情况，将i和j所属的连通分量合并。* 统计连通分量：遍历并查集，统计每个连通分量中的节点数，即每个接触群体的人数。* 计算核酸检测人数：遍历确诊病例人员编号，找到每个确诊病例所属的连通分量，并统计这些连通分量中除了确诊病例外的总人数。**/
public class PrecisionTesting {private final int[] parent;private final int[] rank;public PrecisionTesting(int n) {parent = new int[n];rank = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;rank[i] = 1;}}/*** 查找元素x所属的集合* 通过路径压缩优化查找过程** @param x 要查找的元素* @return 元素x所属的集合的根节点*/private int find(int x) {// 如果x不是自己的父节点，递归查找x的父节点，直到找到根节点if (x != parent[x]) {// 路径压缩：将x的父节点直接设置为根节点，优化下次查找parent[x] = find(parent[x]);}// 返回x所属集合的根节点return parent[x];}/*** 将两个集合合并为一个集合* 使用路径压缩和秩合并的策略来优化合并操作** @param x 集合x的元素标识* @param y 集合y的元素标识*/private void union(int x, int y) {// 找到x和y对应的集合的根int rootX = find(x);int rootY = find(y);// 如果x和y已经在同一个集合中，则无需合并if (rootX != rootY) {// 根据秩来决定将哪个根链接到另一个根上// 这里使用的是秩合并的策略，将秩较小的集合链接到秩较大的集合上if (rank[rootX] < rank[rootY]) {// 将rootX链接到rootY上parent[rootX] = rootY;// 更新rootY的秩rank[rootY] += rank[rootX];} else {// 将rootY链接到rootX上parent[rootY] = rootX;// 更新rootX的秩rank[rootX] += rank[rootY];}// 输出合并操作的信息System.out.println("Merging " + rootX + " and " + rootY);}}public static void main(String[] args) {// 输入总人数 Nint n = 10;// 创建PrecisionTesting对象，传入总人数PrecisionTesting pt = new PrecisionTesting(n);// 输入确诊病例编号int[] confirmedCasesStr = {0,2};// 定义接触关系二维数组，表示谁和谁接触过int[][] contacts = {{0, 1},{0, 2},{1, 3},{2, 4},{2, 5},{3, 6},{5, 7},{5, 8},{7, 9}};// 合并接触关系for (int[] contact : contacts) {int x = contact[0];int y = contact[1];// 使用并查集的union操作合并两个接触过的人pt.union(x, y);}// 计算需要进行核酸检测的人数int count = 0;// 创建一个布尔数组标记已经统计过的人boolean[] visited = new boolean[n];// 遍历确诊病例编号，找出需要进行核酸检测的人for (int caseId : confirmedCasesStr) {// 找到确诊病例的根节点int root = pt.find(caseId);// 遍历所有人，找出与确诊病例在同一集合中但未被统计的人for (int i = 0; i < n; i++) {if (pt.find(i) == root && i != caseId && !visited[i]) {count++;// 输出需要核酸检测的人数System.out.println("需要核酸检测的人数: " + count);// 标记此人已统计visited[i] = true;}}}// 调整计数，减去确诊病例人数count = count - confirmedCasesStr.length;// 输出最终需要进行核酸检测的人数System.out.println("需要进行核酸检测的人数: " + count);}
}

方法二：深度优先搜索（DFS）或广度优先搜索（BFS）

初始化访问数组：创建一个大小为N的数组，用于记录每个人员是否已被访问过。
遍历确诊病例：对于每个确诊病例，如果未被访问过，则进行DFS或BFS遍历。
搜索接触者：在DFS或BFS过程中，对于每个当前节点，遍历其所有接触者（即矩阵中对应行为1的列），如果接触者未被访问过，则标记为已访问并继续搜索。
统计人数：遍历结束后，统计被访问过的人数（不包括确诊病例自身），即为需要进行核酸检测的人数。

`代码实现`

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class PreciseNucleicAcidTesting {private static final Logger log = LoggerFactory.getLogger(PreciseNucleicAcidTesting.class);// 使用邻接表表示图private final List<List<Integer>> graph;private final boolean[] visited;/*** 构造函数，用于初始化精确核酸检测对象* 创建一个包含n个顶点的图，并初始化每个顶点的邻接列表和访问标记数组** @param n 图中顶点的数量，代表需要进行核酸检测的人员数量*/public PreciseNucleicAcidTesting(int n) {// 初始化图的邻接列表graph = new ArrayList<>();// 循环添加n个空的邻接列表到graph中for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());}// 初始化访问标记数组，用于标记每个顶点是否被访问过visited = new boolean[n];}/*** 添加一条边，表示两个个体之间的接触关系* 在接触追踪问题中，我们假设这是单向的接触，即u接触了v，并非v也接触了u* 因此，只在u的邻接列表中添加v，而不反过来添加** @param u 表示个体u的标识符* @param v 表示个体v的标识符*/public void addEdge(int u, int v) {// 向个体u的邻接列表中添加个体v，表示u接触了vgraph.get(u).add(v);// 无向图的话也需要添加下面这行//graph.get(v).add(u);// 但在这个问题中，我们假设是单向的接触追踪，所以只添加一行}// 深度优先搜索private void dfs(int node, Set<Integer> infectedSet) {// 标记当前节点为已访问visited[node] = true;// 假设node是确诊病例，则加入集合（实际中可能从外部传入确诊病例列表）infectedSet.add(node);// 遍历当前节点的所有邻居for (int neighbor : graph.get(node)) {log.info("当前节点：{},邻居节点:{}",node,neighbor);// 如果邻居节点未被访问过，则递归调用dfsif (!visited[neighbor]) {dfs(neighbor, infectedSet);}}}// 计算需要进行核酸检测的人数（不包括确诊病例自身）public int countPeopleForTesting(List<Integer> confirmedCases, int n) {// 初始化visited数组Arrays.fill(visited, false);// 使用HashSet存储感染人群，避免重复Set<Integer> infectedSet = new HashSet<>();// 对每个确诊病例进行深度优先搜索（DFS），以找出所有接触者for (int caseId : confirmedCases) {if (!visited[caseId]) {dfs(caseId, infectedSet);}}// 计算需要进行核酸检测的人数，不包括确诊病例自身// 通过HashSet的size减去确诊病例的数量实现// 注意处理没有额外接触者的情况，即所有人在确诊病例中int size = infectedSet.size() - confirmedCases.size();// 返回需要进行核酸检测的人数（不包括确诊病例自身，但在这个实现中包括了）return size;}public static void main(String[] args) {PreciseNucleicAcidTesting testing = new PreciseNucleicAcidTesting(10);testing.addEdge(0, 1);testing.addEdge(0, 2);testing.addEdge(1, 3);testing.addEdge(2, 4);testing.addEdge(2, 5);testing.addEdge(3, 6);testing.addEdge(5, 7);testing.addEdge(5, 8);testing.addEdge(7, 9);List<Integer> confirmedCases = Arrays.asList(0, 2); // 假设0和2是确诊病例int peopleForTesting = testing.countPeopleForTesting(confirmedCases, 10);System.out.println("需要进行核酸检测的人数（不包括确诊病例自身）:" + peopleForTesting); // 输出应该是8（1, 3, 4, 5, 6, 7, 8, 9中去掉0和2）}
}

方法三：栈和访问数组

初始化栈和访问数组：创建一个栈用于存储待处理的节点，一个大小为N的数组用于记录每个人员是否已被访问过。
将确诊病例入栈：将确诊病例编号存入栈中，并标记为已访问。
遍历栈中元素：当栈不为空时，弹出栈顶元素，并遍历其对应行，找到未访问且有接触的节点，将其入栈并标记为已访问。
统计人数：遍历结束后，统计被访问过的人数（不包括确诊病例自身），即为需要进行核酸检测的人数。

`代码实现`

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;import java.util.Arrays;
import java.util.Collections;
import java.util.Objects;
import java.util.Stack;/** 方法一：并查集* 初始化并查集：根据总人数N初始化并查集，每个节点初始时都是独立的连通分量。* 合并接触关系：遍历接触矩阵，对于matrix[i][j]为1的情况，将i和j所属的连通分量合并。* 统计连通分量：遍历并查集，统计每个连通分量中的节点数，即每个接触群体的人数。* 计算核酸检测人数：遍历确诊病例人员编号，找到每个确诊病例所属的连通分量，并统计这些连通分量中除了确诊病例外的总人数。**/
public class PrecisionTestingStack {private static final Logger log = LoggerFactory.getLogger(PrecisionTestingStack.class);public static void main(String[] args) {// 输入总人数 Nint n = 10;// 输入确诊病例编号int[] confirmedCases = {0, 2};// 定义接触关系二维数组，表示谁和谁接触过int[][] contacts = {{0, 1},{0, 2},{1, 3},{2, 4},{2, 5},{3, 6},{5, 7},{5, 8},{7, 9}};// 调用方法三计算需要进行核酸检测的人数int count = methodThree(n, confirmedCases, contacts);// 输出结果System.out.println("需要进行核酸检测的人数: " + count);}/*** 方法三：栈和访问数组** @param n 总人数* @param confirmedCases 确诊病例编号数组* @param contacts 接触关系二维数组* @return 需要进行核酸检测的人数*/public static int methodThree(int n, int[] confirmedCases, int[][] contacts) {// 初始化栈和访问数组Stack<Integer> stack = new Stack<>();  // 创建栈用于存储待处理的节点boolean[] visited = new boolean[n];    // 创建一个大小为N的数组用于记录每个人员是否已被访问过// 将确诊病例入栈for (int caseId : confirmedCases) {stack.push(caseId);  // 将确诊病例编号存入栈中visited[caseId] = true;  // 标记确诊病例为已访问}// 遍历栈中元素while (!stack.isEmpty()) {  // 当栈不为空时int current = stack.pop();  // 弹出栈顶元素// 遍历当前人员的所有接触者for (int[] contact : contacts) {if (contact[0] == current) {  // 找到与当前人员有接触的节点int next = contact[1];  // 获取接触者编号if (!visited[next]) {  // 如果接触者未被访问过stack.push(next);  // 将接触者入栈visited[next] = true;  // 并标记为已访问}log.info("-------------------");log.info("当前节点：{},邻居节点:{}",current,next);} else if (contact[1] == current) {  // 反向检查，确保所有接触者都被考虑int next = contact[0];if (!visited[next]) {stack.push(next);visited[next] = true;}log.info("---------------------");log.info("感染节点：{},被感染节点:{}",current,next);}}}// 统计人数int count = 0;for (int i = 0; i < n; i++) {if (visited[i] && !Objects.equals(confirmedCases, i)) {  // 统计被访问过的人数（不包括确诊病例自身）count++;}}count=count-confirmedCases.length;// 返回需要进行核酸检测的人数return count;}}