2025 B卷 100分 題型

本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式；

并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析；

本文收錄于專欄：《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》

華為OD機試真題《最小循環子數組》：

---

文章快捷目錄

題目描述及說明

Java

python

JavaScript

C++

C

GO

---

題目名稱：最小循環子數組

---

知識點：字符串匹配、KMP算法（或枚舉驗證）
時間限制：1秒
空間限制：256MB
限定語言：不限

---

題目描述

給定一個由若干整數組成的數組 nums，請檢查數組是否是由某個子數組重復循環拼接而成，并輸出這個最小的子數組。

輸入描述：

• 第一行輸入數組中元素個數 n，1 ≤ n ≤ 100000。
• 第二行輸入數組的數字序列 nums，以空格分割，0 ≤ nums[i] ≤ 10。

輸出描述：
輸出最小的子數組的數字序列，以空格分割。

備注：
數組本身是其最大的子數組，循環1次可生成自身。

示例：
輸入：

9  
1 2 1 1 2 1 1 2 1  

輸出：

1 2 1  

說明：數組 [1,2,1,1,2,1,1,2,1] 可由子數組 [1,2,1] 重復循環3次拼接而成。

---

Java

問題分析

我們需要找到一個數組的最小循環子數組，即該數組可以由該子數組重復拼接而成。解決此問題的關鍵在于確定數組是否由某個子數組重復構成，并找出最小的這樣的子數組。

---

解題思路

1. 候選子數組長度的確定：循環子數組的長度必須是原數組長度的因數。
2. 因數枚舉：找出原數組長度的所有因數，并按從小到大順序檢查。
3. 循環驗證：對于每個候選長度，驗證數組是否可以由該長度的子數組重復構成。
4. 輸出結果：找到第一個滿足條件的最小子數組。

---

代碼實現

import java.util.Scanner;
import java.util.TreeSet;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 讀取數組長度int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt(); // 讀取數組元素}// 生成所有可能的因數（包括n）TreeSet<Integer> factors = new TreeSet<>();for (int i = 1; i * i <= n; i++) {if (n % i == 0) {factors.add(i);factors.add(n / i);}}// 遍歷所有因數，從小到大檢查for (int d : factors) {if (check(nums, d)) { // 驗證當前因數對應的子數組是否符合循環條件printResult(nums, d); // 打印結果return;}}printResult(nums, n); // 最終必能匹配自身（d=n）}private static boolean check(int[] nums, int d) {for (int i = 0; i < nums.length; i++) {if (nums[i] != nums[i % d]) { // 核心驗證邏輯：每個位置必須與子數組對應位置相同return false;}}return true;}private static void printResult(int[] nums, int d) {StringBuilder sb = new StringBuilder();for (int i = 0; i < d; i++) {sb.append(nums[i]);if (i != d - 1) {sb.append(" ");}}System.out.println(sb);}
}

---

代碼解析

1. 輸入處理

   int n = scanner.nextInt();
   int[] nums = new int[n];
   for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();
   }
   

   • 讀取數組長度和元素。

2. 因數生成

   TreeSet<Integer> factors = new TreeSet<>();
   for (int i = 1; i * i <= n; i++) {if (n % i == 0) {factors.add(i);factors.add(n / i);}
   }
   

   • 遍歷1到sqrt(n)，收集所有因數并存入有序集合，自動去重并排序。

3. 循環驗證

   for (int d : factors) {if (check(nums, d)) {printResult(nums, d);return;}
   }
   

   • 從小到大遍歷因數，驗證每個因數對應的子數組是否符合循環條件。

4. 驗證邏輯

   private static boolean check(int[] nums, int d) {for (int i = 0; i < nums.length; i++) {if (nums[i] != nums[i % d]) {return false;}}return true;
   }
   

   • 核心邏輯：數組的每個元素必須等于其對應子數組位置的元素。

5. 結果輸出

   private static void printResult(int[] nums, int d) {StringBuilder sb = new StringBuilder();for (int i = 0; i < d; i++) {sb.append(nums[i]);if (i