华为OD机试 2023B卷题库疯狂收录中，刷题点这里
一、题目描述
请实现一个简易内存池,根据请求命令完成内存分配和释放。
内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
1、REQUEST
请求的内存大小表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
2、RELEASE
释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
注意：
1.内存池总大小为100字节。
2.内存池地址分配必须是连续内存，并优先从低地址分配。
3.内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
4.不会释放已申请的内存块的中间地址。
5.释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。
二、输入描述
首行为整数N，表示操作命令的个数。
接下来的N行，每行将给出一个操作命令，操作命令和参数之间用“=”分割
三、输出描述
输出最后请求的内存的首地址。
如果位置已满，则输出-1。
样例：
2
REQUEST=10
REQUEST=20
输出样例：
0
10
四、解题思路
- 定义一个map，存储内存的分配情况（key：内存的首地址，value：内存的尾地址）；
- 请求内存时
- 如果map是空，放在首地址0处；
- 如果map不为空，遍历已经存入的首地址；
- 已经存入的首地址 - 第一个空闲区域的首地址 大于 请求的内存值；
- 将当前请求的内存的首地址和内存的尾地址存入map；
- 反之，重置前一个空闲区域的首地址；
- 判断剩余内存是否可以容下当前请求值；
- 如果可以容下，将当前请求的内存的首地址和内存的尾地址存入map；
- 如果容不下，输出error；
- 释放内存时，将其首地址的key移除map；
- 最后输出最后一次请求的首地址。
注意：如果最后发起的命令是RELEASE，也是可以的，会返回最后一次REQUEST的首地址。
五、Java算法源码
package com.guor.od;
import java.util.*;
public class OdTest03 {
static final String REQUEST = "REQUEST";
static final String RELEASE = "RELEASE";
static final String ERROR = "error";
static final int MAX = 100;
public static void main(String[] args) {
try {
Scanner sc = new Scanner(System.in);
// 操作命令的个数
int N = Integer.parseInt(sc.nextLine());
// 每一行的操作命令和参数
String[][] lineArr = new String[N][2];
// 接下来的N行，每行将给出一个操作命令，操作命令和参数之间用“=”分割
for (int i = 0; i < N; i++) {
lineArr[i] = sc.nextLine().split("=");
}
for (int i = 0; i < N; i++) {
// 内存大小
int value = Integer.parseInt(lineArr[i][1]);
if (lineArr[i][0].startsWith(REQUEST)) {// 请求
// 非法输入（内存池总大小为100字节）
if (value > MAX || value <= 0) {
System.out.println(ERROR);
return;
}
request(value);
} else if (lineArr[i][0].startsWith(RELEASE)) {// 释放
map.remove(value);
} else {// 非法输入
System.out.println(ERROR);
}
}
} catch (Exception e) {
// 非法输入
System.out.println(ERROR);
}
}
/**
* 存储内存的分配情况
* key：内存的首地址
* value：内存的尾地址
*/
static Map<Integer, Integer> map = new TreeMap<>();
/**
* 请求内存
* @value：大小
*/
public static void request(int value) {
int zero = 0;
// 前一个空闲区域的首地址
int beforeHeadAddress = 0;
// 如果map是空，放在首地址0处
if (map.isEmpty()) {
map.put(zero, value);
} else {
// 已经存入的首地址
List<Integer> headList = new ArrayList<>(map.keySet());
// 已经存入的首地址
for (Integer requestedHead : headList) {
// 已经存入的首地址 - 第一个空闲区域的首地址 大于 请求的内存值
if (requestedHead - beforeHeadAddress >= value) {
/**
* beforeHeadAddress：内存的首地址
* beforeHeadAddress + value：内存的尾地址
*/
map.put(beforeHeadAddress, beforeHeadAddress + value);
} else {
// 前一个空闲区域的首地址
beforeHeadAddress = map.get(requestedHead);
}
}
// 判断剩余内存是否可以容下当前请求值
if (MAX - beforeHeadAddress >= value) {
map.put(beforeHeadAddress, beforeHeadAddress + value);
} else {
// 如果位置已满，则输出-1。
System.out.println("-1");
}
}
System.out.println(beforeHeadAddress);
}
}
六、效果展示
1、输入
4
REQUEST=20
REQUEST=30
RELEASE=0
REQUEST=30
2、输出
50
3、说明
- 第一次请求20
- 第二请求30
- 第三次释放首地址为0的内存
- 第四次请求30，第一个空闲区域的首地址是0，但空闲长度只有20，放不下当前请求的地址，因此消耗剩余内存，输出最后一次请求的首地址为50。
4、再输入
6
REQUEST=20
REQUEST=30
RELEASE=0
REQUEST=30
REQUEST=10
REQUEST=10
5、再说明
- 第一次请求20
- 第二请求30
- 第三次释放首地址为0的内存
- 第四次请求30，第一个空闲区域的首地址是0，但空闲长度只有20，放不下当前请求的地址，因此消耗剩余内存。
- 第五次请求10，第一个空闲区域的首地址是0，长度20，可以容下当前请求的内存10。
- 第六次请求10，第一个空闲区域的首地址是10，长度10，可以容下当前请求的内存10。
- 输出最后一次请求的首地址为10。
6、如果走后一次请求的是20，会怎么样呢？
🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
