笔试

第一题

解题思路

拓扑排序，最长路径

第二题

解题思路

类LRU做优化（双向链表+哈希表O1删除），但是被卡读入

题干描述

一个管理ID的资源池、可以从资源池中分配资源ID和释放资源ID须，有动态分配和指定分配，动态分配是从资源池的开始分配，指定分配是指定一个资源ID进行分配，无论哪种分配方式释放资源ID都需要放到资源池的尾部，执行一系列操作后，请问资源池的第一个空ID应该是多少？

能否通过用例：|表示换行； 1 3 | 2 | 1 1| 3 1 输出：2

以下是一个可能的解决方案：

import java.util.*;

public class IdPool {
    private final Deque<Integer> pool;

    public IdPool(int size) {
        pool = new ArrayDeque<>(size);
        for (int i = 1; i <= size; i++) {
            pool.offer(i);
        }
    }

    public int allocate() {
        if (pool.isEmpty()) {
            throw new RuntimeException("资源池已满");
        }
        return pool.poll();
    }

    public void allocate(int id) {
        if (pool.contains(id)) {
            pool.remove(id);
        } else {
            throw new RuntimeException("资源ID已被占用");
        }
    }

    public void release(int id) {
        if (pool.contains(id)) {
            throw new RuntimeException("资源ID已在资源池中");
        }
        pool.offer(id);
    }

    public int getFirstAvailableId() {
        if (pool.isEmpty()) {
            throw new RuntimeException("资源池已满");
        }
        return pool.peek();
    }
}

该类使用一个双端队列来存储资源池中的ID。它提供了两种分配方式：动态分配和指定分配。动态分配是从资源池的开始分配，指定分配是指定一个资源ID进行分配。无论哪种分配方式，释放资源ID都需要放到资源池的尾部。它还提供了一个方法来获取资源池的第一个空ID。

第三题

解题思路

二分答案

题干描述

将N种不同的随机种在一块广漠无边的二维平面上(角坐标系内)，给定二维数组points表示第0天所有草的初始位置，第i项points[I]=[XI,Y]表示第0天草i点[XI,YI].每天，被草覆盖的点会向外蔓延到它上、下、左、右、左上、左下、右上、右下8个邻居点。注意，初始状态下，可能有多种草在同一点上。

现给定一个整数 M，问最少需要多少天，方能找到一点同时至少有 M 种草?

不同的草随机种在一块广阔的二维平面上(直角坐标系内)数组 points 表示第0天所有草的初始位置，第i项points[i]表示第0天i草在点[xi, yi]。每天，被草覆盖的点会向外蔓延到它左、右、左上、左下、右上、右下8个邻居点。注息，初始状态有多种草在同一点上。输入一个整数 M, 问最少需要多少天，方能找到一点同时又m种草。找不到返回0

能否通过用例 2 | 2 | 2 1 | 6 2。输出2

m = int(input())n = int(input())xys = []dirs = [[0, 0], [-1, -1], [-1, 1], [-1, 0], [0, 1], [0, -1], [1, 0], [1, 1], [1, -1]]for i in range(n):    x, y = map(int, input().split())    xys.append([x, y])res = -1r = int(1e9 + 1)l = 0while l < r:    mid = (l + r) // 2    stat = 0    ls = []    for i in range(len(xys)):        for j in range(len(xys)):            if max(abs(xys[j][0] - xys[i][0]), abs(xys[j][1] - xys[i][1])) > 2 * mid:                continue            sx1,sy1,ex1,ey1 = xys[i][0] - mid,xys[i][1] - mid,xys[i][0] + mid,xys[i][1] + mid            sx2,sy2,ex2,ey2 = xys[j][0] - mid,xys[j][1] - mid,xys[j][0] + mid,xys[j][1] + mid            ls.append([max(sx1, sx2), max(sy1, sy2)])            ls.append([max(sx1, sx2), min(ey1, ey2)])            ls.append([max(sy1, sy2), max(sx1, sx2)])            ls.append([max(sy1, sy2), min(ex1, ex2)])    for i in ls:        cur=0        for j in range(len(xys)):            if max(abs(i[0] - xys[j][0]), abs(i[1] - xys[j][1]))<=mid:                cur+=1        if cur>=m:            stat=1            break    if stat:        r=mid        res=mid    else:        l= mid + 1if res == -1:    print(0)else:    print(res)