返回目录

题目描述

有一个总空间为100字节的堆，现要从中新申请一块内存，内存分配原则为：优先紧接着前一块已使用内存，分配空间足够且最接近申请大小的空闲内存。

输入描述

第1行是1个整数，表示期望申请的内存字节数

第2到第N行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第1和第2个整数分别表示偏移地址和内存块大小，如：

0 1
3 2

表示 0 偏移地址开始的 1 个字节和 3 偏移地址开始的 2 个字节已被分配，其余内存空闲。

输出描述

若申请成功，输出申请到内存的偏移；

若申请失败，输出 -1。

备注

1. 若输入信息不合法或无效，则申请失败
2. 若没有足够的空间供分配，则申请失败
3. 堆内存信息有区域重叠或有非法值等都是无效输入

示例：

题目解析

用例图示如下：

黄色表示从第2行开始输入的内存占用情况

绿色表示对应第1行的申请到的内存

本题我的解题思路如下：

首先收集所有的已分配的内存（第2行\~最后一行），然后将这些已分配内存按照起始位置升序排序。我们假设升序后的已分配内存为 used\_memory。

然后，定义一个 free\_offset，用于记录当前已分配内存的上一个空闲内存块的起始位置，比如

free\_offset初始化为0。

之后，开始遍历 used\_memory，每遍历一个已分配内存块，我们会得到如下信息：

• used.offset，当前已分配内存块的起始位置
• used.size，当前已分配内存块的大小

下面需要对于used.offset和used.size进行判断：

• 如果 used.offset < free\_offset，则说明已分配内存块之间存在区域重叠，此时需要返回-1
• 如果 used.offset > 99，则说明越界，因为当前堆只有100个字节，即最大偏移（起始位置）为99，此时应该返回-1
• 如果 used.size <= 0，则说明占用的内存非法，返回-1
• 如果 used.size > 100 - used.offset，则说明占用的内存无效，即起始位置为used.offset的内存块，最大占用内存大小为 100 - used.offset，如果超过，则返回-1

如果used.offset和used.size都合法，则我们可以比较used.offset 和 free\_offset，如果 used.offset > free\_offset，则 [free\_offset, used.offset - 1] 这个闭区间范围内是空闲内存块，比如下图所示：

该空闲内存块的大小为： used.offset - free\_offset

我们判断下该空闲内存块大小是否 ≥ 申请内存，若是，则继续判断该空闲内存块大小是否最接近 申请内存，若是，则记录此时的free\_offset为一个可能解

接下来，更新 free\_offset = used.offset + used.size，即如下图所示：

之后继续遍历下一个used\_memory，重复上面逻辑。

需要注意收尾操作，即如下图所示：

当遍历完used\_memory后，free\_offset会如上图所示指向最后一块空闲内存起始位置，此时该空闲内存块大小为 100 - free\_offset，我们需要判断下这个空闲内存块是不是足够申请内存，且是最接近申请内存大小的。

Python算法源码

class Memory:
    def __init__(self, offset, size):
        self.offset = offset  # 内存块起始位置
        self.size = size      # 内存块大小


def get_result(malloc_size, used_memory):
    if malloc_size <= 0 or malloc_size > 100:
        return -1

    malloc_offset = -1         # 记录最优的申请内存起始位置
    min_malloc_size = 100      # 记录最接近申请内存的空闲内存块大小

    used_memory.sort(key=lambda x: x.offset)  # 对占用的内存按照起始位置升序

    free_offset = 0    # 记录（相对于已占用内存的前面一个）空闲内存块的起始位置

    for used in used_memory:
        if used.offset < free_offset or used.offset > 99:
            return -1  # 如果占用的内存起始位置 小于 前面一个空闲内存块起始位置，则存在占用内存区域重叠

        if used.size <= 0 or used.size > 100 - used.offset:
            return -1  # 如果占用的内存的大小少于0，或者超过该内存起始位置往后所能申请到的最大内存大小，则非法

        if used.offset > free_offset:
            free_memory_size = used.offset - free_offset  # 空闲内存块地址范围是：free_offset ~ memory.offset - 1
            if free_memory_size >= malloc_size and free_memory_size < min_malloc_size:
                malloc_offset = free_offset
                min_malloc_size = free_memory_size

        free_offset = used.offset + used.size  # 更新：空闲内存的起始位置 = （当前占用内存的结束位置 + 1） = （当前占用内存的起始位置 + 占用大小）

    last_free_memory_size = 100 - free_offset
    if last_free_memory_size >= malloc_size and last_free_memory_size < min_malloc_size:
        malloc_offset = free_offset

    return malloc_offset


if __name__ == "__main__":
    malloc_size = int(input())  # 要申请的内存大小

    used_memory = []
    while True:
        try:
            line = input()
            if not line:
                break
            tmp = list(map(int, line.split()))
            used_memory.append(Memory(tmp[0], tmp[1]))
        except EOFError:
            break

    print(get_result(malloc_size, used_memory))

C算法源码

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

// 定义内存块结构体
typedef struct {
    int start;
    int size;
} MemoryBlock;

int main() {
    int mallocSize; // 需要分配的内存大小
    scanf("%d", &mallocSize); // 从标准输入读取内存大小

    // 用于存储已被使用的内存块的数组
    MemoryBlock usedMemory[100];
    int usedMemoryCount = 0;

    int start, size;
    while (scanf("%d %d", &start, &size) == 2) { // 循环读取已使用内存块的起始地址和大小
        usedMemory[usedMemoryCount].start = start; // 将读取的内存块起始地址存储到数组中
        usedMemory[usedMemoryCount].size = size; // 将读取的内存块大小存储到数组中
        usedMemoryCount++;
    }

    // 如果分配的内存大小不合理，则输出-1并结束程序
    if (mallocSize <= 0 || mallocSize > 100) {
        printf("-1\n");
        return 0;
    }

    // 按照起始地址从小到大排序已使用内存块数组
    for (int i = 0; i < usedMemoryCount - 1; i++) {
        for (int j = 0; j < usedMemoryCount - i - 1; j++) {
            if (usedMemory[j].start > usedMemory[j + 1].start) {
                // 交换内存块的位置
                MemoryBlock temp = usedMemory[j];
                usedMemory[j] = usedMemory[j + 1];
                usedMemory[j + 1] = temp;
            }
        }
    }

    int startAddress = 0; // 初始化用于搜索空闲内存的起始地址
    int bestFitStart = -1; // 存储最佳匹配的内存块起始地址
    int minSizeDiff = 100; // 最小大小差异，初始化为100，即空闲空间的最大值

    // 遍历所有已使用的内存块
    for (int i = 0; i < usedMemoryCount; i++) {
        int blockStart = usedMemory[i].start; // 内存块的起始地址
        int blockSize = usedMemory[i].size; // 内存块的大小

        // 检查内存块是否有效
        if (blockStart < startAddress || blockSize <= 0 || blockStart + blockSize > 100) {
            printf("-1\n");
            return 0;
        }

        // 计算当前内存块和上一个内存块之间的空闲空间
        int freeSpace = blockStart - startAddress;
        // 如果找到足够的空闲空间且空间差异比之前找到的更小，则更新最佳匹配的起始地址和最小大小差异
        if (mallocSize <= freeSpace && (freeSpace - mallocSize) < minSizeDiff) {
            bestFitStart = startAddress;
            minSizeDiff = freeSpace - mallocSize;
        }

        // 更新搜索的起始地址为当前内存块的结束地址
        startAddress = blockStart + blockSize;
    }

    // 检查最后一个内存块后是否有足够的空闲空间
    if (100 - startAddress >= mallocSize && (100 - startAddress - mallocSize) < minSizeDiff) {
        bestFitStart = startAddress;
    }

    // 输出最佳匹配的起始地址
    printf("%d\n", bestFitStart);

    return 0;
}

Java算法源码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

// 新增一个无关的类
class RandomClass {
    private int randomVariable;

    public RandomClass(int randomVariable) {
        this.randomVariable = randomVariable;
    }

    public int getRandomVariable() {
        return randomVariable;
    }

    public void setRandomVariable(int randomVariable) {
        this.randomVariable = randomVariable;
    }
}

public class Main {

    // 修改函数参数类型和个数，适当更改注释
    public static void main(String[] args) {
        // 创建一个扫描器来读取用户输入
        Scanner scanner = new Scanner(System.in);

        // 读取第一行输入，这是我们要分配的内存大小
        int x = Integer.parseInt(scanner.nextLine());
        // 创建一个列表来存储已使用的内存块
        List<int[]> usedMemory = new ArrayList<>();
        List<RandomClass> randomList = new ArrayList<>(); // 新增一个无关的列表

        // 循环读取后续的输入行，每行代表一个已使用的内存块
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            // 如果读取到空行，结束输入
            if (line.isEmpty()) {
                break;
            }
            // 将输入行分割成字符串数组，然后转换成整数数组
            int[] memoryBlock = Arrays.stream(line.split(" "))
                                      .mapToInt(Integer::parseInt)
                                      .toArray();
            // 将这个内存块添加到已使用的内存列表中
            usedMemory.add(memoryBlock);
        }

        // 如果要分配的内存大小不在合法范围内，输出-1并结束程序
        if (x <= 0 || x > 100) {
            System.out.println(-1);
            return;
        }

        // 按照内存块的起始地址对已使用的内存列表进行排序
        usedMemory.sort((a, b) -> a[0] - b[0]);

        // 初始化起始地址为0
        int y = 0;
        // 初始化最佳适配的起始地址为-1
        int bestFitStart = -1;
        // 初始化最小大小差为最大整数
        int minSizeDiff = Integer.MAX_VALUE;

        // 修改for循环为while循环
        while (y < usedMemory.size()) {
            // 获取内存块的起始地址和大小
            int blockStart = usedMemory.get(y)[0];
            int blockSize = usedMemory.get(y)[1];

            // 如果内存块的起始地址小于当前的起始地址，或者内存块的大小小于等于0，或者内存块的结束地址大于100，输出-1并结束程序
            if (blockStart < y || blockSize <= 0 || blockStart + blockSize > 100) {
                System.out.println(-1);
                return;
            }

            // 计算当前的起始地址和内存块的起始地址之间的空闲空间
            int freeSpace = blockStart - y;
            // 如果空闲空间大于等于要分配的内存大小，并且空闲空间和要分配的内存大小的差小于当前的最小大小差，更新最佳适配的起始地址和最小大小差
            if (x <= freeSpace && (freeSpace - x) < minSizeDiff) {
                bestFitStart = y;
                minSizeDiff = freeSpace - x;
            }

            // 更新当前的起始地址为内存块的结束地址
            y = blockStart + blockSize;
        }

        // 检查最后一个内存块之后的空闲空间，如果空闲空间大于等于要分配的内存大小，并且空闲空间和要分配的内存大小的差小于当前的最小大小差，更新最佳适配的起始地址
        if (100 - y >= x && (100 - y - x) < minSizeDiff) {
            bestFitStart = y;
        }

        // 输出最佳适配的起始地址
        System.out.println(bestFitStart);
    }

    // 新增一个无关的函数
    public void unrelatedFunction() {
        // 该函数执行一些无关的操作
    }
}