华为笔试题2023-04-26

笔试时间：2023年4月26日 19:00-21:00

注：因为本次第二题很容易超时（只有使用C++有可能过），导致很多人都没拿到150分，所以华为在2023-05-06举行了第二次笔试。

1、批量初始化次数（100分）

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

解答要求

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

输入

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

输出

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

测试样例

输入 5 3 2 3 4 1 5 1 5 1 5 0

输出 3

输入 3 1 2 1 3 1 1

输出 -1

代码

100%通过

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] inDegree = new int[n+1]; // 入度数组
        List<List<Integer>> graph = new ArrayList<>(); // 图
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 1; i <= n; i++) {
            int num = scanner.nextInt();
            for (int j = 0; j < num; j++) {
                int id = scanner.nextInt();
                graph.get(id).add(i); // 构建有向图，id指向i
                inDegree[i]++; // i的入度加1
            }
        }
        int count = 0; // 批量初始化次数
        Queue<Integer> queue = new LinkedList<>(); // 存放入度为0的结点
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i); // 将入度为0的结点加入队列
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int next : graph.get(cur)) {
                    inDegree[next]--; // 将cur指向的结点入度减1
                    if (inDegree[next] == 0) {
                        queue.offer(next); // 将入度变为0的结点加入队列
                    }
                }
            }
            count++; // 批量初始化次数加1
        }
        for (int i = 1; i <= n; i++) { // 检查是否存在循环依赖
            if (inDegree[i] != 0) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(count);
    }
}

2、分配资源ID（200分）

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

注意: 资源池的初始顺序是从小到大。 资源池中空闲资源ID不足时，动态分配失败，对资源池不进行任何操作。 指定分配资源ID已经被占用或者不在资源池范围内时，对资源池不进行任何操作。 释放资源ID不在资源池范围内时或者已经是空闲资源ID时，对资源池不进行任何操作。 保证每个用例最后都有空闲资源ID。

解答要求

时间限制：C/C++ 100ms，其他语言：200ms 内存限制：C/C++ 32MB，其他语言：64MB

输入

第一行是资源池的范围; 第二行是操作个数。 第三行开始，第一个数字代表操作类型，1表示动态分配，2表示指定分配，3表示释放； 如果第一个数字是1，第二个表示分配的个数； 如果第一个数字是2，第二个表示分配的资源ID； 如果第一个数字是3，第二个表示释放的资源ID。

输出

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

测试样例

输入 1 3 2 1 1 3 1 输出 2

输入 1 3 3 2 2 3 2 1 1 输出 3

代码

测试用例通过，提交通过4%，提示超时。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int rangeFrom = scanner.nextInt(), rangeTo = scanner.nextInt();
        LinkedList<Integer> resources = new LinkedList<>();
        for (int i = rangeFrom; i <= rangeTo; i++) {
            resources.addLast(i);
        }
        int n = scanner.nextInt();
        int resID, count;
        for (int i = 0; i < n; i++) {
            switch (scanner.nextInt()) {
                case 1:
                    count = scanner.nextInt();
                    if (resources.size() < count) {
                        continue;
                    }
                    resources.subList(0, count).clear();
                    break;
                case 2:
                    resID = scanner.nextInt();
                    resources.remove(Integer.valueOf(resID));
                    break;
                case 3:
                    resID = scanner.nextInt();
                    if (resID >= rangeFrom && resID <= rangeTo && !resources.contains(resID))
                        resources.addLast(resID);
                    break;
            }
        }
        System.out.println(resources.getFirst());
    }
}