筆試時間：2025年04月03日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目

假設(shè)你正在開發(fā)地圖數(shù)據(jù)校驗工具，其中有一個功能是檢測城市的道路網(wǎng)絡(luò)是否連通。具體來說，就是判斷從任何一個地點出發(fā)，能否通過現(xiàn)有的道路到達其他任何地點。為此，我們需要設(shè)計一個算法來驗證這一點。

輸入描述

第一行包含兩個整數(shù) n 和 m，分別表示城市中有多少個地點以及有多少條雙向道路。每個地點都有唯一的編號，范圍是 [1, n]。

接下來 m 行，每行包含兩個整數(shù) a 和 b，表示地點 a 和地點 b 之間有一條雙向道路相連。

輸出描述

輸出一行字符串，如果城市的所有地點都是相互連通的，則輸出 "Yes"；否則，輸出 "No"。

樣例輸入

5 6

0 1

0 2

1 3

2 3

3 4

1 4

樣例輸出

Yes

參考題解

用 鄰接表（List） 存儲圖結(jié)構(gòu)：graph[i] 存儲 與地點 i 相連的所有地點。構(gòu)建圖。讀取 m 條邊，每條邊連接 a 和 b，表示地點 a 和 b 之間有道路：由于是 無向圖，所以 graph[a].add(b) 和 graph[b].add(a) 都需要添加。深度優(yōu)先搜索（DFS）遍歷。使用 visited[] 數(shù)組 記錄哪些節(jié)點被訪問過。從 0 號節(jié)點 開始執(zhí)行 DFS，遞歸訪問所有能到達的節(jié)點。判斷連通性。遍歷 visited[] 數(shù)組，檢查是否所有節(jié)點都被訪問：若 visited[i] == false（有未訪問的節(jié)點），說明圖不連通，輸出 "No"。否則，輸出 "Yes"，表示所有節(jié)點都能相互到達。

C++：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

#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：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

import java.util.*;

public class MapDataVerification {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 讀取地點數(shù)量和道路數(shù)量
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 構(gòu)建鄰接表表示圖
        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);
        }

        // 標記節(jié)點是否被訪問過
        boolean[] visited = new boolean[n];
        // 從節(jié)點 0 開始深度優(yōu)先搜索
        dfs(graph, 0, visited);

        // 檢查是否所有節(jié)點都被訪問過
        boolean isConnected = true;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                isConnected = false;
                break;
            }
        }

        // 輸出結(jié)果
        System.out.println(isConnected ? "Yes" : "No");
    }

    private static void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
        // 標記當前節(jié)點為已訪問
        visited[node] = true;
        // 遍歷當前節(jié)點的所有鄰居節(jié)點
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(graph, neighbor, visited);
            }
        }
    }
}    

Python：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

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中，實現(xiàn)為用戶推薦最近的3個充電樁的功能，需求如下：

給出用戶所在位置，以及N個備選充電樁位置，返回距離用戶最近且距離小于3km的前3個充電樁。

輸入描述

第一行包含兩個整數(shù)n和m，分別表示有向圖中有多少個點以及有多少條邊。每個點都有唯一的編號，范圍是[0, n]。

第二行包含一個整數(shù)，為用戶所在NodeID。

第三行包含一個整數(shù)k，為備選充電樁個數(shù)。

接下來k行，每行一個整數(shù)，為備選充電樁所在NodeID。

接下來m行，每行包含三個整數(shù)a、b、w，表示點a和點b之間有一條單向邊，權(quán)重為w(單位米)。

輸出描述

最近的充電樁的NodeID和距離，用"NodeID,Distance"表達，多個樁以";"分隔，若沒有結(jié)果則返回"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

參考題解

構(gòu)建圖數(shù)據(jù)結(jié)構(gòu)用 List<List<Edge>> 存儲有向圖，每個點存儲連接的邊（鄰接表）。讀取 m 條邊的信息，建立圖結(jié)構(gòu)。Dijkstra 算法求最短路徑使用 優(yōu)先隊列（堆） 維護當前最短路徑。遍歷所有可達點，更新到達該點的最短路徑。篩選 & 排序篩選出 距離小于 3000m 的充電樁。按 距離升序排序，取 最近的 3 個。格式化輸出按 NodeID,Distance 形式輸出，多個樁用 ; 分隔。若無滿足條件的充電樁，返回 "None"。復雜度分析Dijkstra 算法：O((N + M) log N)，N 是點數(shù)，M 是邊數(shù)。充電樁篩選 & 排序：O(K log K)，K 是充電樁數(shù)?？傮w復雜度 ≈ O((N + M) log N) + O(K log K)，適用于 大規(guī)模地圖數(shù)據(jù)。

C++：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

#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