华为校招2023年4月26日考的三道题（截图转文字，练习用）

第一题：批量初始化次数

某部门在开发一个代码分析工具，需要分析模块之间的依赖关系，用来确定模块的初始化顺序，是否有循环依期等问题。

“批量初始化” 是指一次可以初始化一个或多个模块。

例如 模块 1 依赖模块 2， 模块 3 也依赖模块 2， 但模块 1 和 3 没有依赖关系， 则必须先 “批量初始化” 模块 2，再 “批量初始化” 模块 1 和 3。

现给定一组模块间的依赖关系，请计算需要 “批量初始化” 的次数。

输入

1. 第 1 行只有一个数字.表示模块总数 $NN$。
2. 随后的 $NN$ 行依次表示模块 1 到 $NN$ 的依赖数据。每行的第 1 个数表示依赖的模块数量(不会超过 $NN$)，之后的数字表示当前模块依赖的 ID 序列。该序列不会重复出现相同的数字，模块 ID 的取值定在 [1,N] 之内。
3. 模块总数 $NN$ 取值范围 1<=N<=1000
4. 每一行里面的数字按 1 个空格分隔。

输出

输出 “批量初始化次数”
若有循环依赖无法完成初始化，则输出 -1。

示例一

输入

5
3 2 3 4
1 5
1 5
0

输出

3

说明

• 共 5 个模块。
• 模块 1 依赖模块 2、3、4；
• 模块 2 依赖模块 5
• 模块 3 依赖模块 5
• 模块 4 依赖模块 5
• 模块 5 没有依赖任何模块
• 批量初始化顺序为 {5}->{2,3,4}->{1},共需 “批量初始化” 3 次

示例二

输入

3
1 2
1 3
1 1

输出

-1

说明

存在循环依赖，无法完成初始化，返回-1

第二题：分配资源 ID

给定一个管理 ID 的资源池，可以从资源池中分配资源 ID 和释放资源 ID。 分配方式有动态分配和指定分配，动态分配是从资源池的开始分配一个资源 ID，指定分配是指定一个资源 ID 进行分配，无论哪种分配方式释放资源 ID 时都需要放到资源池的尾部。

执行一系列操作后，请问资源池的第一个空闲资源 ID 应该是多少?

注意:

• 资源池的初始顺序是从小到大。

• 资源池中空闲资源 ID 不足时，动态分配失败，对资源池不进行任何操作。

• 指定分配资源 ID 已经被占用或者不在资源池范围内时，对资源池不进行任何操作。

• 释放资源 ID 不在资源池范围内时或者已经是空闲资源 ID 时，对资源池不进行任何操作。

• 保证每个用例最后都有空闲资源 ID。

输入

• 第一行是资源池的范围；

• 第二行是操作个数；

• 第三行开始，第一个数字代表操作类型，1 表示动态分配，2 表示指定分配，3 表示释放；

• 如果第一个数字是 1，第二个表示分配的个数;

• 如果第一个数字是 2，第二个表示分配的资源 ID;

• 如果第一个数字是 3，第二个表示释放的资源 ID。

输出

资源池的第一个空闲资源 ID

示例一

输入

1 3
2
2 2
3 1

输出

2

说明

• 第一行资源池范围是 [1,3]，资源池的初始顺序是 1->2->3。
• 第二行操作个数有 2 个。
• 第三行动态分配 1 个资源 ID，资源池中剩余的资源 ID 顺序是 2->3。
• 第四行释放 1 个资源 ID，资源 ID 是 1，资源池中剩余的资源 ID 顺序是 2->3->1。
• 执行以上操作后，资源池的第一个空闲资源 ID 是 2。

示例二

输入

1 3
3
2 2
3 2
1 1

输出

3

说明

• 第一行资源池范围是 [1,3]，资源池的初始顺序是 1->2->3。
• 第二行操作人数有 3 个。
• 第三行指定分配 1 个资源 ID，资源 ID 是 2，资源池中剩余的资源 ID 顺序是 1->3->2。
• 第四行释放 1 个资源 D，资源 ID 是 2，资源池中剩余的资源 ID 顺序是 1->3->2。
• 第五行动态分配 1 个资源 ID，分配的资源 ID 是 1，资源池中剩余的资源 ID 顺序是 3->2。
• 执行以上操作后，资源池的第一个空闲资源 ID 是 3。

提示

• 保证输入的操作都是合法的。

• 操作类型范围是 [1,3]。

• 分配次数范围是 [1,100000]。

• 资源池范围的最小值是 1，最大值取值范围是 [1,100000]。

• 如果操作类型是 1，分配资源个数的取值范围是 [1,200]。

第三题：疯长的草

将 N 种不同的随机种在一块广漠无边的二维平面上(角坐标系内)，给定二维数组 points 表示第 0 天所有草的初始位置，第 i 项 $points[i]=[Xi,Yi]points[i]=[Xi,Yi]$表示第0天草 $ii$ 点$[X_i,Y_i][X\_i,Y\_i]$。

每天，被草覆盖的点会向外蔓延到它上、下、左、右、左上、左下、右上、右下 8 个邻居点。

注意，初始状态下，可能有多种草在同一点上。

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

输入

• 第一行输入整数 M。()

• 第二行输入草的种数 N。()

• 后面连续 N 行输入草 i 初始位置 $[x_i,y_i][x\_i,y\_i]$。()

输出

返回找到一点至少生长 M 种草的最少天数，找不到返回 0

示例一

输入

2
2
2 1
6 2

输出

2

示例二

输入

2
3
2 1
6 2
100 100

输出

2