西山居笔试 西山居笔试题 0414
笔试时间: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]:
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024 BAT笔试合集 文章被收录于专栏
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。