(C卷,100分)- 堆内存申请（Java & JS & Python & C）

在线OJ刷题

题目描述

有一个总空间为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，我们需要判断下这个空闲内存块是不是足够申请内存，且是最接近申请内存大小的。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

class Memory {
  constructor(offset, size) {
    this.offset = offset; // 内存块起始位置
    this.size = size; // 内存块大小
  }
}

void (async function () {
  // 要申请的内存大小
  const malloc_size = parseInt(await readline());

  // 已占用的内存
  const used_memory = [];

  while (true) {
    try {
      const line = await readline();

      // 本地测试使用空行作为结束条件
      // if (line.length == 0) break;

      const [offset, size] = line.split(" ").map(Number);
      used_memory.push(new Memory(offset, size));
    } catch (e) {
      break;
    }
  }

  console.log(getResult(malloc_size, used_memory));
})();

function getResult(malloc_size, used_memory) {
  // 申请的内存大小非法，则返回-1
  if (malloc_size <= 0 || malloc_size > 100) {
    return -1;
  }

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

  // 对占用的内存按照起始位置升序
  used_memory.sort((a, b) => a.offset - b.offset);

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

  for (let used of used_memory) {
    // 如果占用的内存起始位置 小于 前面一个空闲内存块起始位置，则存在占用内存区域重叠
    // 如果占用的内存起始位置 大于 99，则非法
    if (used.offset < free_offset || used.offset > 99) return -1;

    // 如果占用的内存的大小少于0，则非法
    // 如果占用的内存的大小超过该内存起始位置往后所能申请到的最大内存大小，则无效
    if (used.size <= 0 || used.size > 100 - used.offset) return -1;

    // 空闲内存块地址范围是：free_offset ~ memory.offset - 1
    if (used.offset > free_offset) {
      // 空闲内存块大小
      const free_memory_size = used.offset - free_offset;

      // 如果该空闲内存块大小足够，且最接近申请的内存大小
      if (
        free_memory_size >= malloc_size &&
        free_memory_size < min_malloc_size
      ) {
        malloc_offset = free_offset;
        min_malloc_size = free_memory_size;
      }
    }

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

  // 收尾
  const last_free_memory_size = 100 - free_offset;
  if (
    last_free_memory_size >= malloc_size &&
    last_free_memory_size < min_malloc_size
  ) {
    malloc_offset = free_offset;
  }

  return malloc_offset;
}

Java算法源码

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

public class Main {
  static class Memory {
    // 内存块起始位置
    int offset;
    // 内存块大小
    int size;

    public Memory(int offset, int size) {
      this.offset = offset;
      this.size = size;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // 要申请的内存大小
    int malloc_size = Integer.parseInt(sc.nextLine());

    // 已占用的内存
    ArrayList<Memory> used_memory = new ArrayList<>();
    while (sc.hasNextLine()) {
      String line = sc.nextLine();

      // 本地测试使用空行作为结束条件
      //      if (line.length() == 0) break;

      int[] tmp = Arrays.stream(line.split(" ")).mapToInt(Integer::parseInt).toArray();
      used_memory.add(new Memory(tmp[0], tmp[1]));
    }

    System.out.println(getResult(malloc_size, used_memory));
  }

  public static int getResult(int malloc_size, ArrayList<Memory> used_memory) {
    // 申请的内存大小非法，则返回-1
    if (malloc_size <= 0 || malloc_size > 100) {
      return -1;
    }

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

    // 对占用的内存按照起始位置升序
    used_memory.sort((a, b) -> a.offset - b.offset);

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

    for (Memory used : used_memory) {
      // 如果占用的内存起始位置 小于 前面一个空闲内存块起始位置，则存在占用内存区域重叠
      // 如果占用的内存起始位置 大于 99，则非法
      if (used.offset < free_offset || used.offset > 99) return -1;

      // 如果占用的内存的大小少于0，则非法
      // 如果占用的内存的大小超过该内存起始位置往后所能申请到的最大内存大小，则无效
      if (used.size <= 0 || used.size > 100 - used.offset) return -1;

      // 空闲内存块地址范围是：free_offset ~ memory.offset - 1
      if (used.offset > free_offset) {
        // 空闲内存块大小
        int free_memory_size = used.offset - free_offset;

        // 如果该空闲内存块大小足够，且最接近申请的内存大小
        if (free_memory_size >= malloc_size && free_memory_size < min_malloc_size) {
          malloc_offset = free_offset;
          min_malloc_size = free_memory_size;
        }
      }

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

    // 收尾
    int last_free_memory_size = 100 - free_offset;
    if (last_free_memory_size >= malloc_size && last_free_memory_size < min_malloc_size) {
      malloc_offset = free_offset;
    }

    return malloc_offset;
  }
}

Python算法源码

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


# 输入获取
malloc_size = int(input())  # 要申请的内存大小

used_memory = []  # 已占用的内存
while True:
    try:
        offset, size = map(int, input().split())
        used_memory.append(Memory(offset, size))
    except:
        break


# 算法入口
def getResult():
    # 申请的内存大小非法，则返回-1
    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:
        # 如果占用的内存起始位置 小于 前面一个空闲内存块起始位置，则存在占用内存区域重叠
        # 如果占用的内存起始位置 大于 99，则非法
        if used.offset < free_offset or used.offset > 99:
            return -1

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

        # 空闲内存块地址范围是：free_offset ~ memory.offset - 1
        if used.offset > free_offset:
            # 空闲内存块大小
            free_memory_size = used.offset - free_offset

            # 如果该空闲内存块大小足够，且最接近申请的内存大小
            if malloc_size <= free_memory_size < min_malloc_size:
                malloc_offset = free_offset
                min_malloc_size = free_memory_size

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

    # 收尾
    last_free_memory_size = 100 - free_offset
    if malloc_size <= last_free_memory_size < min_malloc_size:
        malloc_offset = free_offset

    return malloc_offset


# 算法调用
print(getResult())

C算法源码

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

#define MAX_COUNT 100

typedef struct {
    int offset;  // 内存块起始位置
    int size; // 内存块大小
} Memory;

Memory *new_Memory(int offset, int size) {
    Memory *m = (Memory *) malloc(sizeof(Memory));
    m->offset = offset;
    m->size = size;
    return m;
}

int cmp(const void *a, const void *b) {
    Memory *A = *((Memory **) a);
    Memory *B = *((Memory **) b);
    return A->offset - B->offset;
}

int getResult(int malloc_size, Memory *used_memory[], int used_memory_count) {
    // 申请的内存大小非法，则返回-1
    if (malloc_size <= 0 || malloc_size > 100) {
        return -1;
    }

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

    // 对占用的内存按照起始位置升序
    qsort(used_memory, used_memory_count, sizeof(Memory *), cmp);

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

    for (int i = 0; i < used_memory_count; i++) {
        Memory *used = used_memory[i];

        // 如果占用的内存起始位置 小于 前面一个空闲内存块起始位置，则存在占用内存区域重叠
        // 如果占用的内存起始位置 大于 99，则非法
        if (used->offset < free_offset || used->offset > 99) return -1;

        // 如果占用的内存的大小少于0，则非法
        // 如果占用的内存的大小超过该内存起始位置往后所能申请到的最大内存大小，则无效
        if (used->size <= 0 || used->size > 100 - used->offset) return -1;

        // 空闲内存块地址范围是：free_offset ~ memory.offset - 1
        if (used->offset > free_offset) {
            // 空闲内存块大小
            int free_memory_size = used->offset - free_offset;

            // 如果该空闲内存块大小足够，且最接近申请的内存大小
            if (free_memory_size >= malloc_size && free_memory_size < min_malloc_size) {
                malloc_offset = free_offset;
                min_malloc_size = free_memory_size;
            }
        }

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

    // 收尾
    int last_free_memory_size = 100 - free_offset;
    if (last_free_memory_size >= malloc_size && last_free_memory_size < min_malloc_size) {
        malloc_offset = free_offset;
    }

    return malloc_offset;
}

int main() {
    // 要申请的内存大小
    int malloc_size;
    scanf("%d", &malloc_size);
    getchar();

    // 已占用的内存
    Memory *used_memory[MAX_COUNT];
    int count = 0;

    char s[100];
    while (gets(s)) {
        // 本地测试使用空行作为结束条件
        if(strlen(s) == 0) break;

        int offset, size;
        sscanf(s, "%d %d", &offset, &size);
        used_memory[count++] = new_Memory(offset, size);
    }

    printf("%dn", getResult(malloc_size, used_memory, count));

    return 0;
}