IT评测·应用市场-qidao123.com

标题: 【华为OD机考真题】- 必要广播的服务器数量（Java） [打印本页]
作者: 南七星之家    时间: 2025-3-13 19:15
标题: 【华为OD机考真题】- 必要广播的服务器数量（Java）
[img]https://i-blog.csdnimg.cn/direct/ebc80bc863

f441

8d895583

3

2854c24d2.gif[/img]
    &#x1

f3

c6;本文收录于「2025华为OD机试真题(Java版)」专栏，手把手带你零基础教学华为OD机试，通过Java语言进行解题，助你突破OD机试，轻松登陆&#xff01

;同时，欢迎大家关注&&收藏&&订阅&#xff01

;疯狂收录中，up&#xff01

;up&#xff01

;up&#xff01

;&#xff01

;
一次订阅，终身使用，后续更新都能学习。
提醒&#xff1

a;拒绝一切代考/替考，违法必究&#xff01

;
  
&#x1

f4da;1

. 题目形貌

   具体题目形貌如下&#xff1

a;
服务器连接方式包括直接相连，间接连接。A和B直接连接，B和C直接连接，则A和C间接连接。
直接连接和间接连接都可以发送广播。
给出一个N*N 数组，代表N个服务器， matrix[j] &#61

;&#61

; 1

，则代表 i 和 j 直接连接&#xff1

b;不等于1

时，代表 i 和 j不直接连接。
matrix &#61

;&#61

; 1

，即自己和自己直接连接。 matrix[j] &#61

;&#61

; matrix[j]。计算初始必要给几台服务器广播，才可以使每个服务器都收到广播。
  
  
   温馨提醒&#xff1

a; 大家在参加华为OD机试时，牢记不要仅仅死记硬背题解代码。真正的通过率取决于你对代码的明白能力。建议你在明白基本原理和逻辑的基础上，模拟并自己编写代码，这样才能更有效地应对机试。
  &#x1

f4dd;2. 输入形貌

输入为N行，每行有N个数字，为0或1

，由空格分隔，构成 N*N 的数组，N的范围为1

<&#61

;N<&#61

; 40
&#x1

f5a5;️3

. 输出形貌

输出一个数字为必要广播的服务器的数量。
&#x1

f50d;4. 示例演示

[size=3

]✨4.1

示例1



输入&#xff1

a;
  1. 1
  3. 0 0
  4. 0 1
  6. 0
  7. 0 0 1
复制代码
输出&#xff1

a;
  1. 3
复制代码
示例说明&#xff1

a; 3

台服务器互不连接，所以必要分别广播这3

台服务器。
[size=3

]✨4.2 示例2

输入&#xff1

a;
  1. 1
  3. 1
  6. 1
  8. 1
复制代码
输出&#xff1

a;
  1. 1
复制代码
示例说明&#xff1

a; 2 台服务器相互连接，所以只必要广播基中一台服务器。
&#x1

f51

1

;5. 解题分析

[size=3

]&#x1

f91

4;5.1

题目明白

在这个题目中，我们必要根据给定的连接关系，计算出至少必要多少个服务器来进行广播。具体来说，给定一个 N*N 的矩阵，矩阵中的每个元素 matrix[j] 表示第 i 台服务器与第 j 台服务器是否有直接连接，若 matrix[j] &#61

; 1

则表示有连接，若为 0 则表示没有连接。
使命是找到连接的服务器组，每个服务器组内部全部服务器直接或间接连接，即只要一个服务器的广播就能使得该组内的全部服务器都能吸收到信号。我们必要计算最少必要几个服务器来完成广播。
[size=3

]&#x1

f4a1

;5.2 解题思路

[list=1

]
  • 图的表示&#xff1

    a;

    • 将服务器之间的连接看作一个图，其中每个节点代表一台服务器，边表示服务器之间的连接。
    • 如果两个节点之间有直接连接，意味着它们属于同一组，不必要额外的服务器。

  • 探求连接的组&#xff1

    a;

    • 我们必要找到图中全部互相连接的子图，也就是不同的服务器组。可以使用深度优先搜索（DFS）来遍历图并找到这些组。

  • 最小服务器数&#xff1

    a;

    • 每个服务器组必要一个服务器来进行广播。因此，我们只必要计算图中有多少个连通子图，即可得到最小的服务器数量。

  • DFS遍历&#xff1

    a;

    • 对每个没有被访问的节点（服务器）进行DFS遍历，找到一个连通子图并标志全部与之连接的节点，遍历竣过后增长服务器的数量。

    [size=3

    ]&#x1

    f3

    af;5.3

    题目考点



    • 图的遍历&#xff1

      a;深度优先搜索（DFS）用于遍历图，找到全部的连通分量。
    • 数据结构&#xff1

      a;使用二维数组表示图，使用布尔数组记载哪些节点已经访问过。
    • 图的连通性&#xff1

      a;利用DFS可以有效地找到全部互相连接的节点。
    [size=3

    ]&#x1

    f4dd;5.4 解题步调

    [list=1

    ]
  • 输入数据&#xff1

    a;读取矩阵大小 N 和连接矩阵 matrix。
  • 初始化&#xff1

    a;创建一个布尔数组 visited 来记载哪些服务器已经被访问。
  • 深度优先搜索（DFS）&#xff1

    a;遍历每个服务器，如果该服务器没有被访问过，则调用DFS来标志全部与它相连的服务器。
  • 计算组数&#xff1

    a;每调用一次DFS，就表示找到一个新的服务器组，计数器加一。
  • 输出结果&#xff1

    a;输出最小的服务器数量，即图中连通子图的个数。
    &#x1

    f4bb;6. 解题Coding

      根据如上题解思路，进行代码实战，大家请看如下，建议不要死记硬背代码，要明白其题型及实现思路，别担心，代码我都会给出超具体注释，你肯定能看明白的。
    [size=3

    ]&#x1

    f5a5;6.1

    代码实现

    1. package com.demo.java.OD1
    3. 01
    5. _1
    7. 50.OD1
    9. 3
    11. 7;import java.util.Scanner;/** * @author bug菌 * @Source 公众号&#xff1
    13. a;猿圈奥妙屋 * @des&#xff1
    15. a; 【必要广播的服务器数量】题目 * @url&#xff1
    17. a; https://blog.csdn.net/weixin_43
    19. 970743
    21. /article/details/1
    23. 4572981
    25. 6 */public class OdMain {    public static int count &#61
    27. ; 0;  // 用于记载符合条件的节点数量    public static void main(String[] args) {        Scanner sc &#61
    29. ; new Scanner(System.in);        // 读取输入并分割成字符串数组        String[] inputStr &#61
    31. ; sc.nextLine().split(&#3
    33. 4; &#3
    35. 4;);        int n &#61
    37. ; inputStr.length;  // 获取节点数（图的大小）        // 创建一个n * n的二维数组，用于存储图的毗邻矩阵        int[][] arr &#61
    39. ; new int[n][n];        // 解析第1
    41. 行输入，填充毗邻矩阵的第一行        for (int i &#61
    43. ; 0; i < n; i&#43
    45. ;&#43
    47. ;) {            arr[0][i] &#61
    49. ; Integer.parseInt(inputStr[i]);        }        // 读取剩余的毗邻矩阵数据        for (int i &#61
    51. ; 1
    53. ; i < n; i&#43
    55. ;&#43
    57. ;) {            String[] s &#61
    59. ; sc.nextLine().split(&#3
    61. 4; &#3
    63. 4;);            for (int j &#61
    65. ; 0; j < n; j&#43
    67. ;&#43
    69. ;) {                arr[i][j] &#61
    71. ; Integer.parseInt(s[j]);  // 将每一行的数据填充到矩阵中            }        }        // 创建一个布尔数组，标志每个节点是否被访问过        boolean[] visited &#61
    73. ; new boolean[n];        // 遍历全部节点，若该节点未被访问过，则从该节点开始进行DFS        for (int i &#61
    75. ; 0; i < n; i&#43
    77. ;&#43
    79. ;) {            if (!visited[i]) {                dfs(arr, visited, i);  // 从节点i开始深度优先搜索            }        }        // 输出符合条件的节点数量        System.out.println(count);    }    // 深度优先搜索函数    public static void dfs(int[][] arr, boolean[] visited, int index) {        visited[index] &#61
    81. ; true;  // 标志当前节点为已访问        boolean flag &#61
    83. ; true;  // 标志变量，用于判断是否存在未访问的毗邻节点        // 遍历当前节点的全部毗邻节点        for (int i &#61
    85. ; index &#43
    87. ; 1
    89. ; i < arr.length; i&#43
    91. ;&#43
    93. ;) {            if (arr[index][i] &#61
    95. ;&#61
    97. ; 1
    99. ) {  // 如果存在边，即arr[index][i] &#61
    101. ;&#61
    103. ; 1
    105.                 flag &#61
    107. ; false;  // 存在未访问的毗邻节点，设置flag为false                dfs(arr, visited, i);  // 对该毗邻节点进行递归DFS            }        }        // 如果当前节点没有未访问的毗邻节点，意味着它是一个终止节点        if (flag) {            count&#43
    109. ;&#43
    111. ;;  // 终止节点数量&#43
    113. ;1
    115.         }    }}
    复制代码
    [size=3

    ]⏱6.2 时间&空间复杂度



    • 时间复杂度&#xff1

      a;O(N^2)，其中 N 是服务器的数量。由于我们必要遍历整个矩阵来执行DFS，时间复杂度是O(N^2)，这是因为我们必须检查每对大概的服务器连接。
    • 空间复杂度&#xff1

      a;O(N)，我们必要一个大小为 N 的 visited 数组来记载服务器的访问状态，并且必要栈空间用于DFS的递归。
    [size=3

    ]&#x1

    f50d;6.3

    代码解析

    以下是代码的主要步调和解析&#xff1

    a;
    [list=1

    ]
  • 输入解析&#xff1

    a;

    • 步伐起首通过 Scanner 读取输入。第一行输入被分割成字符串数组，确定图的大小 n（图的节点数）。
    • 然后，通过毗邻矩阵表示图的边，读取后续的 n-1

      行并存储在二维数组 arr 中。arr[j] 表示节点 i 和节点 j 之间是否有边（1

      表示有边，0表示无边）。

  • 深度优先搜索（DFS）&#xff1

    a;

    • 使用 DFS 遍历图。dfs 方法通过递归实现深度优先搜索。
    • 参数 arr 是毗邻矩阵，visited 是标志每个节点是否已访问的布尔数组，index 是当前搜索的节点索引。
    • 每当 DFS 访问一个节点时，标志该节点为已访问，并继续遍历它的毗邻节点。

  • 标志终止节点&#xff1

    a;

    • 对于每个节点，如果该节点没有未访问的毗邻节点（即在 dfs 中遍历到的全部毗邻节点都已访问），则它被认为是一个终止节点。
    • 如果节点是终止节点，count 变量就增长1

      。

  • 结果输出&#xff1

    a;

    • 在遍历全部节点后，输出 count，即满足条件的终止节点的数量。

    焦点思路


    • 图的表示&#xff1

      a;       使用毗邻矩阵表示无向图，其中矩阵中的 arr[j] 为 1

      表示存在边，0 表示不存在边。
    • 深度优先搜索&#xff1

      a;       对每个未访问的节点，调用 DFS 递归函数，访问其全部毗邻节点。若当前节点没有未访问的毗邻节点，它就被认为是一个终止节点。
    • 终止节点的界说&#xff1

      a;       终止节点是指在 DFS 中无法进一步访问的节点，即没有毗邻节点未被访问。
    [size=3

    ]&#x1

    f4dd;6.4 小结

    通过使用DFS遍历，我们有效地找到了全部互相连接的服务器组，并计算了最小的服务器数量。通过图的遍历和递归算法，我们可以或许高效地解决这个题目，确保服务器的最小广播数量。
    &#x1

    f9ea;7. 测试用例

    针对如上题解，这里我们再进行几个测试用例的实测，并会给出实际运行结果截图，方便大家核验。
    [size=3

    ]&#x1

    f9ea;7.1

    测试用例1



    &#x1

    f5a5;️7.1

    .1

    输入

    1. 1
    3. 0 0
    4. 0 1
    6. 0
    7. 0 0 1
    复制代码
    &#x1

    f5a5;️7.1

    .2 输出

    1. 3
    复制代码
    &#x1

    f5a5;️7.1

    .3

    实际运行结果展示

    根据本地代码进行方法测试，本地运行结果展示如下&#xff1

    a;
    [img]https://i-blog.csdnimg.cn/direct/e65a7d21

    797b4f1

    aa8e3

    840990c6a546.png[/img]

    [size=3

    ]&#x1

    f9ea;7.2 测试用例2

    &#x1

    f5a5;️7.2.1

    输入

    1. 1
    3. 1
    6. 1
    8. 1
    复制代码
    &#x1

    f5a5;️7.2.2 输出

    1. 1
    复制代码
    &#x1

    f5a5;️7.2.3

    实际运行结果展示

    根据本地代码进行方法测试，本地运行结果展示如下&#xff1

    a;
    [img]https://i-blog.csdnimg.cn/direct/cb47920af3

    b84ad98cdab257864f3

    8a9.png[/img]

    &#x1

    f4e5;8. 附录源码

      针对如上分享OD机试真题之外，这里我还开源全部OD机试原真题源码，供同学们一对一学习&#xff01

    ;对照每题都有题目号及具体代码注释。Gitee，例如题序号为1

    ，则题解代码对应文件夹OD1

    ，题序号为5，则题解代码对应文件夹OD5，以此类推，目标就是为了方便大家学习，一举登陆&#xff01

    ;(这里的题序号指专栏导航贴中表格一列的序号)
    [img]https://i-blog.csdnimg.cn/direct/dba894b43

    0d04f9c9c7affb078451

    1

    8e.png[/img]

    &#x1

    f9e7;福利赠与你&#x1

    f9e7;

      如果你还想学习更多干系OD真题题解，都建议直接毫不夷由地学习此专栏「2024华为OD机试真题(全栈版)」，快速掌握Java、Python、C&#43

    ;&#43

    ;、JavaScript等多种热门语言具体解题，快速突破华为OD机试，实现高分目标。还将提供线上多端答疑互换，解决你的全部题目&#xff01

    ;
    [size=3

    ]&#x1

    f3

    81

    ;安利其他语言版本题解册&#x1

    f3

    81

    ;



    • 【华为OD机试】2025年真题汇总A&#43

      ;B&#43

      ;C&#43

      ;D&#43

      ;E卷【Python实现】
    • 【华为OD机试】2025年真题汇总A&#43

      ;B&#43

      ;C&#43

      ;D&#43

      ;E卷【Java实现】
    • 【华为OD机试】2025年真题汇总A&#43

      ;B&#43

      ;C&#43

      ;D&#43

      ;E卷【C&#43

      ;&#43

      ;实现】
    • 【华为OD机试】2025年真题汇总A&#43

      ;B&#43

      ;C&#43

      ;D&#43

      ;E卷【JavaScript实现】
       上述专栏一次订阅，终身使用，后续更新都能学习。
      &#x1

    f469;‍&#x1

    f4bb;Who am I?

    我是bug菌，CSDN | 掘金 | InfoQ | 51

    CTO | 华为云 | 阿里云 | 腾讯云 等社区博客专家，C站博客之星Top3

    0，华为云多年度十佳博主&最具价值贡献奖，掘金多年度人气作者Top40，掘金等各大社区平台签约作者，51

    CTO年度博主Top1

    2，掘金/InfoQ/51

    CTO等社区优质创作者&#xff1

    b;全网粉丝合计 3

    0w&#43

    ;    &#xff1

    b;更多精彩福利点击这里&#xff1

    b;硬核微信公众号「猿圈奥妙屋」，欢迎你的参加&#xff01

    ;免费白嫖最新BAT互联网公司面试真题、4000G PDF电子册本、简历模板等海量资料，你想要的我都有，关键是你不来拿。
       
    [img]https://i-blog.csdnimg.cn/direct/f7f3

    d1

    c6201

    74b5ebd4d74b7255a3

    3

    ad.png[/img]
      -End-

    免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1

    23

    .com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



    欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4