2502.设计内存分配器

链接：2502.设计内存分配器
难度：Medium
标签：设计、数组、哈希表、模拟
简介：给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。请你设计一个具备以下功能的内存分配器。

题解 1 - cpp

• 编辑时间：2022-12-11
• 执行用时：40ms
• 内存消耗：29.7MB
• 编程语言：cpp
• 解法介绍：链表。

#include <vector>
#include <set>
#include <iostream>
#include <unordered_map>
#define X first
#define Y second
#define lb(x) ((x) & (-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug freopen("input","r",stdin)
using namespace std;
typedef long long ll;
class Node {
public:
    int l, r, mID;
    Node *next, *prev;
    Node() {}
    Node(int l, int r, int mID): l(l), r(r), mID(mID), next(nullptr), prev(nullptr) {}
    void insert(Node *node) {
      node->next = next;
      node->prev = prev;
      if (next) next = node;
      if (prev) prev->prev = node;
    }
    void remove() {
      Node *nextNode = next;
      next = nextNode->next;
      nextNode->prev = this;
    }
};
class Allocator {
public:
    int n;
    Node *head, *tail;
    Allocator(int n): n(n), head(new Node(-1, -1, 0)), tail(new Node(n, n, 0)){
      head->next = tail;
      tail->prev = head;
    }
    int allocate(int size, int mID) {
        Node *p = head;
        while (p != tail) {
            int s = p->next->l - p->r - 1;
            if (s >= size) {
              Node *newNode = new Node(p->r + 1, p->r + size, mID);
              p->insert(newNode);
              return p->r + 1;
            }
            p = p->next;
        }
        return -1;
    }
    int free(int mID) {
        Node *p = head;
        int sum = 0;
        while (p != tail) {
          if (p->next->mID == mID) {
            sum += p->next->r - p->next->l + 1;
            p->remove();
            continue;
          }
          p = p->next;
        }
        print();
        return sum;
    }
    void print() {
      Node *p = head;
      while (true) {
        if (p == tail) {
          break;
        }
        p = p->next;
      }
    }
};