简易内存池2 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

请实现一个简易内存池,根据请求命令完成内存分配和释放。

内存池支持两种操作命令，REQUEST和RELEASE，其格式为:

  • REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址;如果内存不足，或指定的大小为0，则输error。
  • RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。

注意：

1.内存池总大小为100字节

2.内存池地址分配必须是连续内存，并优先从低地址分配

3.内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。

4.不会释放已电请的内存块的中间地排

5.释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。

输入描述

首行为整数N表示操作命令的个数，取值范围: 0 N<100。

接下来的N行,每行将给出一个操作命令，操作命令和参数之间用“=”分割。

输出描述

见题面输出要求

示例1

输入：
3
REQUEST=30
RELEASE=0
REQUEST=30

输出：
0
0

题解

解题思路

该问题要求实现一个简易内存池，支持两种操作命令：REQUEST 和 RELEASE。

  • REQUEST 表示请求分配指定大小内存，

  • RELEASE 表示释放之前分配的内存。

内存池总大小为 100 字节，地址分配必须是连续内存，并优先从低地址分配。

解题思路主要包括以下几个步骤：

  1. 定义内存池的大小、内存使用状态、已分配内存的字典（映射首地址到内存大小）。
  2. 实现 request 方法，用于处理请求分配内存的操作。遍历内存池，找到连续的空闲内存块，并记录已分配的内存块。
  3. 实现 release 方法，用于处理释放内存的操作。在已分配的内存块中查找要释放的地址，将其标记为空闲状态。
  4. 在 main 函数中，根据输入命令调用相应方法，输出结果。

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        Solution solution = new Solution();
        for (int i = 0; i < n; i++) {
            String[] split = in.nextLine().split("=");
            int val = Integer.parseInt(split[1]);
            if ("REQUEST".equals(split[0])) {
                // 申请内存
                solution.request(val);
            } else {
                // 释放内存
                solution.release(val);
            }
        }
    }
}

class Solution {
    // 声明一个静态字符串变量，用于表示错误信息
    public static String ERROR = "error";

    // 内存大小
    private int size;
    // 内存使用状态
    private boolean[] mem;

    // 已经使用的内存<首地址, 内存大小>
    private Map<Integer, Integer> used = new HashMap<>();

    public Solution() {
        this.size = 100;
        this.mem = new boolean[size];
    }

    // 申请内存
    public void request(int val) {
        if (val == 0 || val > 100) {
            System.out.println(ERROR);
            return;
        }

        for (int i = 0; i < size; i++) {
            // 当前内存已被使用
            if (mem[i]) continue;

            int cnt = 0;  // 空闲的连续内存大小
            while (i + cnt < size && !mem[i + cnt]) cnt++;

            // 空间足够分配
            if (cnt >= val) {
                // 记录已经申请的内存片段
                used.put(i, val);

                // 标记内存点已被使用
                while (--val >= 0) mem[i + val] = true;

                System.out.println(i);
                return;
            }

            i += cnt;
        }

        System.out.println(ERROR);
    }

    // 释放内存
    public void release(int addr) {
        if (!used.containsKey(addr)) {  // 不存在的首地址
            System.out.println(ERROR);
            return;
        }

        // 释放内存片段
        int s = addr, len = used.get(s);
        // 标记内存点空闲
        for (int i = 0; i < len; i++) mem[s + i] = false;
        used.remove(addr);
    }
}

Python

class Solution:
    # 类变量，用于表示错误信息
    ERROR = "error"

    def __init__(self):
        self.size = 100
        # 内存使用状态
        self.mem = [False] * self.size
        # 已经使用的内存 {首地址: 内存大小}
        self.used = {}

    # 申请内存
    def request(self, val):
        if val == 0 or val > 100:
            print(self.ERROR)
            return

        i = 0
        while i < self.size:
            # 当前内存已被使用
            if self.mem[i]:
                i += 1
                continue

            cnt = 0  # 空闲的连续内存大小
            while i + cnt < self.size and not self.mem[i + cnt]:
                cnt += 1

            # 空间足够分配
            if cnt >= val:
                # 记录已经申请的内存片段
                self.used[i] = val

                # 标记内存点已被使用
                for j in range(val):
                    self.mem[i + j] = True

                print(i)
                return

            i += cnt

        print(self.ERROR)

    # 释放内存
    def release(self, addr):
        if addr not in self.used:  # 不存在的首地址
            print(self.ERROR)
            return

        # 释放内存片段
        s, length = addr, self.used[addr]
        # 标记内存点空闲
        for i in range(length):
            self.mem[s + i] = False
        del self.used[addr]


def main():
    n = int(input())
    solution = Solution()

    for _ in range(n):
        relation = input().split("=")
        val = int(relation[1])

        if relation[0] == "REQUEST":
            # 申请内存
            solution.request(val)
        else:
            # 释放内存
            solution.release(val)


if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <sstream>

using namespace std;

void request(vector<bool>& mem, unordered_map<int, int>& used, int val) {
    const int size = mem.size();

    if (val == 0 || val > size) {
        cout << "error" << endl;
        return;
    }

    for (int i = 0; i < size; ) {
        if (mem[i]) {
            ++i;
            continue;
        }

        int cnt = 0;  // 空闲的连续内存大小
        while (i + cnt < size && !mem[i + cnt]) {
            ++cnt;
        }

        if (cnt >= val) {
            used[i] = val;

            for (int j = 0; j < val; ++j) {
                mem[i + j] = true;
            }

            cout << i << endl;
            return;
        }

        i += cnt;
    }

    cout << "error" << endl;
}

void release(vector<bool>& mem, unordered_map<int, int>& used, int addr) {
    if (used.find(addr) == used.end()) {
        cout << "error" << endl;
        return;
    }

    int len = used[addr];

    for (int i = 0; i < len; ++i) {
        mem[addr + i] = false;
    }

    used.erase(addr);
}

int main() {
    int n;
    cin >> n;
    cin.ignore();  // Consume the newline after n

    const int size = 100;
    // 内存使用状态
    vector<bool> mem(size, false);
    // 已经使用的内存<首地址, 内存大小>
    unordered_map<int, int> used;

    for (int i = 0; i < n; ++i) {
        string line;
        getline(cin, line);
        int    pos       = line.find('=');
        string operation = line.substr(0, pos);
        int    val       = stoi(line.substr(pos + 1));

        if (operation == "REQUEST") {
            request(mem, used, val);
        } else {
            release(mem, used, val);
        }
    }

    return 0;
}

‍❤️‍华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/423581.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Day21-磁盘管理之raid及分区

Day21-磁盘管理之raid及分区

Day21-磁盘管理之raid及分区 1 Raid技术1.1 什么是Raid?1.2 为什么服务器需要Raid?1.3 什么是Raid级别?1.4 Raid有哪些实现方式&#xff1f;1.5 什么是RAID0&#xff1f;&#xff08;图&#xff09;1.6 什么是RAID1&#xff1f;&#xff08;图&#xff09;1.7 什么是RAID5&a…
阅读更多...
Python之Flask框架~四大内置对象

Python之Flask框架~四大内置对象

1.g global全局对象 g对象是专门用来保存用户的数据的 g对象在一次请求中的所有的代码的地方, 都是可以使用的 突破变量存储位置限制，为数据传递添加了新的方式，比如我们在before_request产生一个数据在后面需要使 用, 可以保存在g对象中, 在其他视图西数中就可以使用这个数据…
阅读更多...
LaTeX-设置图像大小

LaTeX-设置图像大小

文章目录 LaTeX-设置图像大小1.导入图片2.更改图像大小并旋转图像2.1按比例缩放2.2将图像缩放到特定的宽度和高度2.3将图片设置为与文字宽度相同2.4旋转图片 LaTeX-设置图像大小 在本文中&#xff0c;将解释如何以最常见的格式包含图像&#xff0c;如何缩小、放大和旋转它们。…
阅读更多...
Day11：信息打点-Web应用企业产权指纹识别域名资产网络空间威胁情报

Day11：信息打点-Web应用企业产权指纹识别域名资产网络空间威胁情报

目录 Web信息收集工具 业务资产-应用类型分类 Web单域名获取-接口查询 Web子域名获取-解析枚举 Web架构资产-平台指纹识别 思维导图 章节知识点&#xff1a; Web&#xff1a;语言/CMS/中间件/数据库/系统/WAF等 系统&#xff1a;操作系统/端口服务/网络环境/防火墙等 应用…
阅读更多...
考研机试C++题目精选

考研机试C++题目精选

更多内容会在godownio.github.io更新 算法练习&#xff08;C代码&#xff09; 考研上机或C语言代码笔试准备&#xff0c;暨大机试原题letcode牛客中南大等高校机试 快速幂算法 题目&#xff1a;输入一个整数 n &#xff0c;求 n^n 的个位数是多少。 快速幂算法&#xff1a;…
阅读更多...
集合篇之ArrayList

集合篇之ArrayList

一、源码如何分析&#xff1f; 1.成员变量 2.构造方法 3.关键方法 一些添加的方法。 二、debug看源码 我们给出下面代码&#xff1a; public void test01() {ArrayList<Integer> list new ArrayList<>();list.add(1);for (int i 2; i < 10; i) {list.add(i…
阅读更多...
Java虚拟机（JVM）从入门到实战【上】

Java虚拟机（JVM）从入门到实战【上】

Java虚拟机&#xff08;JVM&#xff09;从入门到实战【上】&#xff0c;涵盖类加载&#xff0c;双亲委派机制&#xff0c;垃圾回收器及算法等知识点&#xff0c;全系列6万字。 一、基础篇 P1 Java虚拟机导学课程 P2 初识JVM 什么是JVM Java Virtual Machine 是Java虚拟机。…
阅读更多...
Flutter中Future和Stream关系

Flutter中Future和Stream关系

Future和Stream类是Dart异步编程的核心。 Future 表示一个不会立即完成的计算过程。与普通函数直接返回结果不同的是异步函数返回一个将会包含结果的 Future。该 Future 会在结果准备好时通知调用者。 Stream 是一系列异步事件的序列。其类似于一个异步的 Iterable&#xff0c;…
阅读更多...
（三）softmax分类--九五小庞

（三）softmax分类--九五小庞

softmax分类 对数几率回归解决的是二分类的问题&#xff0c;对于多个选项的问题&#xff0c;我们可以使用softmax函数&#xff0c;它是对数几率回归在N个可能不同的值上的推广 softmax各样本分量之和为1&#xff0c;当只有两个类别时&#xff0c;与对数几率回归完全相同 损失…
阅读更多...
多个版本的Python如何不冲突？

多个版本的Python如何不冲突？

转载文章&#xff0c;防止忘记或删除 转载于&#xff1a;电脑中存在多个版本的Python如何不冲突&#xff1f; - 知乎 (zhihu.com) 如何安装多版本的Python并与之共存&#xff1f; 如果你的工作涉及到Python多版本之间开发或测试&#xff0c;那么请收藏本文&#xff0c; 如果你…
阅读更多...
Jvm之内存泄漏

Jvm之内存泄漏

1 内存溢出 1.1 概念 java.lang.OutOfMemoryError&#xff0c;是指程序在申请内存时&#xff0c;没有足够的内存空间供其使用&#xff0c;出现OutOfMemoryError。产生该错误的原因主要包括&#xff1a;JVM内存过小。程序不严密&#xff0c;产生了过多的垃圾。 程序体现: 内…
阅读更多...
CSS 【详解】响应式布局（含 rem 详解）

CSS 【详解】响应式布局（含 rem 详解）

响应式布局&#xff1a; 同一页面在不同的屏幕上有不同的布局&#xff0c;即一套代码自适应不同的屏幕。 为什么 rem 能用于实现响应式布局&#xff1f; px 绝对长度单位&#xff0c;不同客户端表现都相同&#xff0c;不具有响应式em 相对长度单位&#xff0c;相对于父元素的 f…
阅读更多...
【MATLAB源码-第147期】基于matlab的QPSK调制解调在AWGN信道，瑞利信道，莱斯信道理论与实际误码率对比仿真。

【MATLAB源码-第147期】基于matlab的QPSK调制解调在AWGN信道，瑞利信道，莱斯信道理论与实际误码率对比仿真。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 四相位移键控&#xff08;QPSK&#xff0c;Quadrature Phase Shift Keying&#xff09;是一种重要的数字调制技术&#xff0c;它通过改变信号的相位来传输数据。与其他调制技术相比&#xff0c;QPSK在相同的带宽条件下能够传…
阅读更多...
【HTML】HTML基础4.2（锚点链接）

【HTML】HTML基础4.2（锚点链接）

目录 解释锚点链接 “公式” 例子 点击回首页 解释锚点链接 在我们浏览网页的时候&#xff0c;总有目录一样的功能&#xff0c;比如 这个时候&#xff0c;只要点击相应目录&#xff0c;就可以直接跳转到相应界面&#xff0c;比如&#xff0c;点击“演职员表” 今天就让我们一…
阅读更多...
Leetcode438. 找到字符串中所有字母异位词 -hot100

Leetcode438. 找到字符串中所有字母异位词 -hot100

题目&#xff1a; 代码(首刷看解析 2024年3月2日&#xff09;&#xff1a; 感觉自己这个ac率根本不可能找得到实习 class Solution { public:vector<int> findAnagrams(string s, string p) {int plen p.size(), slen s.size();if (slen < plen) return {};vector…
阅读更多...
蓝桥杯备战刷题four（自用）

蓝桥杯备战刷题four（自用）

1.砝码称重 #include <iostream> #include <vector> using namespace std; const int N110; const int M100010; int w[N]; int n; int f[N][M]; int m; int ans; //f[i][j]表示到第i个砝码进行放置时的称得的重量为j的方案数 int main() {cin>>n;for(int i1…
阅读更多...
【解决（几乎）任何机器学习问题】:交叉验证

【解决（几乎）任何机器学习问题】:交叉验证

在上⼀章中&#xff0c;我们没有建⽴任何模型。原因很简单&#xff0c;在创建任何⼀种机器学习模型之前&#xff0c;我们必须知道什么是交叉检验&#xff0c;以及如何根据数据集选择最佳交叉检验数据集。 那么&#xff0c;什么是 交叉检验 &#xff0c;我们为什么要关注它&…
阅读更多...
HelixToolKit的模型旋转操作

HelixToolKit的模型旋转操作

前面加载了模型以后&#xff0c;鼠标拖动和缩放比较好操作&#xff1b;但是旋转似乎没有&#xff0c; 操作了一阵&#xff0c;也不是没有&#xff0c;应该是还不熟悉&#xff1b; 旋转的指示器在右下角&#xff0c;现在U面看到正面&#xff0c; 想看一下模型的背面&#xff0…
阅读更多...
2024年最免费的DAW混音编曲FL Studio21.2.3.4004中文破解版下载

2024年最免费的DAW混音编曲FL Studio21.2.3.4004中文破解版下载

FLStudio21.2.3.4044中文破解版完整下载是最好的音乐开发和制作软件也称为水果循环。它是最受欢迎的工作室&#xff0c;因为它包含了一个主要的听觉工作场所。最新fl studio破解版有不同的功能&#xff0c;如它包含图形和音乐音序器&#xff0c;帮助您使完美的配乐在一个美妙的…
阅读更多...
powershell常用命令分类

powershell常用命令分类

powershell常用命令分为三类&#xff1a;get类、set类、write类。 一 Get类 1.Get-Command &#xff1a; 得到所有PowerShell命令&#xff0c;获取有关 cmdlet 以及有关 Windows PowerShell 命令的其他元素的基本信息。包括Cmdlet、Alias、Function。 2.Get-Process &#xf…
阅读更多...
最新文章

Copyright @ 2022~2023