华为嵌入式软件开发工程师笔试4-26

公号：嵌入式未来

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《嵌入式软件笔试-2023年真题汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

1、批量初始化次数

某部门在开发一个代码分析工具，需要分析代码模块之间的依赖关系，用来确定模块的初始化顺序、是否有循环依赖等问题。“批量初始化”是指一次可以初始化一个或多个模块。例如模块1依赖模块2，模块3也依模块2，但模块1和3没有依赖关系。则必须先“批量初始化”模块2，再“批量初始化”模块1和3。现给定一组模块间的依赖关系，请计算需要“批量初始化”的次数。

输入

(1)第1行只有一个数字表示模块总数N

(2)随后的N行依次表示模块1到N的依赖数据。每行的第1个数据表示依赖的模块数量(不会超过N)，之后的数字表示当前模块依赖的模块ID序列,该序列不会重复出现相同的数字,模块ID的取值一定在[1,N]之内。

(3)模块总数N取值范围1<=N<=1000

(4)每一行里面的数字按1个空格分隔

输出

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

样例1

输入：

5

3 2 3 4

1 5

1 5

1 5

0

输出：

3

解释:共5个模块。模块1依赖模块2、3、4;模块2依赖模块5;模块3依赖模块5:模块4依赖模块5;模块5没有依赖任何模块.

批量初始化顺序为{5}->{2,3,4}->{1}，共需“批量初始化”3次.

#include <iostream>
#include <vector>
#include <queue>

int main() {
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> graph(n + 1);
    std::vector<int> indegree(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        int dep_count;
        std::cin >> dep_count;
        while (dep_count--) {
            int dep;
            std::cin >> dep;
            graph[dep].push_back(i);
            ++indegree[i];
        }
    }

    std::queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int batch_init_count = 0;
    while (!q.empty()) {
        ++batch_init_count;
        int level_size = q.size();
        while (level_size--) {
            int cur = q.front();
            q.pop();
            for (int next : graph[cur]) {
                --indegree[next];
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (indegree[i] != 0) {
            std::cout << -1 << std::endl;
            return 0;
        }
    }

    std::cout << batch_init_count << std::endl;
    return 0;
}

2、分配资源ID

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

注意:

资源池的初始顺序是从小到大。资源池中空闲资源ID不足时，动态分配失败，对资源池不进行任何操作指定分配资源ID已经被占用或者不在资源池范围内时，对资源池不进行任何操作。

释放资源ID不在资源池范围内时或者已经是空闲资源ID时，对资源池不进行任何操作。保证每个用例最后都有空闲资源ID。

输入

第一行是资源池的范围;

第二行是操作个数。

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

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

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

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

输出

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

样例1

输入:

1 3

2

1 1

3 1

输出:

2

解释:第一行资源池范围是[1,3],资源池的初始顺序是1->2->3。

第二行操作个数有2个。

第三行动态分配1个资源ID,资源池中剩余的资源ID顺序是2->3。

第四行释放1个资源ID，资源ID是1,资源池中剩余的资源ID顺序是2->3->1。

执行以上操作后,资源池的第一个空闲资源ID是2。

样例2

输入:

1 3

3

2 2

3 2

1 1

输出:

3

解释:第一行资原池范围是[1,3]，资源池的初始顺序是1->2->3。

第二行操作个数有3个。

第三行指定分配1个资源ID，资源ID是2，资源池中剩余的资源ID顺序是1->3.

1IDID2ID1->3->2.