2个小时，3道编程题

第一题

题目描述

某运营商需要在某一区域铺设光缆，起点为机房，终点为某小区，整个区域以一个m*n的矩阵表示，光缆沿着矩阵的边铺设（不允许走对角线），区域内有些节点可以经过，但有些节点（如图红色x的位置，输入时给定）因为各种因素无法经过，起点的机房与终点的小区可能在区域内的任何位置，计算从机房到目标小区铺设光缆的最短距离（如果光缆无法从起点机房铺设到达目标小区，返回-1） 输入： m 矩阵宽（横轴点数量，例如图示为11，以0~10作为下标） n 矩阵高（纵轴点数量，例如图示为8，以0~7作为下标） 机房坐标（a1, a2） 目标小区坐标（b1, b2） 矩阵内不允许经过的节点数量k 依次为这些不允许经过的节点坐标

1<=m,n<=1000 0<=k<=100000

输出： 从机房道目标小区铺设光缆的最短距离

样例1： 11 8 2 3 7 5 6 2 4 3 5 4 4 5 4 6 4 7 4 输出： 9

对样例1的解释：

11*8的矩阵（横轴坐标0_{10，纵轴坐标0}7） 起始点（机房）为坐标（2 3） 目标点（要连到的小区）为坐标（7 5） 矩阵内不允许经过的节点数为6个 依次给出这些不允许经过的节点坐标

样例2： 输入： 3 3 0 0 2 2 3 0 1 1 1 2 1

输出： -1

解题思路

本题要求在一个 $m \times n$ 的矩阵中，从起点 (a1, a2) 到终点 (b1,b2)，找到一条最短路径，路径只能沿着矩阵的边（上、下、左、右）移动，且不能经过指定的不可经过节点。

由于矩阵的规模较大（$1 \leq m, n \leq 1000，0 \leq k \leq 100000$），需要一个高效的算法。广度优先搜索（BFS）是一种适合在无权图中寻找最短路径的算法，时间复杂度为 $O(m \times n)$，能够在可接受的时间范围内完成搜索。

算法步骤：

1. 读取输入数据：

   • 读取矩阵的宽度 m 和高度 n。
   • 读取起点坐标 (a1,a2) 和终点坐标 (b1,b2)。
   • 读取不可经过节点的数量 kkk 以及它们的坐标。

2. 初始化矩阵：

   • 创建一个大小为 $m \times n$ 的二维数组 grid，默认值为 0。
   • 将不可经过的节点在 grid 中标记为 -1。

3. 检查起点和终点：

   • 如果起点或终点是不可经过的节点，直接输出 -1。

4. 执行广度优先搜索（BFS）：

   • 使用队列存储待访问的节点，初始时将起点加入队列。
   • 将起点在 grid 中的值设为 1，表示已访问，距离为 1。
   • 定义四个方向数组 dx 和 dy，用于移动到相邻节点。
   • 当队列不为空时，重复以下步骤：
     • 从队列中取出当前节点 (x,y)。
     • 如果当前节点是终点，输出距离并结束程序。
     • 遍历四个方向，计算新位置 (nx,ny)。
     • 检查新位置是否在矩阵范围内，且未被访问过（值为 0），并且不是不可经过的节点。
     • 如果满足条件，将新位置加入队列，并将其在 grid 中的值设为 grid[x][y] + 1。

5. 输出结果：

   • 如果在 BFS 过程中找到终点，已在步骤 4 中输出结果。
   • 如果 BFS 结束后仍未找到终点，输出 -1。

代码实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int a1 = scanner.nextInt();
        int a2 = scanner.nextInt();
        int b1 = scanner.nextInt();
        int b2 = scanner.nextInt();
        int k = scanner.nextInt();

        // 初始化grid
        int[][] grid = new int[m][n];

        // 读取不可经过的节点
        for (int i = 0; i < k; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            grid[x][y] = -1;
        }

        // 检查起点和终点是否为不可经过的节点
        if (grid[a1][a2] == -1 || grid[b1][b2] == -1) {
            System.out.println(-1);
            return;
        }

        // BFS
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{a1, a2});
        grid[a1][a2] = 1; // 起点距离设为1

        int[] dx = {-1, 1, 0, 0}; // 四个方向
        int[] dy = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];

            // 如果到达终点，输出距离并结束
            if (x == b1 && y == b2) {
                System.out.println(grid[x][y] - 1);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 检查边界
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    // 如果未访问且不是不可经过的节点
                    if (grid[nx][ny] == 0) {
                        grid[nx][ny] = grid[x][y] + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        // 如果无法到达终点
        System.out.println(-1);
    }
}

过了90%

第二题

题目描述

有一个比较复杂的软件系统需要部署到客户提供的服务器上。该软件系统的安装过程非常繁琐，为了降低操作成本，需要开发一个工具实现自动化部署。 软件的安装过程可以分成若干个小步骤，某些步骤间存在依赖关系，被依赖的步骤必须先执行完，才能执行后续的安装步骤。满足依赖条件的多个步骤可以并行执行。 请你开发一个调度程序，以最短的时间完成软件的部署。

输入： 第一行：总步骤数 N （0<N<=10000) 第二行：N个以空格分隔的整数，代表每个步骤所需的时间。该行所有整数之和不大于int32 第三行开始的N行：表示每个步骤所依赖的其它步骤的编号（编号从1开始，行号减2表示步骤的编号），如果依赖多个步骤，用空格分隔。-1表示无依赖 测试用例确保各个安装步骤不会出现循环依赖。 输出： 1个数字，代表最短执行时间。

样例1： 输入： 4 6 2 1 2 -1 -1 1 3 输出： 9 解释： 一共4个步骤。 每个步骤所需的时间分别为6 2 1 2。 步骤1和步骤2无依赖，可并发执行；步骤3依赖步骤1；步骤4依赖步骤3。 总的最小执行时间为6 + 1 + 2 = 9

样例2： 输入： 4 1 2 3 4 2 3 3 -1 1 输出： 10 解释： 步骤1依赖步骤2和3，步骤2依赖步骤3，步骤3无依赖，步骤4依赖步骤1 执行顺序为 3 --> 2 --> 1 --> 4，最小执行时间为3 + 2 + 1 + 4 = 10

解题思路

本题需要在满足依赖关系的情况下，找到完成所有安装步骤的最短总时间。由于多个步骤在满足依赖条件下可以并行执行，因此需要找到最长的执行路径。

算法步骤：

1. 读取输入并构建图：

   • 读取总步骤数 N。
   • 读取每个步骤的执行时间，存储在数组 duration 中，索引从 1 开始。
   • 初始化邻接表 adjList，用于存储依赖关系。
   • 初始化数组 indegree，用于记录每个步骤的入度（依赖它的步骤数量）。
   • 对于每个步骤，读取其依赖的步骤编号：
     • 如果为 -1，表示无依赖，入度为 0。
     • 否则，遍历依赖列表，构建邻接表，并更新对应步骤的入度。

2. 拓扑排序和最早完成时间计算：

   • 使用队列 queue 进行拓扑排序，将所有入度为 0 的步骤加入队列，并将其最早完成时间设为其自身的执行时间。
   • 当队列不为空时，重复以下步骤：
     • 从队列中取出一个步骤 u。
     • 遍历 u 指向的所有步骤 v（即依赖 u 的步骤）：
       • 将步骤 v 的入度减 1。
       • 更新步骤 v 的最早完成时间为 max(earliestFinish[v], earliestFinish[u] + duration[v])。
       • 如果步骤 v 的入度为 0，将其加入队列。

3. 计算总的最短执行时间：

   • 遍历所有步骤的最早完成时间，取最大值即为完成所有步骤所需的最短总时间。

代码实现

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] duration;
    static int[] indegree;
    static List<Integer>[] adjList;
    static long[] earliestFinish;

    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 StringTokenizer 提高读取效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 读取总步骤数 N
        N = Integer.parseInt(br.readLine());

        duration = new int[N + 1]; // 步骤持续时间，索引从1开始
        indegree = new int[N + 1]; // 每个步骤的入度
        earliestFinish = new long[N + 1]; // 每个步骤的最早完成时间

        // 读取每个步骤的持续时间
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            duration[i] = Integer.parseInt(st.nextToken());
        }

        // 初始化邻接表
        adjList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        // 读取每个步骤的依赖关系
        for (int i = 1; i <= N; i++) {
            String line = br.readLine();
            st = new StringTokenizer(line);
            if (line.equals("-1")) {
                // 无依赖
                continue;
            } else {
                while (st.hasMoreTokens()) {
                    int dep = Integer.parseInt(st.nextToken());
                    adjList[dep].add(i); // 被依赖的步骤指向当前步骤
                    indegree[i]++;
                }
            }
        }

        // 进行拓扑排序并计算最早完成时间
        Queue<Integer> queue = new LinkedList<>();
        // 将所有入度为0的步骤加入队列
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
                earliestFinish[i] = duration[i];
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adjList[u]) {
                indegree[v]--;
                // 更新步骤 v 的最早完成时间
                earliestFinish[v] = Math.max(earliestFinish[v], earliestFinish[u] + duration[v]);
                if (indegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 计算总的最短执行时间
        long result = 0;
        for (int i = 1; i <= N; i++) {
            result = Math.max(result, earliestFinish[i]);
        }

        System.out.println(result);
    }
}

第三题

题目描述

存储软件负责将数据写入硬盘，每次可向单块硬盘写入4KB数据，每写入n次可随机分配一次写入策略，存储软件的写入策略分为3种： 策略1、轮循写入：比如存在3块硬盘0、1、2，当n=2，采用该策略写入数据时，写入顺序为0->1；当n=5，采用该策略写入数据时，写入顺序为0->1->2->0->1。 策略2、优先写入剩余空间高的磁盘(剩余空间相同时，先写入序号小的硬盘)：比如存在3块硬盘0、1、2，空闲容量分别为12KB、16KB、24KB，当n=2，采用该策略写入数据时，写入顺序为2->2；当n=5，采用该策略写入数据时，写入顺序为2->2->1->2->0。 策略3、按比例轮循写入：比如存在3块硬盘0、1、2，写入比例为1:2:3，当n=3，采用该策略写入数据时，数据写入顺序为0->1->1；当n=6，采用该策略写入数据时，数据写入顺序为0->1->1->2->2->2。 切换写入策略时，可切换不同的策略也可以和上次策略保持一致，切换策略后不继承上次写入策略的执行结果，如：3块硬盘0、1、2，写入比例为1:1:2，待写入的数据量有24KB，当n=2，一直通过策略1写入数据，写入顺序为(策略1)0->1->(策略1)0->1>(策略1)0->1；当n=2，一直通过策略3写入数据，写入顺序为(策略3)0->1->(策略3)0->1->(策略3)0->1；当n=5，一直通过策略1写入数据，写入顺序为(策略1)0->1->2->0->1->(策略1)0；当n=5，一直通过策略3写入数据，写入顺序为(策略3)0->1->2->2->0->(策略3)0

现在有一批数据要写入初始状态为空的硬盘，存在几种写入策略分配使最后硬盘空间的占用率(硬盘空间的占用率=硬盘写入的数据量/硬盘的总容量)保持均衡。

备注：如果不存在合适的写入策略分配使最后硬盘空间的占用率保持均衡，则返回0;如果存在合适的写入策略，最终的磁盘空间占用率一定是整除的结果，精度>0.000001。

输入： 磁盘的个数 m, (1<=m<=200) 每个磁盘的容量(单位KB，空间是4的倍数) (1<=每个磁盘容量<=10000]) 磁盘的写入比例, 范围为[1,1000] 待写入的总数据量(单位KB，总数据量是4的倍数), 范围为[1,1000] 每n次切换一次写入策略(1<=n<=1000)

输出： 存在几种写入策略分配

样例1： 输入： 3 128 128 128 1 1 1 24 3 输出： 9 解释： 总共有3块硬盘，每块硬盘有128KB容量，三块硬盘的写入权重比为1:1:1，待写入24KB数据，每3次切换一次写入策略，共存在9种写入策略分配使最后的硬盘空间的占用率保持均衡。 方式1：策略1->策略1 方式2：策略1->策略2 方式3：策略1->策略3 方式4：策略2->策略1 方式5：策略2->策略2 方式6：策略2->策略3 方式7：策略3->策略1 方式8：策略3->策略2 方式9：策略3->策略3 采用9种方式均能保持写入后3块硬盘的空间占用率保持一致，均为8/128=0.0625。

样例2： 输入： 3 128 64 32 1 1 1 4 3 输出： 0 解释： 总共有3块硬盘，每块硬盘分别有128KB、64KB、32KB容量，三块硬盘的写入比例比为1:1:1，待写入4KB数据，每3次切换一次写入策略，不存在写入策略分配使最后硬盘空间的占用率保持均衡，因此返回0。

解题思路

测评题目

https://www.nowcoder.com/discuss/353158733318529024

https://www.cnblogs.com/cgengwei/p/16708445.html

https://blog.csdn.net/weixin_45541762/article/details/130837710

https://blog.csdn.net/weixin_41171614/article/details/136977122

版权所有

版权归属：cloudinwind

本文链接：/review/qwd7vuzf/

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)