返回目录

题目描述

• 请实现一个简易内存池,根据请求命令完成内存分配和释放。
• 内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
• REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
• RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。

注意：

1. 内存池总大小为100字节。
2. 内存池地址分配必须是连续内存，并优先从低地址分配。
3. 内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
4. 不会释放已申请的内存块的中间地址。
5. 释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。

输入描述

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

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

输出描述

请求分配指定大小内存时，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error

释放掉之前分配的内存时，释放成功无需输出，如果释放不存在的首地址则输出error。

示例：

题目解析

我的解题思路如下：

定义一个used数组，用来存储已被占用的内存区间，即[起始位置，结束位置]。

初始化给used数组一个 [100,101]，表示存在一个已占有内存区间[100,101]，这个内存区间将作为尾边界使用。

当REQUEST申请size大小的内存时，我们从start=0位置开始申请，即申请[start, start+size-1]区间，接下来看该区间是否和used[i]区间存在交叉，如果存在交xian叉，则说明申请的内存区间中部分内存已被使用，因此我们应该更新 start = usedi + 1位置，重新申请一个区间，这样就必然不和used[i]区间交叉了，但是要继续和used[i+1]区间比较。

直到找到一个不存在交叉的内存区间，打印此时的start，并将申请到的内存区间插入到used数组中，注意插入位置是 i 。

如果一直都找不到不存在交叉的内存区间，则打印error。

当RELEASE释放起始位置addr的内存时，我们只需要遍历每一个used[i]，比较usedi和addr是否相同，若相同，则表示找到了要释放的内存，此时只要将used[i]从used中删除即可。

如果没有找到，则打印error。

Python算法源码

# 算法入口
def get_result(cmds):
    # used保存被占用的内存 [起始地址，结束地址]，初始时有一个[100,101]作为尾边界限定
    used = [[100, 101]]
 
    for cmd in cmds:
        key, val = cmd
 
        # 申请内存
        if key == "REQUEST":
            # 当指令为REQUEST时，对应值为要申请的内存的大小，即size
            size = int(val)
 
            if size == 0:
                print("error")
                continue
 
            # 我们默认从start=0位置开始检查可用内存区间
            start = 0
            flag = True
 
            for i in range(len(used)):
                end = start + size - 1
                # 要申请的内存区间
                range_ = [start, end]
 
                # 检查要申请的内存区间和已占有的内存区间是否交叉
                if not has_intersection(used[i], range_):
                    # 若不存在交叉，则将申请区间加入used中
                    used.insert(i, range_)
                    flag = False
                    # 并打印此时申请区间的起始位置
                    print(start)
                    break
                else:
                    # 若存在交叉，则将变更要申请的内存区间的起始位置
                    start = used[i][1] + 1
 
            # 一旦申请到内存，那么flag就会被赋值为false，否则就保持true，意味着每申请到内存，则打印error
            if flag:
                print("error")
        # 释放内存
        else:
            # 当指令为RELEASE时，值为要释放内存的起始地址addr
            addr = int(val)
 
            if addr >= 100:
                print("error")
                continue
 
            flag = True
 
            for i in range(len(used)):
                # 到已占有内存中找起始位置是addr的，找到则将该区间从used中删除，表示解除占用
                if used[i][0] == addr:
                    used.pop(i)
                    flag = False
                    break
 
            # 一旦释放成功，则flag就会被置为false，否则就保持True,意味着没有内存释放，则打印error
            if flag:
                print("error")


# 判断两个区间是否存在交集
def has_intersection(range1, range2):
    s1, e1 = range1
    s2, e2 = range2
 
    if s1 == s2:
        return True
    elif s1 < s2:
        return e1 >= s2
    else:
        return e2 >= s1


if __name__ == "__main__":
    n = int(input())
    cmds = [input().split("=") for _ in range(n)]
    get_result(cmds)

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 判断两个区间是否存在交集
bool hasIntersection(int range1[2], int range2[2]) {
    int start1 = range1[0];
    int end1 = range1[1];

    int start2 = range2[0];
    int end2 = range2[1];

    if (start1 == start2) return true;
    else if (start1 < start2) return end1 >= start2;
    else return end2 >= start1;
}

// 算法入口，处理请求和释放内存命令
void getResult(int count, char cmds[][15]) {
    // used保存被占用的内存 [起始地址，结束地址]，初始时有一个[100,101]作为尾边界限定
    int usedMemory[count][2];
    usedMemory[0][0] = 100;
    usedMemory[0][1] = 101;

    // 遍历每个命令
    for (int i = 0; i < count; i++) {
        char key[8], value[8];
        sscanf(cmds[i], "%[^=]=%s", key, value);

        // 申请内存
        if (strcmp(key, "REQUEST") == 0) {
            // 解析请求的内存大小
            int size = atoi(value);

            // 处理无效请求
            if (size == 0) {
                printf("error\n");
                continue;
            }

            // 检查可用内存
            int startPoint = 0;
            bool flag = true;

            // 遍历已占用内存列表
            for (int j = 0; j <= i; j++) {
                int endPoint = startPoint + size - 1;
                int range[2] = {startPoint, endPoint}; // 计算请求的内存区间

                // 检查是否与已占用内存区间交叉
                if (!hasIntersection(usedMemory[j], range)) {
                    // 添加申请的内存区间到已占用内存列表
                    for (int k = i; k > j; k--) {
                        usedMemory[k][0] = usedMemory[k - 1][0];
                        usedMemory[k][1] = usedMemory[k - 1][1];
                    }
                    usedMemory[j][0] = startPoint;
                    usedMemory[j][1] = endPoint;
                    flag = false;
                    printf("%d\n", startPoint); // 打印申请内存的起始位置
                    break;
                } else {
                    startPoint = usedMemory[j][1] + 1; // 更新下一个检查的起始位置
                }
            }

            // 处理未能成功申请内存的情况
            if (flag) printf("error\n");
        }
        // 释放内存
        else {
            // 解析要释放的内存起始地址
            int address = atoi(value);

            // 处理无效释放请求
            if (address >= 100) {
                printf("error\n");
                continue;
            }

            bool flag = true;

            // 遍历已占用内存列表
            for (int j = 0; j <= i; j++) {
                // 找到要释放的内存区间并移除
                if (usedMemory[j][0] == address) {
                    for (int k = j; k < i; k++) {
                        usedMemory[k][0] = usedMemory[k + 1][0];
                        usedMemory[k][1] = usedMemory[k + 1][1];
                    }
                    flag = false;
                    break;
                }
            }

            // 处理未能成功释放内存的情况
            if (flag) printf("error\n");
        }
    }
}

// 示例函数，将两个整数相加，并加上常量值
void newFunction(int x, int y) {
    const int CONSTANT_VALUE = 10;
    int result = x + y + CONSTANT_VALUE;
    printf("Result: %d\n", result);
}

int main() {
    // 读取输入行数
    int inputCount;
    scanf("%d", &inputCount);

    // 读取输入命令，每个命令格式为"REQUEST/RELEASE=value"
    char commands[inputCount][15];
    for (int i = 0; i < inputCount; i++) scanf("%s", commands[i]);

    // 调用处理命令的函数
    getResult(inputCount, commands);

    return 0;
}

Java算法源码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    // 输入获取
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入行数
        int inputCount = scanner.nextInt();

        // 读取输入命令，每个命令格式为"REQUEST/RELEASE=value"
        String[][] commands = new String[inputCount][2];
        for (int i = 0; i < inputCount; i++) commands[i] = scanner.next().split("=");

        // 调用处理命令的函数
        getResult(inputCount, commands);
    }

    // 算法入口，处理请求和释放内存命令
    public static void getResult(int count, String[][] cmds) {
        // used保存被占用的内存 [起始地址，结束地址]，初始时有一个[100,101]作为尾边界限定
        LinkedList<Integer[]> usedMemory = new LinkedList<>();
        usedMemory.add(new Integer[]{100, 101});

        // 遍历每个命令
        for (String[] cmd : cmds) {
            String key = cmd[0];
            String value = cmd[1];

            // 申请内存
            if ("REQUEST".equals(key)) {
                // 解析请求的内存大小
                int size = Integer.parseInt(value);

                // 处理无效请求
                if (size == 0) {
                    System.out.println("error");
                    continue;
                }

                // 检查可用内存
                int startPoint = 0;
                boolean flag = true;

                // 遍历已占用内存列表
                for (int i = 0; i < usedMemory.size(); i++) {
                    int endPoint = startPoint + size - 1;
                    Integer[] range = {startPoint, endPoint}; // 计算请求的内存区间

                    // 检查是否与已占用内存区间交叉
                    if (!hasIntersection(usedMemory.get(i), range)) {
                        usedMemory.add(i, range); // 添加申请的内存区间到已占用内存列表
                        flag = false;
                        System.out.println(startPoint); // 打印申请内存的起始位置
                        break;
                    } else {
                        startPoint = usedMemory.get(i)[1] + 1; // 更新下一个检查的起始位置
                    }
                }

                // 处理未能成功申请内存的情况
                if (flag) System.out.println("error");
            }
            // 释放内存
            else {
                // 解析要释放的内存起始地址
                int address = Integer.parseInt(value);

                // 处理无效释放请求
                if (address >= 100) {
                    System.out.println("error");
                    continue;
                }

                boolean flag = true;

                // 遍历已占用内存列表
                for (int i = 0; i < usedMemory.size(); i++) {
                    // 找到要释放的内存区间并移除
                    if (usedMemory.get(i)[0] == address) {
                        usedMemory.remove(i);
                        flag = false;
                        break;
                    }
                }

                // 处理未能成功释放内存的情况
                if (flag) System.out.println("error");
            }
        }
    }

    // 判断两个区间是否存在交集
    public static boolean hasIntersection(Integer[] range1, Integer[] range2) {
        int start1 = range1[0];
        int end1 = range1[1];

        int start2 = range2[0];
        int end2 = range2[1];

        if (start1 == start2) return true;
        else if (start1 < start2) return end1 >= start2;
        else return end2 >= start1;
    }

  
    private static final int CONSTANT_VALUE = 10;

    // 示例函数，将两个整数相加，并加上常量值
    public static void newFunction(int x, int y) {
        int result = x + y + CONSTANT_VALUE;
        System.out.println("Result: " + result);
    }
}