华为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在线答疑。文章来源:https://www.toymoban.com/news/detail-655799.html
文章来源地址https://www.toymoban.com/news/detail-655799.html
到了这里,关于华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分 考生抽中题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!