笔试时间：2024年08月21日 秋招

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

第一题

题目：数据重删

数据重删是一种节约存储空间的技术，通常情况下，在数据存储池内是有很多重复的数据块，重删则是将这些重复的数据块找出并处理的技术。简单地说重删，就是将N份重复的数据块仅保留1份，并将N-1份数据的地址指针指向唯一的那一份。我们输入一串存储的数据，用N表示数据个数，用K表示数据块的大小，设计一个方法判断当前数据块是否和前面的数据块有重复，两个数据块内容完全一样则表示重复，如果重复则将这个数据块删除，并且在第一个出现数据块的后面增加重复数据的计数，输出经过重删之后的数据内容。

输入描述

8 输入数据的个数

2 数据块的大小

1 2 3 4 1 2 3 4 依次是数据值注意：

输入的数据值都是正整数

1 <= K <= 10^6

1<= N <= 10^2

输出描述

1 2 2 3 4 2 输出结果为去除重复数据后的结果，输出结果最后没有空格，以数字结尾，输出内容不改变输入数据块的顺序

样例输入一

8 

2 

1 2 3 4 1 2 3 4

样例输出一

1 2 2 3 4 2

解释：总共8个数据，数据块的大小为2，按照窗口2进行切片表示一个数据块，分别得到数据块为 [1, 2]，[3, 4]，[1, 2]，[3, 4]。其中第一个数据块和第三个数据块相同，第二个数据块和第四个数据块相同，可以分别进行重删。重删之后数据块[1,2]的计数变为2，表示有两个相同的数据块[1,2]；同理[3,4]的数据块计数也变为2

样例输入二

8 

3 

3 4 5 3 4 5 5 4

样例输出二

3 4 5 2 5 4 1

解释：总共8个数据，数据块的大小为3，按照窗口3进行切片表示一个数据块，分别得到数据块为 [3, 4, 5]，[3, 4, 5]，[5, 4]，其中 [3, 4, 5] 和 [3, 4, 5] 是重复的窗口，可以进行重删。重删之后数据块[3,4,5]的计数变为2，由于剩余数据块不满足3个连续数据，所以下一个数据块只包含 [5, 4]，[5,4]和前面的数据块不同，所以保留下来，只有一份。

参考题解

哈希，照题目要求去截取字符串，然后用哈希表来统计出现次数。

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

#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <algorithm>

using namespace std;

int main() {
    int N, blk;
    cin >> N >> blk;
    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }

    map<vector<int>, pair<int, int>> res;  // 用于存储数据块及其首次出现的下标和出现次数

    for (int i = 0; i < N; i += blk) {
        vector<int> cur_blk(nums.begin() + i, nums.begin() + min(i + blk, N));
        if (res.find(cur_blk) == res.end()) {
            res[cur_blk] = {i, 1};
        } else {
            res[cur_blk].second += 1;
        }
    }

    vector<pair<vector<int>, pair<int, int>>> sorted_res(res.begin(), res.end());
    sort(sorted_res.begin(), sorted_res.end(), [](const auto &a, const auto &b) {
        return a.second.first < b.second.first;
    });

    vector<int> ans;
    for (const auto &kv : sorted_res) {
        ans.insert(ans.end(), kv.first.begin(), kv.first.end());
        ans.push_back(kv.second.second);
    }

    for (size_t i = 0; i < ans.size(); ++i) {
        cout << ans[i];
        if (i != ans.size() - 1) cout << " ";
    }
    cout << endl;

    return 0;
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int blk = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }

        Map<List<Integer>, int[]> res = new HashMap<>();

        for (int i = 0; i < N; i += blk) {
            List<Integer> curBlk = new ArrayList<>();
            for (int j = i; j < Math.min(i + blk, N); j++) {
                curBlk.add(nums[j]);
            }

            if (!res.containsKey(curBlk)) {
                res.put(curBlk, new int[]{i, 1});
            } else {
                res.get(curBlk)[1] += 1;
            }
        }

        List<Map.Entry<List<Integer>, int[]>> sortedRes = new ArrayList<>(res.entrySet());
        sortedRes.sort(Comparator.comparingInt(a -> a.getValue()[0]));

        List<Integer> ans = new ArrayList<>();
        for (Map.Entry<List<Integer>, int[]> entry : sortedRes) {
            ans.addAll(entry.getKey());
            ans.add(entry.getValue()[1]);
        }

        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i));
            if (i != ans.size() - 1) System.out.print(" ");
        }
        System.out.println();
    }
}

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

N = int(input())
blk = int(input())
nums = [int(c) for c in input().split()]

res = {}

for i in range(0, N, blk):
    cur_blk = nums[i:i + blk]
    tp = tuple(cur_blk)
    if tp not in res:
        res[tp] = [i, 1]  # 下标、出现次数
    else:
        res[tp][1] += 1

sorted_res = sorted(res.items(), key=lambda x: x[1][0])
ans = []
for key, value in sorted_res:
    ans.extend(key)  # 将整个数据块加入结果
    ans.append(value[1])  # 加入计数

print(' '.join(map(str, ans)))

第二题

题目：DevOps任务调度

某Devops系统有一批并发任务需要匹配合适的执行机调度执行，任务和执行机都具有CPU型（用0表示）和IO型（用1表示）的区别，此外还有一种通用型执行机（用2表示），一批任务和执行机的类型分别用数组tasks、machines表示，tasks[i]表示第i个任务，machines[i]表示执行机的类型。每台CPU型、IO型执行机只能执行一个对应类型的任务，而通用型执行机既能执行CPU类型任务也能执行IO类型任务。假设现有的匹配策略如下: 任务需要按照优先级从高到低依次匹配执行机（i=0优先级最高）,因此每一轮选择任务数组头部(i=0)的任务去匹配空置执行机数组头部（i=0）的执行机，若任务与执行机类型匹配，则代表该任务调度成功，把该执行机从空置执行机数组中移除。若任务与执行机的类型不匹配，则将执行机放到执行机数组尾部，循环该过程直到任务全部匹配成功或当前任务无法被所有剩余空置执行机匹配。现规定任意时刻都可以选择使用通用执行机，但一旦选择将某个类型的任务匹配通用型执行机，则所有通用型机器都只能用于执行该类型的任务，为了避免任务排队阻塞，请返回现有匹配策略下剩下的最小空置执行机数量。

输入描述

输入共3行

首行是一个正整数n，表示任务数量以及执行机数量

第2行包含n个整数，以空格分隔，表示为任务数组tasks

第3行包含n个整数，以空格分隔，表示为空置执行机数组machines

数据范围：1<=n<=100, 0<=tasks[i]<=1，0<=machines[i]<=2。

输出描述

一行一个整数，代表当前匹配策略下剩下的最小空置执行机数量。

样例输入一

3 

1 0 1 

1 2 0

样例输出一

0

解释：第一轮 任务数组头部类型1，空置执行机数组头部类型1，匹配成功，任务数组变为[0, 1],空置执行机数组变为[2, 0]

第二轮 任务数组头部类型0，空置执行机数组头部类型2，若不选择类型2的执行机执行类型0的任务，将执行机放回数组尾部，任务数组不变为[0, 1],空置执行机数组变为[0, 2]

第三轮 任务数组头部类型0，空置执行机数组头部类型0，匹配成功，任务数组变为[1],空置执行机数组变为[2]

第四轮 任务数组头部类型1，空置执行机数组头部类型2，任务类型1选择匹配执行机类型2，因此剩下的最小空置执行机数量为0

样例输入二

4 

1 0 1 1 

1 0 2 0 

样例输出二

1

解释：第一轮 任务数组头部类型1，空置执行机数组头部类型1，调度成功，任务数组变为[0,1,1],空置执行机数组变为[0,2,0]

第二轮 任务数组头部类型0，空置执行机数组头部类型0，调度成功，任务数组变为[1,1],空置执行机数组变为[2,0]

第三轮 任务数组头部类型1，空置执行机数组头部类型2，类型1的任务选择匹配类型2的执行机，任务数组变为[1],空置执行机数组变为[0]

第四轮 任务数组头部类型1，空置执行机数组头部类型0，无法匹配，剩下的最小空置执行机数量为1

参考题解

枚举+队列模拟。对于通用性的机器2，无非就两种选择：改成0或者改成1，我们尝试两种方案，取最小值即可。

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

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int solve(deque<int> machines, const vector<int>& tasks) {
    for (int task : tasks) {
        int cnt = 0;
        while (cnt < machines.size() && task != machines.front()) {
            machines.push_back(machines.front());
            machines.pop_front();
            cnt++;