华为
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的矩阵（横轴坐标010，纵轴坐标07） 起始点（机房）为坐标（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)\)，能够在可接受的时间范围内完成搜索。
算法步骤：
-
读取输入数据：
- 读取矩阵的宽度 m 和高度 n。
- 读取起点坐标 (a1,a2) 和终点坐标 (b1,b2)。
- 读取不可经过节点的数量 kkk 以及它们的坐标。
-
初始化矩阵：
-
创建一个大小为 \(m \times n\) 的二维数组
grid，默认值为 0。 - 将不可经过的节点在
grid中标记为 -1。 -
检查起点和终点：
-
如果起点或终点是不可经过的节点，直接输出 -1。
-
执行广度优先搜索（BFS）：
-
使用队列存储待访问的节点，初始时将起点加入队列。
- 将起点在
grid中的值设为 1，表示已访问，距离为 1。 - 定义四个方向数组
dx和dy，用于移动到相邻节点。 - 当队列不为空时，重复以下步骤：
- 从队列中取出当前节点 (x,y)。
- 如果当前节点是终点，输出距离并结束程序。
- 遍历四个方向，计算新位置 (nx,ny)。
- 检查新位置是否在矩阵范围内，且未被访问过（值为 0），并且不是不可经过的节点。
- 如果满足条件，将新位置加入队列，并将其在
grid中的值设为grid[x][y] + 1。
-
输出结果：
-
如果在 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
解题思路¶
本题需要在满足依赖关系的情况下，找到完成所有安装步骤的最短总时间。由于多个步骤在满足依赖条件下可以并行执行，因此需要找到最长的执行路径。
算法步骤：
-
读取输入并构建图：
- 读取总步骤数
N。 - 读取每个步骤的执行时间，存储在数组
duration中，索引从 1 开始。 - 初始化邻接表
adjList，用于存储依赖关系。 - 初始化数组
indegree，用于记录每个步骤的入度（依赖它的步骤数量）。 - 对于每个步骤，读取其依赖的步骤编号：
- 如果为
-1，表示无依赖，入度为 0。 - 否则，遍历依赖列表，构建邻接表，并更新对应步骤的入度。
- 如果为
-
拓扑排序和最早完成时间计算：
-
使用队列
queue进行拓扑排序，将所有入度为 0 的步骤加入队列，并将其最早完成时间设为其自身的执行时间。 - 当队列不为空时，重复以下步骤：
- 从队列中取出一个步骤
u。 - 遍历
u指向的所有步骤v（即依赖u的步骤）：- 将步骤
v的入度减 1。 - 更新步骤
v的最早完成时间为max(earliestFinish[v], earliestFinish[u] + duration[v])。 - 如果步骤
v的入度为 0，将其加入队列。
- 将步骤
- 从队列中取出一个步骤
-
计算总的最短执行时间：
-
遍历所有步骤的最早完成时间，取最大值即为完成所有步骤所需的最短总时间。
- 读取总步骤数
代码实现¶
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