堆内存申请 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

题目描述

有一个总空间为100字节的堆，现要从中新申请一块内存，内存分配原则为:

优先分配紧接着前一块已使用的内存，分配空间足够时分配最接近申请大小的空闲内存。

输入描述

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

第2到第N行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第1个和第2个整数分别表示偏移地址和内存块大小，如: 0 1 3 2 表示0偏移地址开始的1个字节和3偏移地址开始的2个字节已被分配，其余内存空闲。

输出描述

若申请成功，输出申请到内存的偏移 若申请失败，输出-1。

备注 1.若输入信息不合法或无效，则申请失败

2.若没有足够的空间供分配，则申请失败

3.堆内存信息有区域重叠或有非法值等都是无效输入

示例1

输入：
1
0 1
3 2

输出：
1

说明：
堆中已使用的两块内存是偏移从0开始的1字节和偏移从3开始的2字节，空闲的两块内存是偏移从1开始2个字节和偏移从5开始95字节根据分配原则，新申请的内存应从1开始分配1个字节，所以输出偏移为1。

题解

这道题属于内存管理中的内存分配问题，需要模拟堆内存的管理，根据现有已分配内存块和分配原则，来确定能否满足新的内存申请。

解题思路

1. 内存使用情况：使用一个布尔数组 used 表示每个字节的使用情况，True 表示已使用，False 表示空闲。
2. 标记内存使用 (mark)：遍历输入的已分配内存块，标记内存块中的每个字节。如果发现重叠或非法情况，则返回 False。
3. 申请内存 (allocate)：遍历 used 数组，寻找能够容纳新申请的内存块的连续空闲空间。优先选择紧邻已使用内存块的空闲空间，并且选择最接近申请大小的空闲块。
4. 解决函数 (solve)：首先标记所有已分配的内存块，然后尝试分配新申请的内存，返回内存偏移地址或者失败标志 -1。
5. 输入处理和调用：处理输入数据并调用 solve 函数。

Java

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

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int req = in.nextInt();

        List<int[]> lst = new ArrayList<>();
        while (in.hasNextInt()) {
            lst.add(new int[]{in.nextInt(), in.nextInt()});
        }
        Solution solution = new Solution();
        System.out.println(solution.solve(lst, req));
    }
}


class Solution {
    // 内存使用情况
    boolean[] used = new boolean[100];

    /**
     * 标记内存使用
     *
     * @param offset 偏移地址
     * @param size   内存块大小
     * @return
     */
    public boolean mark(int offset, int size) {
        // 输入信息不合法
        if (offset < 0 || offset > 99 || size > 100) return false;

        for (int i = 0; i < size; i++) {
            // 区域重叠非法
            if (used[offset + i]) return false;
            used[offset + i] = true;
        }

        return true;
    }

    /**
     * 申请内存
     *
     * @param reqSize 申请的内存大小
     * @return
     */
    public int allocate(int reqSize) {
        int len = used.length;
        if (reqSize > len) return -1;

        // 申请到内存的偏移、 分配内存空闲的间隙值（空闲内存空间大小 - 申请的内存空间大小）
        int offset = -1, gap = len;
        for (int left = 0; left < len; ) {
            if (used[left]) {
                left++;
                continue;
            }

            int right = left + 1;
            while (right < len && !used[right]) right++;

            // 空闲的内存空间大小
            int freeSize = right - left;
            // 空闲内存够分配 且 更接近申请的内存空间大小
            if (freeSize >= reqSize && f