华为4.26暑期实习机考

华为4.26机考题目解析

一、批量初始化次数

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

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

模块总数N取值范围 1<=N<=1000.
每一行里面的数字按1个空格分隔。

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

样例1：
输入:
5
3 2 3 4
1 5
1 5
1 5
0
输出: 3

样例2：
输入:
3
1 2
1 3
1 1
输出: -1

思路：拓扑排序

代码：

import java.util.*;
public class Main1 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        ArrayList<Integer>[] G = new ArrayList[N + 1]; // 邻接表,每个模块所连接的后一个模块
        for (int i = 1; i <= N; ++i) {
            G[i] = new ArrayList<>(); // 初始化邻接表
        }
        int[] inDegree = new int[N + 1]; // 每个模块的入度
        for (int i = 1; i <= N; ++i) {
            int num = cin.nextInt();  // 第i个模块依赖的模块个数
            if (num == 0) continue;
            for (int j = 0; j < num; ++j) {
                int t = cin.nextInt();
                G[t].add(i);  // 加入模块t的邻接
                inDegree[i] += 1; // 模块i的入度+1 (总共就加num)
            }
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; ++i) {
            if (inDegree[i] == 0) {
                q.offer(i); // 入度为0的模块先加入队列
            }
        }
        int ans = 0;
        int count = 0;  // 判断是否遍历了所有节点，以此判断是否存在环
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int u = q.poll();
                count++;
                for (int j = 0; j < G[u].size(); ++j) {
                    int v = G[u].get(j);
                    inDegree[v]--;
                    if (inDegree[v] == 0) {
                        q.offer(v);
                    }
                }
            }
            ans++; // 当前批入度为0的节点遍历完成
        }
        if (count == N) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }
    }
}

二、分配资源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
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。

样例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]。

思路：Java过不了

代码：

三、疯长的草

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

输入
第一行输入整数M。(2 <= M <= n)
第二行输入草的种数n。(2 <= n <= 50)
后面连续n行输入草i初始位置[xi, yi]。(1 <= xi,yi <= 10^9)

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

样例1：
输入:
2
2
2 1
6 2
输出:
2

样例2：
输入:
2
3
2 1
6 2
100 100
输出:
2

思路：二分答案。二分天数，如果x天满足要求，x + 1天也满足要求。两个点(x1, y1)、(x2, y2)长的草最短的相遇时间为max(|x1 - x2|, |y1 - y2|) / 2 向上取整。选一个天数，在该天数下，遍历所有点（两两一组）,找到mid天后的相交区域，放入list集合中（放入区域的四个顶点即可），然后遍历list集合中的点，计算在所有的草点中，mid天后能长到这个点的草点数量（一个点(x, y)在a天后能长到点(p, q)的条件是max(|x - p|, |y - q|) <= mid ），如果草点数量大于等于m，说明mid天够用，继续缩小搜索范围。

代码：

/**
 * @author 姚庆澳
 * @create 2023-04-26 18:34
 */
import java.util.*;
public class Main3 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int m = cin.nextInt();
        int n = cin.nextInt();
        int[][] points = new int[n][2];
        for (int i = 0; i < n; ++i) {
            points[i][0] = cin.nextInt();
            points[i][1] = cin.nextInt();
        }
        int ans = -1; // 保存最少天数
        // 二分答案
        int left = 0;  // 天数左边界
        int right = (int)1e9 + 1;  // 天数右边界
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int stat = 0; // 标记是否可以找到一个点符合要求
            ArrayList<int[]> list = new ArrayList<>(); //
            for (int i = 0; i < points.length; ++i) {  // 遍历所有点
                for (int j = 0; j < points.length; ++j) {
                    // point[i]和point[j]两个点长的草在mid天后能不能相遇
                    // 两个点相遇的最短天数为 横坐标之间的距离 和 纵坐标之间的距离的 最大值除2向上取整：max(|x1 - x2|, |y1 - y2|) / 2 向上取整
                    if (Math.max(Math.abs(points[i][0] - points[j][0]), Math.abs(points[i][1] - points[j][1])) > 2 * mid) {
                        continue; // mid天后这两个点长的草不能相遇
                    }
                    int sx1 = points[i][0] - mid, sy1 = points[i][1] - mid, ex1 = points[i][0] + mid, ey1 = points[i][1] + mid;
                    int sx2 = points[j][0] - mid, sy2 = points[j][1] - mid, ex2 = points[j][0] + mid, ey2 = points[j][1] + mid;
                    // 求出两个点mid天后长的草的相交区域
                    int sx = Math.max(sx1, sx2), sy = Math.max(sy1, sy2); // 区域左下点的坐标
                    int ex = Math.min(ex1, ex2), ey = Math.min(ey1, ey2); // 区域右上点的坐标

                    // 存在相交区域，则将相交区域中的所有点加入到list中，实际只用加入四个顶点足以判断区域里的点是否符合题目要求
                    if (sx <= ex && sy <= ey) {
                        list.add(new int[]{sx, sy});
                        list.add(new int[]{sx, ey});
                        list.add(new int[]{ex, sy});
                        list.add(new int[]{ex, ey});
                    }
                }
            }
            // 遍历list
            for (int[] pos : list) {
                int cur = 0; // mid天后 点(pos[0], pos[1])处 草的种数
                // 遍历所有店points
                for (int i = 0; i < points.length; ++i) {
                    // 点(pos[0], pos[1])距离每个草点的距离（max(|x1 - x2|, |y1 - y2|)）是否小于等于mid
                    // 如果小于等于mid，说明mid天后，该草点可以长到 点(pos[0], pos[1])处
                    if (Math.max(Math.abs(pos[0] - points[i][0]), Math.abs(pos[1] - points[i][1])) <= mid) {
                        cur++;
                    }
                }
                if (cur >= m) {
                    stat = 1;
                    break;
                }
            }
            if (stat == 1) {  // 找到了一个点符合要求，缩小区间
                right = mid;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        if (ans == -1) {
            System.out.println(0);
        } else {
            System.out.println(ans);
        }
    }
}