笔试时间：2024年05月22日

历史笔试传送门：2023秋招笔试合集

第一题

题目：获取公共链表片段

给定两个链表，获取两者中相同节点值的最大连续片段。如果没有公共片段，返回-1。

输入描述

第一行表示链表1，第二行表示链表2，每条链表长度不超过20个元素，链表不会为空。

输出描述

公共链表片段。

样例输入

1 2 2 3 9 1 5

9 2 2 3 6 8

样例输出

2 2 3

参考题解

模拟。找到第一个数组的所有子数组，放入哈希表。遍历第二个数组的所有子数组，判断是否存在于哈希表即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::string nums1, nums2;
    std::cin >> nums1 >> nums2;

    std::unordered_set<std::string> s;
    int n = nums1.size(), m = nums2.size();

    // 找到所有子串并放入集合
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            s.insert(nums1.substr(i, j - i + 1));
        }
    }

    std::string res = "";

    // 检查nums2中的子串是否存在于集合中
    for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j <= m; ++j) {
            std::string sub = nums2.substr(i, j - i + 1);
            if (s.find(sub) != s.end() && (j + 1 - i) > res.size()) {
                res = sub;
            }
        }
    }

    if (!res.empty()) {
        std::cout << res << std::endl;
    } else {
        std::cout << -1 << std::endl;
    }

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String nums1 = scanner.nextLine();
        String nums2 = scanner.nextLine();

        HashSet<String> set = new HashSet<>();
        int n = nums1.length(), m = nums2.length();

        // 找到所有子串并放入集合
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                set.add(nums1.substring(i, j + 1));
            }
        }

        String res = "";

        // 检查nums2中的子串是否存在于集合中
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j <= m; j++) {
                String sub = nums2.substring(i, j + 1);
                if (set.contains(sub) && (j + 1 - i) > res.length()) {
                    res = sub;
                }
            }
        }

        if (!res.isEmpty()) {
            System.out.println(res);
        } else {
            System.out.println(-1);
        }

        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

nums1 = input()
nums2 = input()

# 找到最长公共子数组
s = set()
n,m = len(nums1),len(nums2)

for i in range(n):
    for j in range(i+1,n+1):
        s.add(nums1[i:j+1])

res = ""

for i in range(m):
    for j in range(i+1,m+1):
        if nums2[i:j+1] in s and j+1-i > len(res):
            res = nums2[i:j+1]

if res:
    print(res.strip())
else:
    print(-1)

第二题

题目：矿车运输成本

露天矿采矿作业的特点是规模大，矿石和废料的移动量达到百万吨，运输成本开销较大，需要寻求一种最优的运输路径节省成本。已知矿场可以划分成N*M的网格图，每个网格存在地形的差异，因此通过不同网格时，成本开销存在差异。网格有以下5种类型：

1、标志为'S’的网格为运输起点；

2、标志为'E”的网格时运输终点；

3、标志为'B’的网格为阻塞点，不允许通行；

4、标志为'C'的网格为检查点，矿车在运输路径中，至少需要进入一次检查点。

5、标志为‘数字”的网格，其数字表示经过该网格的成本开销。

运输矿车只能上下左右4个方向运行，不允许斜对角进入其他网格。必要时可重复进入网格。

请根据输入的网格图，寻求一条从S网格到E网格，并且至少经过一次检查点的最低成本运输路径，并输出其成本开销。

输入描述

第一行：网格图的行数N[3,200]和网格图的列数M[3,200]，使用空格隔开。

第二行至第N+1行：网格图每一行的元素，可以为'S’，E’，'B'，‘C'或者数字[0,100]，并且有且仅有一个'S’和一个'E’，同时存在一个或者多个‘C'，并依次使用空格隔开。

输出描述

第一行：输出运输最低成本开销。

如果不存在可达通路，请输出-1

样例输入

3 3

S 4 5

7 B 3

C 9 E

样例输出

16

参考题解

逆向思维+迪杰斯特拉。枚举所有的C点，从C点出发跑一次迪杰斯特拉，找到C->S和C->E的最短距离即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>

using namespace std;

int n, m;
vector<vector<string>> matrix;

vector<vector<int>> solve(int st_i, int st_j) {
    vector<vector<int>> distance(n, vector<int>(m, INT_MAX));
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    distance[st_i][st_j] = 0;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> h;
    h.push(make_tuple(0, st_i, st_j));
    
    while (!h.empty()) {
        int d, i, j;
        tie(d, i, j) = h.top();
        h.pop();
        if (visited[i][j]) continue;
        visited[i][j] = true;

        vector<pair<int, int>> directions = {{i+1, j}, {i, j+1}, {i-1, j}, {i, j-1}};
        for (auto [ni, nj] : directions) {
            if (ni < 0 || nj < 0 || ni >= n || nj >= m || visited[ni][nj] || matrix[ni][nj] == "B") continue;
            int w = 0;
            if (matrix[ni][nj] == "C" || matrix[ni][nj] == "E" || matrix[ni][nj] == "S") {
                w = 0;
            } else {
                w = stoi(matrix[ni][nj]);
            }
            if (distance[ni][nj] > distance[i][j] + w) {
                distance[ni][nj] = distance[i][j] + w;
                h.push(make_tuple(distance[ni][nj], ni, nj));
            }
        }
    }
    return distance;
}

int main() {
    cin >> n >> m;
    matrix.resize(n, vector<string>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }

    vector<pair<int, int>> C;
    int