【华为OD机试真题】堆内存申请 · 堆内存最佳分配 (Python /JS)

_JeanW_

412人浏览 · 2026-03-24 22:09:25

_JeanW_ · 2026-03-24 22:09:25 发布

一、真题

题目描述：

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

输入描述：

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

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

输出描述：

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

备注：

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

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

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

示例1：

输入：
1
0 1
3 2
输出：

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

二、解题思路图解💡

步骤 1：数据清洗与校验

读取所有已分配块，存储为列表/数组。
校验逻辑：
- offset < 0 或 size <= 0 → 非法。
- offset + size > 100 → 越界，非法。
- 重叠检测：将已分配块按 offset 排序，遍历检查 current.offset < prev.offset + prev.size。若成立，则重叠，非法。
- 若任何校验失败，直接输出 -1。

步骤 2：构建空闲区间列表

假设已分配块已按 offset 升序排序：[B1, B2, ..., Bn]。
空闲块来源于三部分：

头部空闲：若 B1.offset > 0，则存在空闲块 [0, B1.offset)，长度 B1.offset。
中间空闲：遍历 i 从 0 到 n-2，若 B[i].offset + B[i].size < B[i+1].offset，则存在空闲块 [B[i].end, B[i+1].offset)，长度 B[i+1].offset - B[i].end。
尾部空闲：若 Bn.end < 100，则存在空闲块 [Bn.end, 100)，长度 100 - Bn.end。

步骤 3：贪心匹配 (Best Fit)

遍历所有生成的空闲块：

若 free.size < reqSize：跳过。
若 free.size >= reqSize：
- 记录当前差值 diff = free.size - reqSize。
- 维护一个全局最小差值 minDiff 和对应的最佳偏移 bestOffset。
- 若 diff < minDiff，更新 minDiff 和 bestOffset。
- (进阶)：若 diff == minDiff，通常选择偏移地址更小的（题目示例未涉及冲突，但代码中可加上此逻辑保证确定性）。

步骤 4：输出结果

若找到 bestOffset，输出该值。
若未找到（即没有足够大的空闲块），输出 -1。

三、Python 语言实现

import sys

def solve():
    # 读取所有输入行
    input_data = sys.stdin.read().split()
    
    if not input_data:
        print("-1")
        return

    iterator = iter(input_data)
    
    try:
        req_size = int(next(iterator))
        if req_size <= 0:
            print("-1")
            return
    except StopIteration:
        print("-1")
        return

    allocated = []
    
    # 解析已分配内存块
    while True:
        try:
            offset_str = next(iterator)
            size_str = next(iterator)
            offset = int(offset_str)
            size = int(size_str)
            allocated.append({'offset': offset, 'size': size, 'end': offset + size})
        except StopIteration:
            break
        except ValueError:
            # 非整数输入
            print("-1")
            return

    # 1. 按偏移量排序
    allocated.sort(key=lambda x: x['offset'])

    # 2. 基础校验
    for block in allocated:
        if block['offset'] < 0 or block['size'] <= 0 or block['end'] > 100:
            print("-1")
            return

    # 3. 重叠检测
    for i in range(1, len(allocated)):
        prev = allocated[i-1]
        curr = allocated[i]
        # 如果当前块的起点小于前一块的终点，说明重叠
        if curr['offset'] < prev['end']:
            print("-1")
            return

    # 4. 贪心查找最佳适配
    best_offset = -1
    min_diff = float('inf')
    
    current_pos = 0
    
    for block in allocated:
        if block['offset'] > current_pos:
            # 发现空闲块 [current_pos, block['offset'])
            free_size = block['offset'] - current_pos
            if free_size >= req_size:
                diff = free_size - req_size
                if diff < min_diff:
                    min_diff = diff
                    best_offset = current_pos
                # 如果 diff == min_diff，由于是从左到右遍历，当前的 best_offset 已经是更小的了，无需更新
        
        current_pos = block['end']

    # 检查尾部空闲
    if current_pos < 100:
        free_size = 100 - current_pos
        if free_size >= req_size:
            diff = free_size - req_size
            if diff < min_diff:
                min_diff = diff
                best_offset = current_pos

    print(best_offset)

if __name__ == "__main__":
    solve()

Python 代码亮点

简洁的输入处理：利用 sys.stdin.read().split() 一次性读取所有 token，自动处理换行和空格，简化解析逻辑。
字典结构：使用字典存储块信息，代码可读性强。
异常捕获：通过 try-except 处理非整数输入和迭代结束，确保鲁棒性。
浮点无穷大：使用 float('inf') 初始化最小差值，逻辑清晰。

四、JavaScript 语言实现

const readline = require('readline');

function solve() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
        terminal: false
    });

    const lines = [];
    
    rl.on('line', (line) => {
        lines.push(line.trim());
    });

    rl.on('close', () => {
        // 合并所有行并按空格分割成 token 数组
        const tokens = lines.join(' ').split(/\s+/).filter(t => t !== '');
        
        if (tokens.length === 0) {
            console.log("-1");
            return;
        }

        let idx = 0;
        let reqSize;

        try {
            reqSize = parseInt(tokens[idx++], 10);
            if (isNaN(reqSize) || reqSize <= 0) {
                console.log("-1");
                return;
            }
        } catch (e) {
            console.log("-1");
            return;
        }

        const allocated = [];

        // 解析已分配内存块
        while (idx < tokens.length) {
            if (idx + 1 >= tokens.length) {
                // 奇数个 token，格式错误
                console.log("-1");
                return;
            }
            const offset = parseInt(tokens[idx++], 10);
            const size = parseInt(tokens[idx++], 10);

            if (isNaN(offset) || isNaN(size)) {
                console.log("-1");
                return;
            }

            allocated.push({ offset, size, end: offset + size });
        }

        // 1. 按偏移量排序
        allocated.sort((a, b) => a.offset - b.offset);

        // 2. 基础校验
        for (const block of allocated) {
            if (block.offset < 0 || block.size <= 0 || block.end > 100) {
                console.log("-1");
                return;
            }
        }

        // 3. 重叠检测
        for (let i = 1; i < allocated.length; i++) {
            const prev = allocated[i - 1];
            const curr = allocated[i];
            if (curr.offset < prev.end) {
                console.log("-1");
                return;
            }
        }

        // 4. 贪心查找最佳适配
        let bestOffset = -1;
        let minDiff = Infinity;
        let currentPos = 0;

        for (const block of allocated) {
            if (block.offset > currentPos) {
                const freeSize = block.offset - currentPos;
                if (freeSize >= reqSize) {
                    const diff = freeSize - reqSize;
                    if (diff < minDiff) {
                        minDiff = diff;
                        bestOffset = currentPos;
                    }
                }
            }
            currentPos = block.end;
        }

        // 检查尾部空闲
        if (currentPos < 100) {
            const freeSize = 100 - currentPos;
            if (freeSize >= reqSize) {
                const diff = freeSize - reqSize;
                if (diff < minDiff) {
                    minDiff = diff;
                    bestOffset = currentPos;
                }
            }
        }

        console.log(bestOffset);
    });
}

solve();

JavaScript 代码亮点

异步流处理：使用 readline 模块处理标准输入，适合 Node.js 环境。
Token 化处理：将所有输入行合并后 split，统一处理空格和换行，逻辑健壮。
数组方法：利用 sort 和 forEach (或 for...of) 使代码具有函数式风格，简洁易读。
Infinity 常量：使用 JS 内置 Infinity 进行初始比较。

五、核心逻辑推演（以示例为例）

输入：

1
0 1
3 2

执行流程：

解析：reqSize = 1。已分配块：[{offset:0, size:1, end:1}, {offset:3, size:2, end:5}]。
校验：
- 块1：0~1，合法。
- 块2：3~5，合法。
- 重叠检查：3 >= 1，无重叠。
扫描空闲块：
- 初始：currentPos = 0。
- 处理块1 (0~1)：block.offset (0) == currentPos (0)，无头部空闲。更新 currentPos = 1。
- 处理块2 (3~5)：block.offset (3) > currentPos (1)。
  - 发现空闲块：[1, 3)，长度 2。
  - 判断：2 >= 1 (满足)。
  - 差值：2 - 1 = 1。
  - 更新：minDiff = 1, bestOffset = 1。
  - 更新 currentPos = 5。
- 尾部检查：currentPos (5) < 100。
  - 发现空闲块：[5, 100)，长度 95。
  - 判断：95 >= 1 (满足)。
  - 差值：95 - 1 = 94。
  - 比较：94 > 1 (不是最小)，不更新。
输出：1。

结果验证：与题目示例输出一致。

六、易错点总结⚠️

重叠的定义：[0, 1) 和 [1, 2) 是不重叠的。代码中必须使用 < 来判断重叠（curr.start < prev.end），如果用 <= 会误判相邻块为重叠。
空输入处理：如果没有已分配内存行，程序应能正确处理，此时整个 0-100 都是空闲块。上述代码逻辑天然支持（循环不执行，直接进入尾部检查）。
相等长度的选择：题目要求“最接近”，若有两个空闲块长度一样且都最小，通常选择偏移地址较小的。上述代码从左向右遍历，天然保证了这一点（只有 diff < minDiff 才更新，相等时不更新，保留了前面的小偏移）。
非法值检测：题目备注提到“非法值”，包括负数、非整数等，代码中必须包含类型转换检查和范围判断。

七、复杂度分析📊

时间复杂度：
- 排序： O(Nlog⁡N) ，其中 N 是已分配块的数量。
- 遍历扫描： O(N) 。
- 总体： O(Nlog⁡N) 。对于 N 较小的情况（通常机考题 N 不会极大），效率极高。
空间复杂度：
- O(N) 用于存储已分配块列表。
- Python 和 JS 的字符串处理可能会产生临时数组，但在内存限制内完全可控。