笔试时间：2025年10月15日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

有一个故障字符串序列由多行组成，每一行内有多个字符串，分别用空格隔开。现需要对这个字符串序列进行限流显示处理，显示规则如下：

1. 输入的第一行为一个数字，表示限流参数
2. 从第2行开始为要处理的字符串数据，我们需要将每一行数据流入一个缓存控制器，缓存中的信息包括字符串和其个数信息
3. 每行输入数据中的字符串可能在缓存中有重复，如果有重复需要在缓存中对字符串的个数累加
4. 每一行流入后需要从当前缓存中取出最早的数据进行输出，取出的数据上限为限流参数，如果数据未取完将继续保存在缓存中，取出的数据将从缓存中删除，后续缓存的相同字符串将重新开始计数

输入描述

输出描述

样例输入

5

abc a b c

ad bc

样例输出

abc 1 a 1 b 1 c 1

null

ad 1 bc 1

样例说明

限制单次输出5个不同字符串。第一行输入为abc a b c，输入后缓存是abc a b c，次数均为1，因此第一行输出是abc 1 a 1 b 1 c 1。第2行输入为空行，之前缓存为空，输入后缓存是空，因此第2行输出为null。第3行输入为ad bc，之前缓存为空，输入后缓存是ad bc，次数均为1，因此第3行输出为ad 1 bc 1。

参考题解

解题思路：

1. 维护一个缓存系统，使用队列保存字符串的输入顺序（先进先出）
2. 使用字典记录每个字符串的当前计数
3. 对于每个输入的字符串：如果已存在则计数+1（队列中位置不变），如果不存在则计数设为1并加入队列末尾
4. 输出阶段：从队列头部取出最多n个字符串，输出这些字符串及其计数，并从缓存中删除

C++：

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
#include <sstream>
using namespace std;

int main() {
    int x;
    cin >> x;
    cin.ignore();
    
    unordered_map<string, int> cnt;
    queue<string> q;
    string line;
    
    while (getline(cin, line)) {
        istringstream iss(line);
        string word;
        vector<string> arr;
        
        while (iss >> word) {
            arr.push_back(word);
        }
        
        for (const string& t : arr) {
            if (cnt.count(t)) {
                cnt[t]++;
            } else {
                cnt[t] = 1;
                q.push(t);
            }
        }
        
        if (x == 0) {
            cout << "null" << endl;
            continue;
        }
        
        int k = min(x, (int)q.size());
        if (k == 0) {
            cout << "null" << endl;
            continue;
        }
        
        vector<string> res;
        for (int i = 0; i < k; i++) {
            res.push_back(q.front());
            q.pop();
        }
        
        for (int i = 0; i < res.size(); i++) {
            if (i > 0) cout << " ";
            cout << res[i] << " " << cnt[res[i]];
            cnt.erase(res[i]);
        }
        cout << endl;
    }
    
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = Integer.parseInt(scanner.nextLine());
        
        Map<String, Integer> cnt = new HashMap<>();
        Queue<String> q = new LinkedList<>();
        
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.isEmpty()) {
                if (x == 0 || q.isEmpty()) {
                    System.out.println("null");
                }
                continue;
            }
            
            String[] arr = line.split("\\s+");
            for (String t : arr) {
                if (cnt.containsKey(t)) {
                    cnt.put(t, cnt.get(t) + 1);
                } else {
                    cnt.put(t, 1);
                    q.offer(t);
                }
            }
            
            if (x == 0) {
                System.out.println("null");
                continue;
            }
            
            int k = Math.min(x, q.size());
            if (k == 0) {
                System.out.println("null");
                continue;
            }
            
            List<String> res = new ArrayList<>();
            for (int i = 0; i < k; i++) {
                res.add(q.poll());
            }
            
            StringBuilder out = new StringBuilder();
            for (String s : res) {
                if (out.length() > 0) out.append(" ");
                out.append(s).append(" ").append(cnt.get(s));
                cnt.remove(s);
            }
            System.out.println(out);
        }
        
        scanner.close();
    }
}

Python：

import sys
from collections import deque

def work():
    x = int(sys.stdin.readline().strip())
    cnt = {}
    q = deque()
    
    while True:
        ln = sys.stdin.readline()
        ln = ln.strip()
        if not ln:
            break
        
        arr = ln.split()
        for t in arr:
            if t in cnt:
                cnt[t] += 1
            else:
                cnt[t] = 1
                q.append(t)
        
        if x == 0:
            print("null")
            continue
        
        k = x if x < len(q) else len(q)
        if k == 0:
            print("null")
            continue
        
        res = []
        for i in range(k):
            res.append(q.popleft())
        
        out = []
        for s in res:
            out.append(f"{s} {cnt[s]}")
            del cnt[s]
        
        print(" ".join(out))

work()

第二题

网络中有n台路由器，两台路由器之间最多只有一条链路双向连通，每条链路有对应的转发成本。以S为源节点进行转发时，会以S为根基于链路转发成本计算一棵最短路径树，S到其它的报文会沿着最短路径树进行转发。转发的下一跳定义如下：源节点S到目的节点D的最短路径上S的直连的邻居节点，用来指导报文从哪条链路转发。需要注意的是，最短路径树中最短路径可能不止一条，对应转发的下一跳可能存在多个。

任务：给定路由器数量和路由器之间的连通关系及转发成本，并指定两个路由器S、D，计算以D为目的时，S到D的最小转发代价，以及S的转发下一跳的集合。

输入描述

输出描述

样例输入

4 3

1 2 5

1 3 5

2 3 5

1 4

样例输出

-1

-1

样例说明

1作为源路由器，4作为目的路由，1→4路径不可达，最小转发代价为-1，转发下一跳集合为空

参考题解

解题思路：

使用改进的Dijkstra算法求最短路径，特殊处理下一跳信息：

1. 初始化源节点S到邻居节点的距离为链路成本，下一跳就是邻居本身
2. 当找到更短路径时，下一跳集合继承自前驱节点的下一跳
3. 当找到等长路径时，下一跳集合合并前驱节点的下一跳

C++：

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <climits>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < k; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    
    int s, d;
    cin >> s >> d;
    
    if (s == d) {
        cout << 0 << "\n-1\n";
        return 0;
    }
    
    const int INF = INT_MAX;
    vector<int> dis(n + 1, INF);
    vector<set<int>> nh(n + 1);
    dis[s] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    
    for (auto& [v, c] : g[s]) {
        if (dis[v] > c) {
            dis[v] = c;
            nh[v] = {v};
            pq.push({c, v});
        } else if (dis[v] == c) {
            nh[v].insert(v);
        }
    }
    
    while (!pq.empty()) {
        auto [x, u] = pq.top();
        pq.pop();