Leetcode2502：设计内存分配器

题目描述：

给你一个整数 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 对应的所有内存单元。返回释放的内存单元数目。

代码思路：

初始化 (`init` 方法)

n: 表示总共有多少个元素（或内存块）可供分配。
container: 一个长度为 n 的列表，用于记录每个元素的归属（即哪个ID分配了这个元素）。初始时，所有元素都未被分配，因此列表中的值全部为 0。
num_used: 记录当前有多少个元素被占用。

分配内存 (`allocate` 方法)

size: 请求分配的内存块大小（即连续的元素数量）。
mID: 请求分配内存块的ID（用于标识分配的内存块）。

步骤：

预先判断：如果请求的内存块大小大于剩余可分配的元素数量（self.n - self.num_used），则直接返回 -1，表示分配失败。
寻找起始下标：从列表的开头开始，寻找第一个连续空闲的元素块，该块的大小至少为 size。
- 使用两个指针 i 和 j，其中 i 是当前考察的起始位置，j 是尝试扩展的结束位置。
- 如果 self.container[i] 不为 0，表示该位置已被占用，i 向后移动一位继续寻找。
- 如果 self.container[i] 为 0，则尝试扩展，直到找到一个连续空闲块的大小至少为 size 或到达列表末尾。
分配内存：如果找到了一个足够大的连续空闲块，则将这个块内的所有元素标记为 mID，并更新 num_used。
返回结果：如果成功分配，返回起始下标 i；如果失败，返回 -1。

释放内存 (`freeMemory` 方法)

mID: 要释放的内存块的ID。

步骤：

遍历列表：遍历 container 列表，找到所有归属为 mID 的元素。
释放内存：将这些元素的值重置为 0，表示它们现在是空闲的。
更新计数：记录释放的元素数量，并从 num_used 中减去这个数量。
返回结果：返回释放的元素数量。

代码实现：

class Allocator:

    def __init__(self, n: int):
        self.n = n # 一共有多少个元素
        self.container = [0]*n # 每个元素归属哪个ID（ID为0表示当前下标空闲）
        self.num_used = 0 # 有多少个下标被占用
        
    def allocate(self, size: int, mID: int) -> int:
        if size > self.n-self.num_used: return -1 # 预先判断有没有可能分配内存
        i = 0 # 寻找起始下标
        while i<self.n-size+1:
            if self.container[i]:
                i += 1
                continue
            # 当前位置有空
            j = i # [i,j) 左右边界
            while j<self.n and self.container[j]==0 and j-i<size: j += 1
            # 看下j停下来的位置
            if j-i>=size: # 可以分配大小为size的连续内存
                for l in range(i,j): self.container[l]=mID
                self.num_used += size
                return i
            else: # 无法分配，跳过
                i = j
        return -1

    def freeMemory(self, mID: int) -> int:
        ans = 0
        for i in range(self.n):
            if self.container[i]==mID:
                self.container[i]=0
                ans += 1
        self.num_used -= ans
        return ans
        


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