2025 A卷 200分 題型

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

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

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

華為OD機試真題《書籍疊放》：

---

文章快捷目錄

題目描述及說明

Java

python

JavaScript

C++

C

GO

---

題目名稱：書籍疊放

---

• 知識點：動態規劃（最長遞增子序列變種）、排序
• 時間限制：1秒
• 空間限制：256MB
• 限定語言：不限

---

題目描述

書籍的長、寬都是整數對應 (l, w)。如果書A的長和寬都比書B的長和寬大時，則允許將B疊放在A上面。現在給定一組規格的書籍，書籍疊放時不能旋轉，請計算最多能有多少本書疊放在一起。

輸入描述
輸入：books = [[20,16],[15,11],[10,10],[9,10]]
說明：共4本書，第一本長20寬16，第二本長15寬11，依此類推。

輸出描述
輸出：3
解釋：最多疊放3本，從下到上依次為 [20,16]、[15,11]、[10,10]。

測試用例

1. 輸入：[[5,4],[6,4],[6,7],[2,3]]
   輸出：3

---

Java

問題分析

題目要求找到最多能疊放的書籍數量，每本書的長和寬都必須比下面的書嚴格小。可以通過排序和最長遞增子序列（LIS）解決。

---

解題思路

1. 排序處理：將書籍按長度升序排序，若長度相同則按寬度降序排序。這樣后續只需考慮寬度是否遞增，確保長度條件自動滿足。
2. 最長遞增子序列：在排序后的寬度數組中找到最長遞增子序列的長度，即為答案。

---

代碼實現

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();// 解析輸入int[][] books = parseInput(input);// 排序Arrays.sort(books, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);// 計算最長遞增子序列的長度int max = lengthOfLIS(books);System.out.println(max);}// 解析輸入字符串為二維數組private static int[][] parseInput(String input) {String[] parts = input.replaceAll("\\[\\[|\\]\\]", "").split("\\],\\[");int[][] books = new int[parts.length][2];for (int i = 0; i < parts.length; i++) {String[] nums = parts[i].split(",");books[i][0] = Integer.parseInt(nums[0]);books[i][1] = Integer.parseInt(nums[1]);}return books;}// 計算最長遞增子序列的長度（O(n log n)）private static int lengthOfLIS(int[][] books) {int[] tails = new int[books.length];int size = 0;for (int[] book : books) {int h = book[1];int i = Arrays.binarySearch(tails, 0, size, h);if (i < 0) i = -(i + 1);tails[i] = h;if (i == size) size++;}return size;}
}

---

代碼詳解

1. 輸入解析：

   String input = sc.nextLine();
   int[][] books = parseInput(input);
   

   • 讀取輸入字符串并解析為二維數組。例如，將[[20,16],[15,11]]轉換為books數組。

2. 排序處理：

   Arrays.sort(books, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
   

   • 按長度升序排序，長度相同則按寬度降序排序。確保后續只需處理寬度遞增。

3. 最長遞增子序列：

   int[] tails = new int[books.length];
   int size = 0;
   for (int[] book : books) {int h = book[1];int i = Arrays.binarySearch(tails, 0, size, h);if (i < 0) i = -(i + 1);tails[i] = h;