笔试时间：2025年5月28日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：找到通信质量最高的基站

闹市区中有一条马路，马路从0号路口开始，到N-1号路口结束，在每个路口都架设了最新技术的通信基站，每个基站的信号可以覆盖前后各k个路口的范围，即第i个路口上的基站，可以覆盖[i-k, i+k]这两个路口之间的马路，因此用户的手机处于多个基站的覆盖范围中。每个基站会统计当前接入人数，为保障最佳通信质量，用户手机应选择连接人数最少的基站进行通讯。这条马路一共N个路口，小明从0号路口出发向前走，求小明在每个路段中的最佳通讯基站。不考虑处于路口中间的特殊场景，只考虑在每个路段中的场景，例如第1个路段为0号路口到1号路口之间的路段，如果基站覆盖范围k=2，此时最佳基站应为0、1、2中连接人数最少的基站。

输入描述

输入为两行 第一行长度为N的整数数组crossroads[]，数组元素以空格分隔，其中crossroads[i]表示i号路口基站的当前接入人数。

1 <= crossroads.length数组长度 <= 10^5，0 <= crossroads[i] <= 10^2

第二行为基站覆盖范围k，1 <= k <= crossroads.length 非法输入返回-1

输出描述

返回一个数组ret，ret[i]表示i路段上最佳基站的编号，数组元素之间以空格分隔。例如0号路口到1号路口的路段，为0号路段，其最佳基站用ret[0]表示。

样例输入

3 5 8 7 6 7 4

2

样例输出

0 0 1 4 6 6

解释：小明在第1段路时，位于0号和1号基站中间，此时可以连接到0、1、2这3个基站，而这三个基站中连接人数最小的是0号基站（3个人），因此输出数组第一个元素应为0号基站。小明位于第2段路时，位于1号和2号基站中间，此时可以连接到0、1、2、3这4个基站，选择其中连接人数最小的基站，即0号基站（3人），因此输出数组第二个元素为0号基站。以此类推。

参考题解

对于每个路段 i，我们需要查找 [max(0, i-k+1), min(N-1, i+k-1)] 中的基站中接入人数最少者。我们从 i=0 到 i=N-2 遍历每个路段，并维护一个单调递增队列（按接入人数递增，若相等按编号递增）中的元素在当前窗口 [left, right] 内。单调队列维护：队列中始终保持从前到后是"更好"的基站（连接数更少或编号更小）滑动窗口：当窗口右移时，只需要移除过期的左边元素，添加新的右边元素时间复杂度：每个基站最多进队一次、出队一次，所以总体是O(n)

C++：

// C++17
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入路口信号强度
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<int> crossroads;
    int v;
    while (iss >> v) {
        crossroads.push_back(v);
    }
    int n = crossroads.size();

    // 读入 k
    int k;
    cin >> k;

    deque<int> dq;
    auto is_better = [&](int i, int j) {
        // 如果 i 的信号更弱(值更小)，或者信号相同且下标更小
        if (crossroads[i] != crossroads[j])
            return crossroads[i] < crossroads[j];
        return i < j;
    };

    vector<int> result;
    result.reserve(n-1);

    for (int i = 0; i < n - 1; ++i) {
        int left = max(0, i + 1 - k);
        int right = min(n - 1, i + k);

        // 移除队首超出左界的
        while (!dq.empty() && dq.front() < left) {
            dq.pop_front();
        }

        if (i == 0) {
            // 第一次，填满整个窗口 [left, right]
            for (int j = left; j <= right; ++j) {
                while (!dq.empty() && is_better(j, dq.back())) {
                    dq.pop_back();
                }
                dq.push_back(j);
            }
        } else {
            // 只添加新进入窗口的部分
            int prev_right = min(n - 1, (i - 1) + k);
            for (int j = prev_right + 1; j <= right; ++j) {
                while (!dq.empty() && is_better(j, dq.back())) {
                    dq.pop_back();
                }
                dq.push_back(j);
            }
        }

        // 队首即为当前最优基站下标
        result.push_back(dq.front());
    }

    // 输出结果，每行一个下标
    for (int idx : result) {
        cout << idx << "\n";
    }
    return 0;
}

Java：

// Java 8+
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取第一行并解析信号强度列表
        String[] parts = br.readLine().trim().split("\\s+");
        int n = parts.length;
        int[] crossroads = new int[n];
        for (int i = 0; i < n; i++) {
            crossroads[i] = Integer.parseInt(parts[i]);
        }
        // 读取 k
        int k = Integer.parseInt(br.readLine().trim());

        Deque<Integer> dq = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>(n - 1);

        // 判断 idx1 是否“更优”于 idx2
        Comparator<Integer> cmp = (i, j) -> {
            if (crossroads[i] != crossroads[j]) {
                return Integer.compare(crossroads[i], crossroads[j]);
            }
            return Integer.compare(i, j);
        };

        for (int i = 0; i < n - 1; i++) {
            int left = Math.max(0, i + 1 - k);
            int right = Math.min(n - 1, i + k);

            // 弹出超出左边界的
            while (!dq.isEmpty() && dq.peekFirst() < left) {
                dq.pollFirst();
            }

            if (i == 0) {
                // 初始窗口填充
                for (int j = left; j <= right; j++) {
                    while (!dq.isEmpty() && cmp.compare(j, dq.peekLast()) < 0) {
                        dq.pollLast();
                    }
                    dq.offerLast(j);
                }
            } else {
                // 仅添加新增右边界
                int prevRight = Math.min(n - 1, (i - 1) + k);
                for (int j = prevRight + 1; j <= right; j++) {
                    while (!dq.isEmpty() && cmp.compare(j, dq.peekLast()) < 0) {
                        dq.pollLast();
                    }
                    dq.offerLast(j);
                }
            }

            // 队首是当前最优基站
            result.add(dq.peekFirst());
        }

        // 输出
        PrintWriter pw = new PrintWriter(System.out);
        for (int idx : result) {
            pw.println(idx);
        }
        pw.flush();
    }
}

Python：

from collections import deque

def solve():
    crossroads = [int(c) for c in input().split()]
    k = int(input())
    n = len(crossroads)
    result = []

    # 单调双端队列，存储基站索引
    dq = deque()

    def is_better(idx1, idx2):
        return (crossroads[idx1] < crossroads[idx2] or
                (crossroads[idx1] == crossroads[idx2] and idx1 < idx2))

    # 处理每一段路
    for i in range(n - 1):
        left = max(0, i + 1 - k)
        right = min(n - 1, i + k)

        # 移除超出左边界的元素
        while dq and dq[0] < left:
            dq.popleft()

        # 添加新的右边界元素
        if i == 0:
            # 第一次，添加整个窗口
            for j in range(left, right + 1):
                while dq and is_better(j, dq[-1]):
                    dq.pop()
                dq.append(j)
        else:
            # 只添加新进入的元素
            prev_right = min(n - 1, (i - 1) + k)
            if right > prev_right:
                for j in range(prev_right + 1, right + 1):
                    while dq and is_better(j, dq[-1]):
                        dq.pop()
                    dq.append(j)

        # 队首就是当前最优解
        result.append(dq[0])

    return '\n'.join(map(str, result))


print(solve())

第二题：游园线路

某公园每年都会在新年时举办灯会，由于公园面积很大且各景点分散，希望你设计一条游园线路，从某个指定入口景点开始，到某个指定出口景点结束，使得游园总路程最短。最短路线不需要走完所有的景点，且中间允许经过其他出入口景点而不离开公园。

输入描述

第一行：N，景点个数，景点序号从0开始，N - 1结束。2 <= N <= 15

第二行至第N + 1行：是一个N*N的矩阵，表示各相邻景点之间的距离，距离为0表示不相邻。

第N + 2行：该景点是否是公园出入口（1是，0否）。

第N + 3行：要计算最短线路的入口景点序号和出口景点序号 所有用例的输入确保一定存在符合条件的线路，你无需考虑无解的情况。

输出描述

具体游园线路，如果有多条符合条件的线路，按景点序号从小到大进行排序。

样例输入

3

0 2 4

2 0 3

4 3 0

1 0 1

0 2

样例输出

0 2

解释：在出入口不难看出找出0->2是最短的。

参考题解

建立 dist[] 数组：存储从起点到每个点的最短距离

使用优先队列（最小堆）来加速每次选择“当前未处理、距离最小的节点”

不断松弛相邻边，更新最短距离

C++：

// C++17
#include <bits/stdc++.h>
using namespace std;

struct State {
    int dist;
    vector<int> path;
    bool operator>(const State &o) const {
        return dist > o.dist;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> graph(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> graph[i][j];

    // Read but ignore entrance_info
    for (int i = 0, x; i < n; i++) {
        cin >> x;
    }

    int start, end_;
    cin >> start >> end_;

    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0, {start}});
    vector<bool> seen(n, false);

    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        int u = cur.path.back();
        if (seen[u]) continue;
        seen[u] = true;

        if (u == end_) {
            for (int v : cur.path) {
                cout << v << ' ';
            }
            cout << "\n";
            return 0;
        }
        for (int v = 0; v < n; v++) {
            int w = graph[u][v];
            if (w > 0 && !seen[v]) {
                State next = cur;
                next.dist += w;
                next.path.push_back(v);
                pq.push(next);
            }
        }
    }
    return 0;
}

Java：

// Java 8+
import java.io.*;
import java.util.*;

public class Main {
    static class State implements Comparable<State> {
        int dist;
        List<Integer> path;
        State(int d, List<Integer> p) { dist = d; path = p; }
        public int compareTo(State o) {
            return Integer.compare(this.dist, o.dist);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().split("\\s+");
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(parts[j]);
            }
        }
        // Read and ignore entrance_info
        br.readLine();

        String[] se = br.readLine().split("\\s+");
        int start = Integer.parseInt(se[0]);
        int end = Integer.parseInt(se[1]);

        PriorityQueue<State> pq = new PriorityQueue<>();
        pq.offer(new State(0, new ArrayList<>(Arrays.asList(start))));
        boolean[] seen = new boolean[n];

        while (!pq.isEmpty()) {
            State cur = pq.poll();
            int u = cur.path.get(cur.path.size() - 1);
            if (seen[u]) continue;
            seen[u] = true;

            if (u == end) {
                StringBuilder sb = new StringBuilder();
                for (int v : cur.path) {
                    sb.append(v).append(' ');
                }
                System.out.println(sb.toString().trim());
                return;
            }
            for (int v = 0; v < n; v++) {
                int w = graph[u][v];
                if (w > 0 && !seen[v]) {
                    List<Integer> newPath = new ArrayList<>(cur.path);
                    newPath.add(v);
                    pq.offer(new State(cur.dist + w, newPath));
                }
            }
        }
    }
}

Python：

import heapq


def solve():
    n = int(input())
    graph = []
    for i in range(n):
        row = list(map(int, input().split()))
        graph.append(row)

    entrance_info = list(map(int, input().split()))

    start, end = map(int, input().split())

    # Dijkstra算法
    pq = [(0, [start])]
    visited = {}

    while pq:
        dist, path = heapq.heappop(pq)
        node = path[-1]

        if node in visited:
            continue
        visited[node] = (dist, path)

        if node == end:
            print(' '.join(map(str, path)))
            return

        for next_node in range(n):
            if graph[node][next_node] > 0 and next_node not in visited:
                new_dist = dist + graph[node][next_node]
                new_path = path + [next_node]
                heapq.heappush(pq, (new_dist, new_path))


solve()

第三题：爬山路线规划

给定一个二维数组 mountainMap 表示一座山的地图，数组中的每个元素 mountainMap[x][y] 代表坐标 (x, y) 处山的高度。登山员从山底出发，爬到山峰。

山底的含义：mountainMap中高度为0的坐标点。

山峰的含义：mountainMap中高度最高的坐标点。

登山员每次移动只能从当前位置向上下左右四个方向移动一格，向高处移动时，移动到的位置山的高度不能高于当前位置的高度加上固定的攀登能力值climbAbility；向低处移动时，移动到的位置的山的高度不能低于当前位置山的高度减去climbAbility。

请计算出从山底移动到山峰，最少需要移动几次？

输入描述

第一行为climbAbility的值

第二行为mountainMapRows mountainMapCols

从第三行开始为mountainMapRows行mountainMapCols列的高度二维数组mountainMap[mountainMapRows][mountainMapCols]，每行的高度数字中间用空格分割

输出描述

从山底移动到山峰，最少移动次数。 如果无法移动至山峰，则输出-1

样例输入

2

3 2

1 3

0 4

5 3

样例输出

5

解释：攀登能力为2，3行2列的山峰坐标，山底的坐标为(1,0)高度0，山峰的坐标为(2,0)高度5。仅有一条路线 初始位置山底(1,0)高度0->(0,0)高度1->(0,1)高度3->(1,1)高度4->(2,1)高度3->(2,0)高度5 共需要移动5次

参考题解

最少步数问题，使用bfs算法来寻找从山底到山峰的最短路径。 主要思路是： 读取输入数据并找到山底和山峰的坐标 初始化 BFS 队列，从山底开始搜索 每次从队列中取出当前位置，检查四个方向的可能移动 若移动符合高度差限制且未访问过，则加入队列继续搜索 找到山峰时立即返回步数，若队列为空仍未找到则返回 - 1 时间复杂度：O (m*n)

C++：

// C++17
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
struct Node { int x, y, d; };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int climb;
    cin >> climb;
    int rows, cols;
    cin >> rows >> cols;

    vector<vector<int>> a(rows, vector<int>(cols));
    pii bottom(-1,-1), peak(-1,-1);
    int maxh = INT_MIN;

    for(int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++){
            cin >> a[i][j];
            if(a[i][j] == 0){
                bottom = {i,j};
            }
            if(a[i][j] > maxh){
                maxh = a[i][j];
                peak = {i,j};
            }
        }
    }

    vector<vector<bool>> vis(rows, vector<bool>(cols,false));
    queue<Node> q;
    q.push({bottom.first, bottom.second, 0});
    vis[bottom.first][bottom.second] = true;

    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    while(!q.empty()){
        Node cur = q.front(); q.pop();
        if(cur.x == peak.first && cur.y == peak.second){
            cout << cur.d << "\n";
            return 0;
        }
        int h = a[cur.x][cur.y];
        for(auto &dir : dirs){
            int nx = cur.x + dir[0], ny = cur.y + dir[1];
            if(nx>=0 && nx<rows && ny>=0 && ny<cols && !vis[nx][ny]){
                int nh = a[nx][ny];
                if(nh >= h - climb && nh <= h + climb){
                    vis[nx][ny] = true;
                    q.push({nx, ny, cur.d+1});
                }
            }
        }
    }

    cout << -1 << "\n";
    return 0;
}

Java：

// Java 8+
import java.io.*;
import java.util.*;

public class Main {
    static class Node {
        int x, y, d;
        Node(int x, int y, int d) { this.x = x; this.y = y; this.d = d; }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int climb = Integer.parseInt(br.readLine().trim());
        String[] rc = br.readLine().split("\\s+");
        int rows = Integer.parseInt(rc[0]), cols = Integer.parseInt(rc[1]);

        int[][] a = new int[rows][cols];
        int bx=-1, by=-1, px=-1, py=-1;
        int maxh = Integer.MIN_VALUE;
        for(int i = 0; i < rows; i++){
            String[] parts = br.readLine().split("\\s+");
            for(int j = 0; j < cols; j++){
                a[i][j] = Integer.parseInt(parts[j]);
                if(a[i][j] == 0){
                    bx = i; by = j;
                }
                if(a[i][j] > maxh){
                    maxh = a[i][j];
                    px = i; py = j;
                }
            }
        }

        boolean[][] vis = new boolean[rows][cols];
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(bx, by, 0));
        vis[bx][by] = true;

        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while(!q.isEmpty()){
            Node cur = q.poll();
            if(cur.x == px && cur.y == py){
                System.out.println(cur.d);
                return;
            }
            int h = a[cur.x][cur.y];
            for(int[] dir : dirs){
                int nx = cur.x + dir[0], ny = cur.y + dir[1];
                if(nx>=0 && nx<rows && ny>=0 && ny<cols && !vis[nx][ny]){
                    int nh = a[nx][ny];
                    if(nh >= h - climb && nh <= h + climb){
                        vis[nx][ny] = true;
                        q.offer(new Node(nx, ny, cur.d+1));
                    }
                }
            }
        }

        System.out.println(-1);
    }
}

Python：

from collections import deque

def main():
    climb_ability = int(input())
    rows, cols = map(int, input().split())
    a = []
    bottom = None
    peak = None
    max_height = -1

    for i in range(rows):
        row = list(map(int, input.split()))
        a.append(row)
        for j in range(cols):
            if row[j] == 0:
                bottom = (i, j)
            if row[j] > max_height:
                max_height = row[j]
                peak = (i, j)

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    queue = deque()
    queue.append((bottom[0], bottom[1], 0))
    visited[bottom[0]][bottom[1]] = True

    while queue:
        x, y, steps = queue.popleft()
        if (x, y) == peak:
            print(steps)
            return
        current_height = a[x][y]
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny]:
                next_height = a[nx][ny]
                if current_height - climb_ability <= next_height <= current_height + climb_ability:
                    visited[nx][ny] = True
                    queue.append((nx, ny, steps + 1))

    print(-1)

if __name__ == "__main__":
    main()