华为OD机试 2023B卷题库疯狂收录中，刷题点这里
一、题目描述
请实现一个简易内存池,根据请求命令完成内存分配和释放。
内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
REQUEST
请求的内存大小表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
RELEASE
释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
注意：
内存池总大小为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); } } static Map<Integer, Integer> map = new TreeMap<>(); 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) { 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在线答疑。
来源地址：https://blog.csdn.net/guorui_java/article/details/132197477
