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]
。
測試用例
- 輸入:
[[5,4],[6,4],[6,7],[2,3]]
輸出:3
Java
問題分析
題目要求找到最多能疊放的書籍數量,每本書的長和寬都必須比下面的書嚴格小。可以通過排序和最長遞增子序列(LIS)解決。
解題思路
- 排序處理:將書籍按長度升序排序,若長度相同則按寬度降序排序。這樣后續只需考慮寬度是否遞增,確保長度條件自動滿足。
- 最長遞增子序列:在排序后的寬度數組中找到最長遞增子序列的長度,即為答案。
代碼實現
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;}
}
代碼詳解
-
輸入解析:
String input = sc.nextLine(); int[][] books = parseInput(input);
- 讀取輸入字符串并解析為二維數組。例如,將
[[20,16],[15,11]]
轉換為books
數組。
- 讀取輸入字符串并解析為二維數組。例如,將
-
排序處理:
Arrays.sort(books, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
- 按長度升序排序,長度相同則按寬度降序排序。確保后續只需處理寬度遞增。
-
最長遞增子序列:
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;