笔试时间：2024年04月14日

历史笔试传送门：2023秋招笔试合集

第一题

题目：岛群统计

某个市有n座小岛，部分彼此相连。其中，如果小岛a与小岛b直接相连,小岛b又小岛c相连时,我们认为小岛a与小岛c间接相连。我们规定,岛群是相连(直接或者间接)相连小岛的集合,其中不包含没有相连的小岛；你是这个市的市长,想将这些小岛划分为岛群管理，现在需要统计岛群的数量。

补充说明

给你—个n*n的矩阵connectedArray, 其中connectedArray[i][j]=1表示第i个小岛和第j个小岛直接相连,而connectedArray[il[j]=0表示不直接相连, 返回connectedArray中岛群的数量。

样例输入一

[[1,1,0],[1,1,0],[0,0,1]

样例输出一

2

样例输入二

[[1,0,0],[0,1,0],[0,0,1]]

样例输出二

3

参考题解

无向图中有几个连通块，可以使用DFS、BFS、或者并查集。

C++：[此代码未进行大量数据的测试，仅供参考]

class Solution {
public:
    int getIsLandGroupCount(vector<vector<int> >& a) {
        int n = a.size();
        vector<bool> vis(n, false);
        int ans = 0;
        auto dfs = [&](auto&& self, int i) ->void{
            vis[i] = true;
            for (int j = 0; j < n; ++j) {
                if (a[i][j] && !vis[j]) {
                    self(self, j);
                }
            }
        };
        for (int i = 0; i < n; ++i) {
            if (vis[i]) continue;
            dfs(dfs, i);
            ++ans;
        }
        return ans;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

class Solution {
    public int getIsLandGroupCount(int[][] a) {
        int n = a.length;
        boolean[] vis = new boolean[n];
        int ans = 0;

        // 定义深度优先搜索函数
        Runnable dfs = new Runnable() {
            private void dfsUtil(int i) {
                vis[i] = true;
                for (int j = 0; j < n; ++j) {
                    if (a[i][j] == 1 && !vis[j]) {
                        dfsUtil(j);
                    }
                }
            }

            @Override
            public void run() {
                for (int i = 0; i < n; ++i) {
                    if (!vis[i]) {
                        dfsUtil(i);
                        ++ans;
                    }
                }
            }
        };

        // 执行深度优先搜索
        dfs.run();
        return ans;
    }

Python：[此代码未进行大量数据的测试，仅供参考]

class Solution:
    def getIsLandGroupCount(self, a):
        n = len(a)
        vis = [False] * n
        ans = 0

        def dfs(i):
            vis[i] = True
            for j in range(n):
                if a[i][j] == 1 and not vis[j]:
                    dfs(j)

        for i in range(n):
            if not vis[i]: