阿里高德笔试 高德笔试 0403
笔试时间：2025年04月03日
历史笔试传送门：
第一题
题目
假设你正在开发地图数据校验工具，其中有一个功能是检测城市的道路网络是否连通。具体来说，就是判断从任何一个地点出发，能否通过现有的道路到达其他任何地点。为此，我们需要设计一个算法来验证这一点。
输入描述
第一行包含两个整数 n 和 m，分别表示城市中有多少个地点以及有多少条双向道路。每个地点都有唯一的编号，范围是 [1, n]。
接下来 m 行，每行包含两个整数 a 和 b，表示地点 a 和地点 b 之间有一条双向道路相连。
输出描述
输出一行字符串，如果城市的所有地点都是相互连通的，则输出 "Yes"；否则，输出 "No"。
样例输入
5 6
0 1
0 2
1 3
2 3
3 4
1 4
样例输出
Yes
参考题解
用 邻接表（List） 存储图结构：graph[i] 存储 与地点 i 相连的所有地点。构建图。读取 m 条边，每条边连接 a 和 b，表示地点 a 和 b 之间有道路：由于是 无向图，所以 graph[a].add(b) 和 graph[b].add(a) 都需要添加。深度优先搜索（DFS）遍历。使用 visited[] 数组 记录哪些节点被访问过。从 0 号节点 开始执行 DFS，递归访问所有能到达的节点。判断连通性。遍历 visited[] 数组，检查是否所有节点都被访问：若 visited[i] == false（有未访问的节点），说明图不连通，输出 "No"。否则，输出 "Yes"，表示所有节点都能相互到达。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
using namespace std;
void dfs(const vector<vector<int>>& graph, int node, vector<bool>& visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<bool> visited(n, false);
dfs(graph, 0, visited);
bool isConnected = true;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
isConnected = false;
break;
}
}
cout << (isConnected ? "Yes" : "No") << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class MapDataVerification {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取地点数量和道路数量
int n = scanner.nextInt();
int m = scanner.nextInt();
// 构建邻接表表示图
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 读取每条道路的信息并添加到图中
for (int i = 0; i < m; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
graph.get(a).add(b);
graph.get(b).add(a);
}
// 标记节点是否被访问过
boolean[] visited = new boolean[n];
// 从节点 0 开始深度优先搜索
dfs(graph, 0, visited);
// 检查是否所有节点都被访问过
boolean isConnected = true;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
isConnected = false;
break;
}
}
// 输出结果
System.out.println(isConnected ? "Yes" : "No");
}
private static void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
// 标记当前节点为已访问
visited[node] = true;
// 遍历当前节点的所有邻居节点
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def dfs(graph, node, visited):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
def main():
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False] * n
dfs(graph, 0, visited)
is_connected = all(visited)
print("Yes" if is_connected else "No")
if __name__ == "__main__":
main()
第二题
题目
在导航app中，实现为用户推荐最近的3个充电桩的功能，需求如下：
给出用户所在位置，以及N个备选充电桩位置，返回距离用户最近且距离小于3km的前3个充电桩。
输入描述
第一行包含两个整数n和m，分别表示有向图中有多少个点以及有多少条边。每个点都有唯一的编号，范围是[0, n]。
第二行包含一个整数，为用户所在NodeID。
第三行包含一个整数k，为备选充电桩个数。
接下来k行，每行一个整数，为备选充电桩所在NodeID。
接下来m行，每行包含三个整数a、b、w，表示点a和点b之间有一条单向边，权重为w(单位米)。
输出描述
最近的充电桩的NodeID和距离，用"NodeID,Distance"表达，多个桩以";"分隔，若没有结果则返回"None" 。
样例输入
6 8
0
3
2
3
5
0 1 100
1 2 150
2 3 300
3 4 200
0 4 200
4 5 100
5 3 200
1 4 100
2 5 200
样例输出
2,2500;5,3000;3,3500
参考题解
构建图数据结构用 List<List<Edge>> 存储有向图，每个点存储连接的边（邻接表）。读取 m 条边的信息，建立图结构。Dijkstra 算法求最短路径使用 优先队列（堆） 维护当前最短路径。遍历所有可达点，更新到达该点的最短路径。筛选 & 排序筛选出 距离小于 3000m 的充电桩。按 距离升序排序，取 最近的 3 个。格式化输出按 NodeID,Distance 形式输出，多个桩用 ; 分隔。若无满足条件的充电桩，返回 "None"。复杂度分析Dijkstra 算法：O((N + M) log N)，N 是点数，M 是边数。充电桩筛选 & 排序：O(K log K)，K 是充电桩数。总体复杂度 ≈ O((N + M) log N) + O(K log K)，适用于 大规模地图数据。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct Edge {
int to, weight;
Edge(int to, int weight) : to(to), weight(weight) {}
};
unordered_map<int, int> dijkstra(const vector<vector<Edge>>& graph, int start, int n) {
unordered_map<int, int> distances;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, start});
distances[start] = 0;
while (!pq.empty()) {
auto [dist, node] = pq.top(); pq.pop();
if (dist > distances[node]) continue;
for (const auto& edge : graph[node]) {
int newDist = dist + edge.weight;
if (!distances.count(edge.to) || newDist < distances[edge.to]) {
distances[edge.to] = newDist;
pq.push({newDist, edge.to});
}
}
}
return distances;
}
int main() {
int n, m, userNode, k;
cin >> n >> m >> userNode >> k;
unordered_set<int> chargers;
for (int i = 0; i < k; i++) {
int charger;
cin >> charger;
chargers.insert(charger);
}
vector<vector<Edge>> graph(n);
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
graph[a].emplace_back(b, w);
}
auto distances = dijkstra(graph, userNode, n);
vector<pair<int, int>> results;
for (int charg
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
