2025 A卷 200分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

本文收录于专栏：《2025华为OD真题目录+全流程解析/备考攻略/经验分享》

华为OD机试真题《简易内存池》：

---

---

题目名称：简易内存池

---

• 知识点：内存管理（首次适应算法）、逻辑处理
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

请实现一个简易内存池，根据请求命令完成内存分配和释放。
内存池支持两种操作命令：REQUEST和RELEASE，其格式为：

1. REQUEST=请求的内存大小：请求分配指定大小的连续内存。
   • 若分配成功，返回分配到的内存首地址；
   • 若内存不足或请求大小为0，输出 error。
2. RELEASE=释放的内存首地址：释放指定首地址的内存块。
   • 释放成功无需输出；
   • 若释放不存在的首地址，输出 error。

约束条件：

1. 内存池总大小为 100字节，地址从0开始分配。
2. 分配必须为连续内存，优先从低地址分配。
3. 释放后的内存可被再次分配，但已释放的内存块不可二次释放。
4. 不会释放已分配内存块的中间地址，仅能通过首地址操作。

输入描述：

• 首行为整数 N（操作命令数，0 < N ≤ 100）。
• 后续 N 行，每行一个操作命令，格式为 命令=参数（如 REQUEST=10）。

输出描述：

• 按顺序输出每个 REQUEST 的分配结果或 error，RELEASE 仅需在失败时输出 error。

示例：
输入：

5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10  

输出：

0  
10  
30  
0  

说明：

1. 第一条 REQUEST=10 分配地址0~9，返回首地址0。
2. 第二条 REQUEST=20 分配地址10~29，返回首地址10。
3. RELEASE=0 释放首地址0的内存块，0~9变为空闲。
4. 第三条 REQUEST=20 因0~9空间不足，从30开始分配，返回首地址30。
5. 第四条 REQUEST=10 重新分配0~9，返回首地址0。

补充说明：

• 输入保证合法，无需处理非法参数（如负数）。
• 同一列表元素顺序不可变，动态规划或回溯法为典型解法。

---

Java

问题分析

我们需要实现一个简易内存池，支持 REQUEST 和 RELEASE 命令。内存池总大小为 100 字节，地址从 0 开始。分配时采用首次适应算法，优先低地址分配连续内存。释放时需处理合并相邻空闲块。

---

解题思路

1. 数据结构设计：

   • 空闲块列表：按起始地址升序排列，记录每个空闲块的起始地址和大小。
   • 已分配块字典：记录已分配块的首地址和大小，用于快速查找。

2. REQUEST 处理：

   • 遍历空闲块列表，找到第一个足够大的块。
   • 分割该块，记录已分配块，更新空闲列表。

3. RELEASE 处理：

   • 检查要释放的块是否存在。
   • 将释放的块插入空闲列表并合并相邻块。

---

代码实现

import java.util.*;class Block {int start;int size;public Block(int s, int sz) {start = s;size = sz;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = Integer.parseInt(scanner.nextLine());List<Block> freeList = new ArrayList<>();freeList.add(new Block(0, 100)); // 初始空闲块：0-99Map<Integer, Integer> allocated = new HashMap<>();for (int i = 0; i < N; i++) {String line = scanner.nextLine();String[] parts = line.split("=");String cmd = parts[0];int param = Integer.parseInt(parts[1]);if (cmd.equals("REQUEST")) {// REQUEST 处理int size = param;if (size <= 0) {System.out.println("error");continue;}boolean found = false;for (int j = 0; j < freeList.size(); j++) {Block block = freeList.get(j);if (block.size >= size) {// 分配该块allocated.put(block.start, size);System.out.println(block.start);// 处理剩余空间int remaining = block.size - size;if (remaining > 0) {freeList.set(j, new Block(block.start + size, remaining));} else {freeList.remove(j);}found = true;break;}}if (!found) {System.out.println("error");}} else if (cmd.equals("RELEASE")) {// RELEASE 处理int addr = param;if (!allocated.containsKey(addr)) {System.out.println("error");continue;}int size = allocated.get(addr);Block newBlock = new Block(addr, size);// 插入到正确位置int insertIdx = 0;while (insertIdx < freeList.size() && freeList.get(insertIdx).start < newBlock.start) {insertIdx++;}freeList.add(insertIdx, newBlock);// 合并左边while (insertIdx > 0) {Block prev = freeList.get(insertIdx - 1);if (prev.start + prev.size == newBlock.start) {newBlock.start = prev.start;newBlock.size += prev.size;freeList.remove(insertIdx - 1);insertIdx--;} else {break;}}// 合并右边while (insertIdx < freeList.size() - 1) {Block next = freeList.get(insertIdx + 1);if (newBlock.start + newBlock.size == next.start) {newBlock.size += next.size;freeList.remove(insertIdx + 1);} else {break;}}allocated.remove(addr);}}}
}

---

代码详细解析

1. Block 类：表示内存块，包含起始地址 start 和大小 size。
2. 初始化：
   • freeList 初始为 0-99 的块。
   • allocated 记录已分配块的首地址和大小。
3. REQUEST 处理：
   • 遍历 freeList 找第一个足够大的块。
   • 分配后分割剩余空间，更新 freeList 和 allocated。
4. RELEASE 处理：
   • 检查地址是否存在，不存在则输出错误。
   • 插入释放的块到 freeList，合并相邻块。

---

示例测试

示例1输入：

5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10  

输出：

0  
10  
30  
0  

解析：

• 前两次分配分别获得 0-9 和 10-29。
• 释放 0-9 后，第三次分配 30-49。
• 第四次分配重新使用 0-9。

示例2输入：

3  
REQUEST=50  
RELEASE=0  
REQUEST=50  

输出：

0  
error  
0  

解析：

• 首次分配 0-49，释放后合并为 0-99。
• 再次分配成功。

示例3输入：

4  
REQUEST=100  
RELEASE=0  
REQUEST=99  
REQUEST=1  

输出：

0  
99  
error  

解析：

• 首次分配全部内存，释放后再次分配 99 字节成功，剩余 1 字节不足以分配。

---

综合分析

1. 时间复杂度：O(N^2)

   • 每个 REQUEST 和 RELEASE 最坏需遍历列表，但 N ≤ 100，实际可行。

2. 空间复杂度：O(N)

   • 空闲块和已分配块的数量与操作数相关，但总量较小。

3. 优势：

   • 首次适应算法：简单高效，优先低地址分配。
   • 合并策略：释放时合并相邻块，减少内存碎片。

4. 适用场景：

   • 适用于操作数较少且内存管理简单的场景。

---

python

问题分析

我们需要实现一个简易内存池，支持 REQUEST 和 RELEASE 操作。内存池总大小为 100 字节，地址从 0 开始分配。分配时采用首次适应算法，优先从低地址分配连续内存。释放后需合并相邻空闲块。

---

解题思路

1. 数据结构设计：

   • 空闲块列表：按起始地址升序排列，每个块记录起始地址和大小。
   • 已分配块字典：记录已分配块的首地址和大小，便于快速查找。

2. REQUEST 处理：

   • 遍历空闲块列表，找到第一个足够大的块。
   • 分割该块，记录已分配块，更新空闲列表。

3. RELEASE 处理：

   • 检查要释放的块是否存在。
   • 将释放的块插入空闲列表并合并相邻块。

---

代码实现

import bisectn = int(input())
free_blocks = [(0, 100)]  # 空闲块列表，按起始地址排序
allocated = {}             # 已分配块字典 {起始地址: 大小}for _ in range(n):line = input().strip()cmd, param = line.split('=')param = int(param)if cmd == 'REQUEST':size = paramif size <= 0:print('error')continuefound =