【华为】笔试真题训练_20250611

本篇博客旨在记录自已的笔试刷题的练习，里面注有详细的代码注释以及和个人的思路想法，希望可以给同道之人些许帮助。本人也是小白，水平有限，如果文章中有什么错误或遗漏之处，望各位可以在评论区指正出来，各位共勉💪。

1. 找到通信质量最高的基站

考点：

• 滑动窗口：维护一个动态窗口内的最优解。
• 单调队列：高效获取窗口内的最小值（或最优解）。

描述

雨市区中有一条马路，马路从0号路口开始，到N-1号路口结束，在每个路口都架设了最新技术的通信基站，每个基站的信号可以覆盖前后各k个路口的范围，即第i个路口上的基站，可以覆盖[i-k, i+k]这两个路口之间的马路，因此用户的手机处于多个基站的覆盖范围中。每个基站会统计当前接入人数，为保障最佳通信质量，用户手机应选择连接人数最少的基站进行通讯。 这条马路一共N个路口，小明从0号路口出发向前走，求小明在每个路段中的最佳通讯基站。不考虑处于路口中间的特殊场景，只考虑在每个路段中的场景，例如第1个路段为0号路口到1号路口之间的路段，如果基站覆盖范围k=2，此时最佳基站应为0、1、2中连接人数最少的基站。

输入

输入为两行 第一行长度为N的整数数组crossroads[]，数组元素以空格分隔，其中crossroads[i]表示i号路口基站的当前接入人数。1 <= crossroads.length数组长度 <= 10^5，0 <= crossroads[i] <= 10^2 第二行为基站覆盖范围k，1 <= k <= crossroads.length 非法输入返回-1。

输出

返回一个数组ret，ret[i]表示i路段上最佳基站的编号，数组元素之间以空格分隔。例如0号路口到1号路口的路段，为0号路段，其最佳基站用ret[0]表示。

用例输入

3 5 8 7 6 7 4

2

用例输出

0 0 1 4 6 6

Code

/**
 * 【华为】20250528_1_最佳基站
 * @author QIA
 * @create 2025-07-19-15:52
*/

import java.util.*;

public class Main01 {
    public static List<Integer> bestStations(int[] crossroads, int k) {
        if (crossroads == null || crossroads.length < 1 || k < 1 || k > crossroads.length) {
            return Arrays.asList(-1);
        }

        int n = crossroads.length;
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            int minCount = Integer.MAX_VALUE;
            int bestIndex = -1;

            // 枚举所有基站 j
            for (int j = 0; j < n; j++) {
                int left = j - k;
                int right = j + k;

                // 基站 j 能否覆盖路段 [i, i+1]
                if (left <= i && right >= i + 1) {
                    if (crossroads[j] < minCount || (crossroads[j] == minCount && j < bestIndex)) {
                        minCount = crossroads[j];
                        bestIndex = j;
                    }
                }
            }

            result.add(bestIndex);
        }

        return result;
    }

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

        // 读取第一行
        String[] line1 = sc.nextLine().trim().split(" ");
        int[] crossroads = new int[line1.length];
        try {
            for (int i = 0; i < line1.length; i++) {
                crossroads[i] = Integer.parseInt(line1[i]);
            }
        } catch (Exception e) {
            System.out.println(-1);
            return;
        }

        // 读取第二行
        int k;
        try {
            k = Integer.parseInt(sc.nextLine().trim());
        } catch (Exception e) {
            System.out.println(-1);
            return;
        }

        // 处理并输出结果
        List<Integer> res = bestStations(crossroads, k);
        if (res.size() == 1 && res.get(0) == -1) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < res.size(); i++) {
                System.out.print(res.get(i));
                if (i != res.size() - 1)
                    System.out.print(" ");
            }
        }
    }
}

2. 游园线路

考点：

• 最短路径算法：Dijkstra算法或BFS（因为边权非负）。
• 路径输出：需要记录路径而非仅距离。

描述

某公园每年都会在新年时举办灯会，由于公园面积很大且各景点分散，希望你设计一条游园线路，从某个指定入口景点开始，到某个指定出口景点结束，使得游园总路程最短。最短路线不需要走完所有的景点，且中间允许经过其他出入口景点而不离开公园。

输入

第一行：N，景点个数，景点序号从0开始，N - 1结束。2 <= N <= 15
第二行至第N + 1行：是一个N*N的矩阵，表示各相邻景点之间的距离，距离为0表示不相邻。
第N + 2行：该景点是否是公园出入口（1是，0否）。
第N + 3行：要计算最短线路的入口景点序号和出口景点序号
所有用例的输入确保一定存在符合条件的线路，你无需考虑无解的情况。

输出

具体游园线路，如果有多条符合条件的线路，按景点序号从小到大进行排序。

用例输入

5
0 1 2 0 0
1 0 0 3 0
2 0 0 0 10
0 3 0 0 1
0 0 10 1 0
1 0 1 0 1
0 4

用例输出

0 1 3 4

Code

/**
 * 【华为】20250528_2_游园线路
 * @author QIA
 * @create 2025-07-19-15:55
 */
import java.util.*;

public class Main02 {
    static int N;
    static int[][] graph;
    static int[] entrances;
    static int[] dist;
    static List<Integer>[] prev;
    static List<Integer> bestPath = null;
    static List<Integer> path = new ArrayList<>();

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

        try {
            // 读取 N
            N = Integer.parseInt(sc.nextLine().trim());
            if (N < 2 || N > 15) {
                System.out.println("非法景点数量");
                return;
            }

            // 读取邻接矩阵
            graph = new int[N][N];
            for (int i = 0; i < N; i++) {
                String[] row = sc.nextLine().trim().split("\\s+");
                if (row.length != N) {
                    System.out.println("邻接矩阵行数错误");
                    return;
                }
                for (int j = 0; j < N; j++) {
                    graph[i][j] = Integer.parseInt(row[j]);
                }
            }

            // 读取出入口信息
            entrances = new int[N];
            String[] entryLine = sc.nextLine().trim().split("\\s+");
            if (entryLine.length != N) {
                System.out.println("入口数组长度错误");
                return;
            }
            for (int i = 0; i < N; i++) {
                entrances[i] = Integer.parseInt(entryLine[i]);
            }

            // 读取起止点
            String[] startEnd = sc.nextLine().trim().split("\\s+");
            if (startEnd.length != 2) {
                System.out.println("起止点输入格式错误");
                return;
            }
            int start = Integer.parseInt(startEnd[0]);
            int end = Integer.parseInt(startEnd[1]);

            // 求最短路径
            dijkstra(start);
            dfs(end, start);

            // 输出最短路径
            for (int i = 0; i < bestPath.size(); i++) {
                System.out.print(bestPath.get(i));
                if (i != bestPath.size() - 1) System.out.print(" ");
            }
        } catch (Exception e) {
            System.out.println("输入格式错误: " + e.getMessage());
        }
    }

    // Dijkstra + prev 路径追踪
    public static void dijkstra(int start) {
        dist = new int[N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        prev = new ArrayList[N];
        for (int i = 0; i < N; i++) prev[i] = new ArrayList<>();

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0], d = cur[1];
            if (d > dist[u]) continue;

            for (int v = 0; v < N; v++) {
                if (graph[u][v] > 0) {
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        prev[v].clear();
                        prev[v].add(u);
                        pq.offer(new int[]{v, newDist});
                    } else if (newDist == dist[v]) {
                        prev[v].add(u);
                    }
                }
            }
        }
    }

    // 回溯寻找字典序最小路径（关键修复：排序 prev[node]）
    public static void dfs(int node, int start) {
        path.add(node);
        if (node == start) {
            List<Integer> temp = new ArrayList<>(path);
            Collections.reverse(temp);
            if (bestPath == null || comparePath(temp, bestPath) < 0) {
                bestPath = temp;
            }
        } else {
            List<Integer> sortedPrev = new ArrayList<>(prev[node]);
            Collections.sort(sortedPrev); // ✅ 关键排序，保证字典序最小
            for (int pre : sortedPrev) {
                dfs(pre, start);
            }
        }
        path.remove(path.size() - 1);
    }

    // 比较两个路径字典序
    public static int comparePath(List<Integer> a, List<Integer> b) {
        int len = Math.min(a.size(), b.size());
        for (int i = 0; i < len; i++) {
            if (!a.get(i).equals(b.get(i))) {
                return Integer.compare(a.get(i), b.get(i));
            }
        }
        return Integer.compare(a.size(), b.size());
    }
}

3. 爬山路线规划

考点：

• BFS（广度优先搜索）：最少步数问题。

描述

给定一个二维数组 mountainMap 表示一座山的地图，数组中的每个元素 mountainMap[x][y] 代表坐标 (x, y) 处山的高度。登山员从山底出发，爬到山峰。
山底的含义：mountainMap中高度为0的坐标点。
山峰的含义：mountainMap中高度最高的坐标点。
登山员每次移动只能从当前位置向上下左右四个方向移动一格，向高处移动时，移动到的位置山的高度不能高于当前位置的高度加上固定的攀登能力值climbAbility；向低处移动时，移动到的位置的山的高度不能低于当前位置山的高度减去climbAbility。

输入

1. 第一行为climbAbility的值。
2. 第二行为mountainMapRows mountainMapCols。
3. 从第三行开始为mountainMapRows行mountainMapCols列的高度二维数组mountainMap[mountainMapRows][mountainMapCols]，每行的高度数字中间用空格分割。

输出

从山底移动到山峰，最少移动次数。
如果无法移动至山峰，则输出-1

用例输入

1
4 5
1 1 1 1 1
1 0 1 2 1
1 1 1 3 1
1 1 1 1 1

用例输出

3

Code

/**
 * 【华为】20250528_3_爬山路线规划
 * @author QIA
 * @create 2025-07-19-16:01
 */
import java.util.*;

public class Main03 {
    static int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int climbAbility = Integer.parseInt(sc.nextLine().trim());
        String[] dims = sc.nextLine().trim().split("\\s+");
        int rows = Integer.parseInt(dims[0]);
        int cols = Integer.parseInt(dims[1]);

        int[][] map = new int[rows][cols];
        int maxHeight = Integer.MIN_VALUE;

        List<int[]> bottoms = new ArrayList<>();  // 高度为0的山底
        List<int[]> peaks = new ArrayList<>();    // 高度最高的山峰

        // 读取地图并找山底和山峰
        for (int i = 0; i < rows; i++) {
            String[] line = sc.nextLine().trim().split("\\s+");
            for (int j = 0; j < cols; j++) {
                map[i][j] = Integer.parseInt(line[j]);
                if (map[i][j] == 0) {
                    bottoms.add(new int[]{i, j});
                }
                if (map[i][j] > maxHeight) {
                    maxHeight = map[i][j];
                    peaks.clear();
                    peaks.add(new int[]{i, j});
                } else if (map[i][j] == maxHeight) {
                    peaks.add(new int[]{i, j});
                }
            }
        }

        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, -1);

        // BFS from all bottoms
        Queue<int[]> queue = new LinkedList<>();
        for (int[] b : bottoms) {
            queue.offer(b);
            dist[b[0]][b[1]] = 0;
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                    int heightDiff = Math.abs(map[nx][ny] - map[x][y]);
                    if (heightDiff <= climbAbility && dist[nx][ny] == -1) {
                        dist[nx][ny] = dist[x][y] + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        // 找到最短步数到达山峰
        int minSteps = Integer.MAX_VALUE;
        for (int[] peak : peaks) {
            int d = dist[peak[0]][peak[1]];
            if (d != -1) minSteps = Math.min(minSteps, d);
        }

        System.out.println(minSteps == Integer.MAX_VALUE ? -1 : minSteps);
    }
}

有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~✨️✨️✨️