设计内存分配器

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 free(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

示例：

输入
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[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.free(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.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Allocator { public: Allocator(int n) { } int allocate(int size, int mID) { } int free(int mID) { } }; /** * Your Allocator object will be instantiated and called as such: * Allocator* obj = new Allocator(n); * int param_1 = obj->allocate(size,mID); * int param_2 = obj->free(mID); */

python3 解法, 执行用时: 148 ms, 内存消耗: 16 MB, 提交时间: 2022-12-14 11:17:55

from sortedcontainers import SortedList

class Allocator:

    def __init__(self, n: int):
        self.sl = SortedList([(-1, 1, -1), (n, 1, -1)])

    def allocate(self, size: int, I: int) -> int:
        for (lp, ln, _), (rp, _, _) in pairwise(self.sl):
            if rp - (lp + ln) >= size:
                self.sl.add((lp + ln, size, I))
                return lp + ln
        return -1

    def free(self, I: int, res=0) -> int:
        remove = [(i, n) for i, (_, n, id) in enumerate(self.sl) if id == I]
        while remove:
            i, n = remove.pop()
            res += n
            self.sl.pop(i)
        return res

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

golang 解法, 执行用时: 392 ms, 内存消耗: 7.1 MB, 提交时间: 2022-12-14 11:17:03

type Allocator struct {
	a      []int        // 存储具体的数组
	cap    int          // 存储总容量
	hs     map[int]int  // 存储每一个位置对应的 mID
	freeID map[int]bool // 存储每一个 mID 当前是否有对应数据段
	cnt    map[int]int  // 存储每一个 mID 对应的总数量
}

func Constructor(n int) Allocator {
	t := Allocator{
		a:      make([]int, n),
		cap:    n,
		hs:     make(map[int]int),
		freeID: make(map[int]bool),
		cnt:    make(map[int]int),
	}
	for i := 0; i < t.cap; i++ {
		t.hs[i] = 0
	}
	return t
}

func (this *Allocator) Allocate(size int, mID int) int {
	for i := 0; i < this.cap; i++ {
		j := i
		for j-i < size && j < this.cap {
			if val, _ := this.freeID[this.hs[j]]; val == true || this.hs[j] == 0 {
				j += 1
			} else {
				break
			}
		}
		if j-i == size {
			for x := i; x < i+size; x++ {
				this.hs[x] = mID
			}
			delete(this.freeID, mID)
			this.cnt[mID] += size
			return i
		} else {
            i = j
        }
	}
	return -1
}

func (this *Allocator) Free(mID int) int {
	this.freeID[mID] = true
	t := this.cnt[mID]
	this.cnt[mID] = 0
	return t
}

/**
 * Your Allocator object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Allocate(size,mID);
 * param_2 := obj.Free(mID);
 */

golang 解法, 执行用时: 56 ms, 内存消耗: 7 MB, 提交时间: 2022-12-14 11:16:05

type Allocator []int

func Constructor(n int) Allocator {
	return make([]int, n)
}

func (a Allocator) Allocate(size, mID int) int {
	cnt := 0
	for i, id := range a {
		if id > 0 {
			cnt = 0
		} else if cnt++; cnt == size {
			for j := i; j > i-size; j-- {
				a[j] = mID
			}
			return i - size + 1
		}
	}
	return -1
}

func (a Allocator) Free(mID int) (ans int) {
	for i, id := range a {
		if id == mID {
			ans++
			a[i] = 0
		}
	}
	return
}


/**
 * Your Allocator object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Allocate(size,mID);
 * param_2 := obj.Free(mID);
 */

python3 解法, 执行用时: 1020 ms, 内存消耗: 15.8 MB, 提交时间: 2022-12-14 11:15:23

'''
暴力模拟，数据量小
'''
class Allocator:
    def __init__(self, n: int):
        self.a = [0] * n

    def allocate(self, size: int, mID: int) -> int:
        cnt = 0
        for i, _id in enumerate(self.a):
            if _id:
                cnt = 0
            else:
                cnt += 1
                if cnt == size:
                    self.a[i - size + 1: i + 1] = [mID] * size
                    return i - size + 1
        return -1

    def free(self, mID: int) -> int:
        cnt = 0
        for i, _id in enumerate(self.a):
            if _id == mID:
                cnt += 1
                self.a[i] = 0
        return cnt

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

上一题

下一题

详情