2502. 设计内存分配器¶

难度：中等

题目¶

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

分配一块大小为 size 的连续空闲内存单元并赋 id mID 。
释放给定 id mID 对应的所有内存单元。

注意：

多个块可以被分配到同一个 mID 。
你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
int freeMemory(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

示例：

输入
["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.freeMemory(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.freeMemory(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.freeMemory(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。

提示：

1 <= n, size, mID <= 1000
最多调用 allocate 和 free 方法 1000 次

Reference

题解¶

分别维护空闲内存块和已分配内存块。分配内存时，遍历空闲内存块，找到第一个满足条件的块。释放内存时，首先将已分配内存块中的内存块释放，然后合并空闲内存块。

import bisect

class Allocator:

    def __init__(self, n: int):
        self.free = [(0, n)]
        self.allocated = defaultdict(list)

    def allocate(self, size: int, mID: int) -> int:
        if not self.free:
            return -1
        for i in range(len(self.free)):
            start, length = self.free[i]
            if length < size:
                continue
            if length == size:
                self.free.pop(i)
            else:
                self.free[i] = (start + size, length - size)
            self.allocated[mID].append((start, size))
            return start
        return -1

    def freeMemory(self, mID: int) -> int:
        if mID not in self.allocated:
            return 0
        total_length = 0
        for start, length in self.allocated.pop(mID):
            total_length += length
            loc = bisect.bisect_left(self.free, start, key=lambda x: x[0])
            right = None if loc == len(self.free) else loc + 1
            left = None if loc == 0 else loc - 1
            self.free.insert(loc, (start, length))
            self.mergeMemory(loc, left, right)
        return total_length

    def mergeMemory(self, mid, left=None, right=None):
        leftMerge = left is not None and (
            sum(self.free[left]) == self.free[mid][0]
        )
        rightMerge = right is not None and (
            sum(self.free[mid]) == self.free[right][0]
        )
        if rightMerge:
            self.free[mid] = (
                self.free[mid][0],
                self.free[mid][1] + self.free[right][1]
            )
            self.free.pop(right)
        if leftMerge:
            self.free[left] = (
                self.free[left][0],
                self.free[left][1] + self.free[mid][1]
            )
            self.free.pop(mid)

# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.freeMemory(mID)

2502. 设计内存分配器¶

题目¶

题解¶

评论