本篇博客旨在記錄自已的筆試刷題的練習，里面注有詳細的代碼注釋以及和個人的思路想法，希望可以給同道之人些許幫助。本人也是小白，水平有限，如果文章中有什么錯誤或遺漏之處，望各位可以在評論區指正出來，各位共勉💪。
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;// 枚舉所有基站 jfor (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 {// 讀取 NN = 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。
輸入
- 第一行為climbAbility的值。
- 第二行為mountainMapRows mountainMapCols。
- 從第三行開始為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 bottomsQueue<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);}
}
有幫助的話，希望可以點贊??+收藏?，謝謝各位大佬~~??????
)
