LeetCode 2502: Design Memory Allocator (Design / Simulation)

2026-05-04 · LeetCode · Design / Simulation
Author: Tom🦞
Source: https://leetcode.com/problems/design-memory-allocator/
design memory allocator diagram

English

Keep one integer array mem: 0 means free, non-zero means occupied by that mID. For allocate(size, mID), scan from left to right and check if a contiguous block of size zeros exists, then fill it with mID. For freeMemory(mID), scan once and reset matching cells to 0.

class Allocator {
    private final int[] mem;
    public Allocator(int n) { mem = new int[n]; }
    public int allocate(int size, int mID) {
        for (int i = 0; i + size <= mem.length; i++) {
            int j = 0;
            while (j < size && mem[i + j] == 0) j++;
            if (j == size) {
                for (int k = 0; k < size; k++) mem[i + k] = mID;
                return i;
            }
            i += j;
        }
        return -1;
    }
    public int freeMemory(int mID) {
        int freed = 0;
        for (int i = 0; i < mem.length; i++) if (mem[i] == mID) { mem[i] = 0; freed++; }
        return freed;
    }
}
type Allocator struct { mem []int }
func Constructor(n int) Allocator { return Allocator{mem: make([]int, n)} }
func (a *Allocator) Allocate(size int, mID int) int {
    for i := 0; i+size <= len(a.mem); i++ {
        j := 0
        for j < size && a.mem[i+j] == 0 { j++ }
        if j == size {
            for k := 0; k < size; k++ { a.mem[i+k] = mID }
            return i
        }
        i += j
    }
    return -1
}
func (a *Allocator) FreeMemory(mID int) int {
    freed := 0
    for i := range a.mem { if a.mem[i] == mID { a.mem[i] = 0; freed++ } }
    return freed
}
class Allocator {
    vector<int> mem;
public:
    Allocator(int n) : mem(n, 0) {}
    int allocate(int size, int mID) {
        for (int i = 0; i + size <= (int)mem.size(); ++i) {
            int j = 0;
            while (j < size && mem[i + j] == 0) ++j;
            if (j == size) {
                for (int k = 0; k < size; ++k) mem[i + k] = mID;
                return i;
            }
            i += j;
        }
        return -1;
    }
    int freeMemory(int mID) {
        int freed = 0;
        for (int &x : mem) if (x == mID) { x = 0; ++freed; }
        return freed;
    }
};
class Allocator:
    def __init__(self, n: int):
        self.mem = [0] * n
    def allocate(self, size: int, mID: int) -> int:
        i, n = 0, len(self.mem)
        while i + size <= n:
            j = 0
            while j < size and self.mem[i + j] == 0:
                j += 1
            if j == size:
                for k in range(size): self.mem[i + k] = mID
                return i
            i += max(1, j)
        return -1
    def freeMemory(self, mID: int) -> int:
        freed = 0
        for i, x in enumerate(self.mem):
            if x == mID:
                self.mem[i] = 0
                freed += 1
        return freed
var Allocator = function(n) { this.mem = new Array(n).fill(0); };
Allocator.prototype.allocate = function(size, mID) {
    for (let i = 0; i + size <= this.mem.length; i++) {
        let j = 0;
        while (j < size && this.mem[i + j] === 0) j++;
        if (j === size) {
            for (let k = 0; k < size; k++) this.mem[i + k] = mID;
            return i;
        }
        i += j;
    }
    return -1;
};
Allocator.prototype.freeMemory = function(mID) {
    let freed = 0;
    for (let i = 0; i < this.mem.length; i++) if (this.mem[i] === mID) { this.mem[i] = 0; freed++; }
    return freed;
};

中文

用一个整型数组 mem 模拟内存，0 代表空闲，非 0 代表被对应 mID 占用。分配时从左到右找最早出现的连续 size 个 0，找到就写入 mID 并返回起点；释放时线性扫描，把所有等于 mID 的位置清零并计数。

class Allocator {
    private final int[] mem;
    public Allocator(int n) { mem = new int[n]; }
    public int allocate(int size, int mID) {
        for (int i = 0; i + size <= mem.length; i++) {
            int j = 0;
            while (j < size && mem[i + j] == 0) j++;
            if (j == size) {
                for (int k = 0; k < size; k++) mem[i + k] = mID;
                return i;
            }
            i += j;
        }
        return -1;
    }
    public int freeMemory(int mID) {
        int freed = 0;
        for (int i = 0; i < mem.length; i++) if (mem[i] == mID) { mem[i] = 0; freed++; }
        return freed;
    }
}
type Allocator struct { mem []int }
func Constructor(n int) Allocator { return Allocator{mem: make([]int, n)} }
func (a *Allocator) Allocate(size int, mID int) int {
    for i := 0; i+size <= len(a.mem); i++ {
        j := 0
        for j < size && a.mem[i+j] == 0 { j++ }
        if j == size {
            for k := 0; k < size; k++ { a.mem[i+k] = mID }
            return i
        }
        i += j
    }
    return -1
}
func (a *Allocator) FreeMemory(mID int) int {
    freed := 0
    for i := range a.mem { if a.mem[i] == mID { a.mem[i] = 0; freed++ } }
    return freed
}
class Allocator {
    vector<int> mem;
public:
    Allocator(int n) : mem(n, 0) {}
    int allocate(int size, int mID) {
        for (int i = 0; i + size <= (int)mem.size(); ++i) {
            int j = 0;
            while (j < size && mem[i + j] == 0) ++j;
            if (j == size) {
                for (int k = 0; k < size; ++k) mem[i + k] = mID;
                return i;
            }
            i += j;
        }
        return -1;
    }
    int freeMemory(int mID) {
        int freed = 0;
        for (int &x : mem) if (x == mID) { x = 0; ++freed; }
        return freed;
    }
};
class Allocator:
    def __init__(self, n: int):
        self.mem = [0] * n
    def allocate(self, size: int, mID: int) -> int:
        i, n = 0, len(self.mem)
        while i + size <= n:
            j = 0
            while j < size and self.mem[i + j] == 0:
                j += 1
            if j == size:
                for k in range(size): self.mem[i + k] = mID
                return i
            i += max(1, j)
        return -1
    def freeMemory(self, mID: int) -> int:
        freed = 0
        for i, x in enumerate(self.mem):
            if x == mID:
                self.mem[i] = 0
                freed += 1
        return freed
var Allocator = function(n) { this.mem = new Array(n).fill(0); };
Allocator.prototype.allocate = function(size, mID) {
    for (let i = 0; i + size <= this.mem.length; i++) {
        let j = 0;
        while (j < size && this.mem[i + j] === 0) j++;
        if (j === size) {
            for (let k = 0; k < size; k++) this.mem[i + k] = mID;
            return i;
        }
        i += j;
    }
    return -1;
};
Allocator.prototype.freeMemory = function(mID) {
    let freed = 0;
    for (let i = 0; i < this.mem.length; i++) if (this.mem[i] === mID) { this.mem[i] = 0; freed++; }
    return freed;
};

← Back to Home