前言

算是最近华子笔试难度比较低的一场啦，没有那种很恶心的大模拟了。

第一题是个简单的数据结构模拟题。

第二题是字符串处理，题意不是很清楚，笔试的时候多试试应该能试对。

第三题，一个基础的DP问题。

另：虽然目前已经到秋招尾声了，但陆续还是有一些笔试，在此欢迎大家投稿。投稿可加最下方二维码微信，备注投稿。

1.通道资源分配

现有一个硬件加速器资源，可以通过100000个通道对其下发任务。要求设计一种通道资源管理方案，满足：

某个用户需输入-1时。此时资源管理方案分配未使用的最小通道号给用户 当某个用户输入有效的通道号时，此时资源管理方案回收对应通道，允许之后重新分配。

计算经过一段时间后，下次用户申请时，所申请到的通道号，如无未使用的通道，输出-1。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000m内存限制: C/C++ 256MB,其他语言: 512MB

输入

输入以数组的方式传入历史申请释放情况，分为两行

第一行为数组大小，用例保证输入的数组大小为有效输入次数，小于等于500000次

第二行为数组元素，每个元素以“空格”区分每次申请释放操作，用例保证输入的通道号均为有效通道号[0,99999]。

输出

下一次申请操作将会申请到的通道号

样例1

输入

8
-1 -1 -1 2 -1 0 -1 -1

输出

4

思路与代码

用队列模拟通道，遇到-1的时候左边弹出。

否则，插入到对应的位置，这个过程可以使用二分来做。

import bisect
from collections import deque

n = int(input())
ops = [int(c) for c in input().split()]

q = deque([i for i in range(100000)])

for op in ops:
    if op == -1:
        q.popleft()
    else:
        # 插入op
        bisect.insort(q, op)

if q: print(q[0])
else:
    print(-1)

查找匹配路径

某通信设备经过长时间运行产生了大量文件目录与文件名称不同的日志文件，维护人员使用设备命令生成了一种特定格式的文件路径列表。

请编写程序帮助维护人员根据匹配规则从该文件路径列表中快速查找符合要求的日志文件或目录路径。

解答要求

时间限制: C/C++ 200ms, 其他语言: 400ms 内存限制: C/C++ 32MB,其他语言: 64MB

输入

输入数据第一行为文件匹配规则字符串，包含大小写英文字符、“/“、"*”，其中“/“为文件路径中的目录分割符，"*“标识匹配任意名称的文件名或者目录名，1<=长度<=2048;

输入数据从第二行开始为文件列表，包含大小写英文字符、空格， 英文字符表示文件名或目录名，英文字符串前的四个空格缩进标识文件目录结构，1<=每行长度<=1024，总计不超过30000行;

输出

输出格式: 符合匹配规则的文件完整路径，文件路径中使用”/“分割目录。

如果存在多个结果，请使用多行输出，输出的顺序与输入的顺序相同。

如果不存在匹配的结果，则输出: NOT FOUND

样例1

输入

/path1/file1
file0
path1
  file1

输出

 /path1/file1

解释

输入的第一行为文件匹配规则，匹配完整路径为“/path1/file1”的文件。
输入的第二行及后续行为文件列表，其中每行开头的四个空格为目录缩进
转换成完整的文件路径列表如下所示
/fileo
/path1
/path1/file1
根据题意，输出匹配结果为”/path1/file1”

思路与代码

字符串处理。

1. 用数组存储原始路径，按照"/"分割。
2. 使用"tab"来区分当前路径是属于哪一层。

个人觉得，题目有个点说不清楚，就是NOT FOUND应该什么时候输出没有讲清楚，按照样例来看，file0应该是属于不存在的路径，但是题目直接忽视.......

source = input()

file_list = []
while True:
    try:
        file_list.append(input())
    except :
        break

sources = source[1:].split("/")

tab = "    "

pre = -1
current_path = []
for file in file_list:
    cnt = file.count(tab)
    if cnt <= pre and current_path:
        # 打印路径
        print("/" + '/'.join(current_path))
        current_path = current_path[:cnt]
        current_path.append(file.strip())
    else:
        if cnt < len(sources) and (sources[cnt] == file.strip() or sources[cnt] == '*'):
            # 直接符合
            current_path.append(file.strip())


    pre = cnt

print("/"+'/'.join(current_path))

3.二叉查找树的个数

二叉查找树，是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉查找树。

给定一个数n，表示值由1到n的节点构造成二叉查找树，问对应能构造的高度小于等于k的不同二叉查找树的个数，根节点的高度为1。0< n < 36，0< k< 36.

解答要求

时间限制: C/C++ 1000ms, 其他语言: 2000ms 内存限制: C/C++ 256MB,其他语言: 512MB

输入

树的节点个数n，树的高度k，用空格分割。

输出

不同二又查找树的个数。

样例1

输入

3 2

输出

1

思路与代码

动态规划，这里使用记忆化搜索实现。

f[l, r, k]：针对区间[l,r]，划分成深度不大于k的BST的数量。

状态转移：枚举当前子树的根节点 root，划分成两个区间[left, root-1]和[root+1,right]，此时的方案数是左右两边方案数的乘积。

也就是 f[l, r, k] += f[l,root-1,k-1] * f[root+1, r, k-1]

from functools import cache

n,k = map(int, input().split())

@cache
def dfs(l:int, r:int, lvl:int) -> int:
    if l > r: return 1
    if lvl == 1:
        if l == r: return 1
        return 0
    if l == r: return 1

    ans = 0
    for root in range(l, r+1):
        ans += dfs(l,root-1,lvl-1) * dfs(root+1, r, lvl-1)
    return ans

print(dfs(1,n,k))