華為開發崗暑期實習筆試（2025年4月16日）

刷題小記：

第一題懷疑測試樣例不完整，貪心法不應該能夠解決該題。第二題使用0-1BFS解決單源最短路徑的問題，往往搭配雙端隊列實現。第三題是運用動態規劃解決最大不重疊子區間個數的問題，難點在于滿足3重判斷規則，所需數據結構及相關操作較多。

1.最小測試用例集覆蓋

題目分析：

題目描述：

二維cases表示測試用例的覆蓋情況，cases[i][j]為 1 表示第i個測試用例覆蓋了第j個模塊，為 0 則表示未覆蓋。

求一個最小的測試用例集合，使得該集合能夠覆蓋所有模塊。

返回該最小的集合大小，如果不存在這樣的集合，返回-1。

輸入描述：

第一行給定兩個整數，分別表示用例總數n和代碼模塊總數m

第二行開始的n行，每行有m個整數（0或1），表示覆蓋情況。

n,m均屬于[1,50]區間

輸出描述：

輸出一個整數表示最小用例集合的大小，若不存在則輸出-1

解題思路：

當且僅當存在j，對任意的i，均有cases[i][j] == 0時，不存在最小覆蓋集合，此時返回-1。

第i行表示第i個測試用例對m個模塊的覆蓋情況，

用一個長度為m的數組mo記錄樣例集合對模塊的覆蓋情況，其值為每一列由各樣例的對應列取并得到。

如果采用回溯法（暴力搜索），那么遍歷全部覆蓋集的時間復雜度為O(2^n)，而檢查數組mo的時間復雜度為O(n)，那么總的時間復雜度為O(n * 2^n)，太大！

如果采用貪心法，每次選擇覆蓋模塊最多的測試樣例添入集合，仍然無法保證測試樣例集合最小。（據說真實考試情況下，該貪心法過了？！）

2.小慕的地鐵大挑戰

題目分析：

題目描述：

有N條地鐵線路，每條線路按順序連接若干站點，且一條線路上不存在重復的站點名。

地鐵乘坐規則如下：進入任意一條地鐵線路需支付2元，每換乘一次加收1元。

現求小慕從某個出發站前往指定的目的站，規劃一條最省錢的路線并返回最低票價；若不能抵達，輸出"NA"。

輸入描述：

第一行一個整數N表示地鐵線路數量，介于[1,1000]。

接下來N行，每行描述一條地鐵線路，用空格分隔若干個站點名（站點名長度不超過100個字符），最多包含100個站點。不同線路間站點名可能重復，表示是換乘站。

第N+1行包含兩個站點名，分別是出發站和目的站。

輸入保證：若存在可達路徑，則方案唯一。

輸出描述：

第一行輸出“換乘路徑”（除起始點外，只包含可能存在的換乘站點），站點之間用"-"連接。

第二行輸出該方案的總票價。

若無可達路徑，只輸出一行"NA"

解題思路：

運用0-1廣度優先搜索遍歷所有路徑，找出權值最小的路徑，其中：在線路內部移動的邊權為0，換乘時的邊權為1。

關鍵步驟：

構建狀態圖：key是(站點名,所屬線路編號)，value是(下一站點,權重)的列表，其中用"虛擬線路編號-1"表示換乘口

1. 對于同一條地鐵線路的相鄰站點(A,i)和(B,i)相連，即給(A,i)的value列表添加((B,i),0)，給(B,i)的value列表添加((A,i),0)
2. 對于每個站點，將其與對應的虛擬換乘口相連：

1. 1. 從站點(A,i)到虛擬換乘口(A,-1)的權為1，即給(A,i)的value列表添加((A,-1),1)
  2. 從虛擬換乘口(A,-1)到站點(A,i)的權為0，即給(A,-1)的value列表添加((A,i),0)

路徑搜索算法 0-1BFS：

1. 使用雙端隊列Deque，優先處理權值為0的邊，即將其加入隊頭（優先出隊）；處理權值為1的邊時，將其加入隊尾（后出隊），已訪問過的節點直接跳過
2. 用一個映射d記錄每個節點的最小費用，初始化為INT_MAX
3. 用一個映射pre記錄每個節點的前置節點，以便第一次找到終點后復現路徑（權值為0的節點被優先處理，廣度優先搜索能確保找到目標點時路徑代價最小）

路徑還原與票價計算：

1. 找到終點時，借助pre映射還原路徑，每遇到(node, -1)的節點表示為換乘節點，將其添加入路徑并記錄換乘代價
2. 票價 = 2 + 換乘代價 - 1，因為(起點, -1)被視作了換乘節點加入路徑，而其本身是不需要換乘的，只是為了統一寫法才記為-1，因此票價公式末尾減去1

如果最終最短路徑映射d不包含終點，表示不存在能夠從起點到達該終點的路徑，輸出NA。

3.滿足盡可能多的業務需求的IP區間方案組

題目分析：

題目描述：

業務的網絡地址需求用一個閉區間[startip, endip]表示。

由于要求不同業務的IP地址區間不能重疊，要求按照一定的順序將這些業務需求排序，盡可能滿足更多的業務需求：

當業務數量相同時，以IP地址占用區間最少的優先
當業務數量相同時且IP地址占用區間大小也相同時，按照IP范圍排序，比較起始地址，起始地址最小者優先。

輸入描述：

第一行為業務個數N，有效范圍是[1, 1000]

接下來N行是IP地址區間，每行有startip和endip，均為合法的IPv4地址格式，即(A, B, C, D)，其中ABCD的取值范圍是[0, 255]

注意：IP地址大小的比較，是按照A、B、C和D的順序進行比較。

輸出描述：

輸出排序好的M個IP區間，每行一個。

解題思路：

首先將IP地址轉換成32位的整數進行存儲，便于比較大小。

然后將這些IP區間按照startip進行升序排序，若startip相同，那么按照endip進行升序排序，得到32位轉換以及排序后的N行2列的整型數組ips。

動規五部曲：

確定dp數組以及下標的含義：dp[i]表示以第i個區間結尾的最大不重疊子區間數量
確定遞推公式：對于以j（j < i)為結尾的最大不重疊子區間方案，如果與第i個區間不重疊，那么：

1. 如果dp[j] + 1> dp[i]，那么以第i個區間為結尾的方案為在以第j個區間為結尾的最大不重疊區間數方案的基礎上加上第i個區間；
2. 如果dp[j] + 1 == dp[i]，那么比較以第i個區間為結尾的最優方案，以及以第j個區間為結尾的最優方案的基礎上添加第i個區間，比較這兩個方案的長度，選擇較短者；如果兩個方案的長度相同，比較兩個方案的起始IP地址。

確定遍歷方向：由于dp[i]依賴于dp[j](j < i)，因此正序遍歷即可。
dp數組初始化：遍歷第i個區間時，由于一定以第i個區間結尾，因此初始化dp[i] = 1表示將第i個區間添入業務組合方案。

import java.util.*;public class Ipv4ToIntConverter {public static int ipv4ToInt(String ipAddress) {String[] parts = ipAddress.split("\\.");int result = 0;for (int i = 0; i < 4; i++) {int octet = Integer.parseInt(parts[i]);result = (result << 8) | octet;}return result;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.nextLine(); // 消耗掉換行符int[][] ips = new int[n][2];for (int i = 0; i < n; i++) {String[] line = scanner.nextLine().split(" ");ips[i][0] = ipv4ToInt(line[0]);ips[i][1] = ipv4ToInt(line[1]);}// 按照 startip 升序排序，如果 startip 相同，按照 endip 升序排序Arrays.sort(ips, (a, b) -> {if (a[0] == b[0]) {return Integer.compare(a[1], b[1]);}return Integer.compare(a[0], b[0]);});// dp[i] 表示以第 i 個區間結尾的最大不重疊區間數量int[] dp = new int[n];// 記錄每個狀態下選擇的區間List<List<int[]>> choices = new ArrayList<>();// 記錄每個狀態下選擇的區間的總長度int[] lengths = new int[n];for (int i = 0; i < n; i++) {dp[i] = 1;choices.add(new ArrayList<>());choices.get(i).add(ips[i]);lengths[i] = ips[i][1] - ips[i][0];for (int j = 0; j < i; j++) {if (ips[j][1] < ips[i][0]) {// 第i個區間與第j個區間不重合if (dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;List<int[]> newChoice = new ArrayList<>(choices.get(j));newChoice.add(ips[i]);choices.set(i, newChoice);lengths[i] = lengths[j] + (ips[i][1] - ips[i][0]);} else if (dp[j] + 1 == dp[i]) {int newLength = lengths[j] + (ips[i][1] - ips[i][0]);if (newLength < lengths[i]) {List<int[]> newChoice = new ArrayList<>(choices.get(j));newChoice.add(ips[i]);choices.set(i, newChoice);lengths[i] = newLength;} else if (newLength == lengths[i]) {if (newChoice.get(0)[0] < choices.get(i).get(0)[0]) {List<int[]> newChoice = new ArrayList<>(choices.get(j));newChoice.add(ips[i]);choices.set(i, newChoice);}}}}}}// 找到最大不重疊區間數量的方案int maxCount = 0;List<int[]> bestChoice = new ArrayList<>();int minLength = Integer.MAX_VALUE;int startIp = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {if (dp[i] > maxCount) {maxCount = dp[i];bestChoice = choices.get(i);minLength = lengths[i];startIp = bestChoice.get(0)[0];} else if (dp[i] == maxCount) {if (lengths[i] < minLength) {bestChoice = choices.get(i);minLength = lengths[i];startIp = bestChoice.get(0)[0];} else if (lengths[i] == minLength) {if (choices.get(i).get(0)[0] < startIp) {bestChoice = choices.get(i);startIp = bestChoice.get(0)[0];}}}}// 輸出結果for (int[] ip : bestChoice) {System.out.println(intToIpv4(ip[0]) + " " + intToIpv4(ip[1]));}scanner.close();}public static String intToIpv4(int ip) {StringBuilder sb = new StringBuilder();for (int i = 3; i >= 0; i--) {sb.append((ip >> (i * 8)) & 255);if (i > 0) {sb.append(".");}}return sb.toString();}
}