2502. Longest Square Streak in an Array

题目 #

You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

  1. Allocate a block of size consecutive free memory units and assign it the id mID.
  2. Free all memory units with the given id mID.

Note that:

  • Multiple blocks can be allocated to the same mID.
  • You should free all the memory units with mID, even if they were allocated in different blocks.

Implement the Allocator class:

  • Allocator(int n) Initializes an Allocator object with a memory array of size n.
  • int allocate(int size, int mID) Find the leftmost block of size consecutive free memory units and allocate it with the id mID. Return the block’s first index. If such a block does not exist, return -1.
  • int free(int mID) Free all memory units with the id mID. Return the number of memory units you have freed.  

Example 1:

Input
["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]]
Output
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

Explanation
Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.
loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,_,_,_,_,_,_,_,_,_]. We return 0.
loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,_,_,_,_,_,_,_,_]. We return 1.
loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,_,_,_,_,_,_,_]. We return 2.
loc.free(2); // Free all memory units with mID 2. The memory array becomes [1,_, 3,_,_,_,_,_,_,_]. We return 1 since there is only 1 unit with mID 2.
loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,_,3,4,4,4,_,_,_,_]. We return 3.
loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes [1,1,3,4,4,4,_,_,_,_]. We return 1.
loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes [1,1,3,4,4,4,1,_,_,_]. We return 6.
loc.free(1); // Free all memory units with mID 1. The memory array becomes [_,_,3,4,4,4,_,_,_,_]. We return 3 since there are 3 units with mID 1.
loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.
loc.free(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.

  Constraints:

  • 1 <= n, size, mID <= 1000
  • At most 1000 calls will be made to allocate and free.

思路1 #

分析 #

  • 就是设计一个内存池，删除全部清理，分配取最左侧匹配的
  • 使用一个链表存储所有已分配内存，取第一个和最后一个为边界
  • 再使用一个map存储清理时的mID对应在链表的迭代器

代码 # 

 1type mem struct {
 2	start int
 3	end   int // end不属于范围
 4	mID   int
 5}
 6
 7type Allocator struct {
 8	memMap  *list.List
 9	freeMap map[int][]*list.Element
10}
11
12func Constructor(n int) Allocator {
13	res := Allocator{}
14	res.memMap = list.New()
15	// 放一个头节点进去
16	res.memMap.PushFront(mem{
17		start: 0,
18		end:   0,
19		mID:   -1,
20	})
21	// 放一个尾节点进去
22	res.memMap.PushBack(mem{
23		start: n,
24		end:   n,
25		mID:   -1,
26	})
27	res.freeMap = make(map[int][]*list.Element)
28	fmt.Printf("init %p\r\n", &(res.memMap))
29	return res
30}
31
32func (this *Allocator) Allocate(size int, mID int) int {
33	// 从第一个开始找所有间隔是否有空位
34	p := this.memMap.Front()
35	for n := p.Next(); n != nil; p, n = n, n.Next() {
36		if n.Value.(mem).start-p.Value.(mem).end < size {
37			continue
38		}
39		start := p.Value.(mem).end
40		fmt.Printf("insert %p\r\n", &(this.memMap))
41		this.memMap.InsertAfter(mem{
42			start: start,
43			end:   start + size,
44			mID:   mID,
45		}, p)
46		if _, ok := this.freeMap[mID]; !ok {
47			this.freeMap[mID] = make([]*list.Element, 0, 1)
48		}
49		this.freeMap[mID] = append(this.freeMap[mID], p.Next())
50		return start
51	}
52	return -1
53}
54
55func (this *Allocator) Free(mID int) int {
56	ans := 0
57	if idMap, ok := this.freeMap[mID]; ok {
58		for _, v := range idMap {
59			ans += v.Value.(mem).end - v.Value.(mem).start
60			this.memMap.Remove(v)
61		}
62		this.freeMap[mID] = this.freeMap[mID][:0]
63	}
64	return ans
65}
66
67/**
68 * Your Allocator object will be instantiated and called as such:
69 * obj := Constructor(n);
70 * param_1 := obj.Allocate(size,mID);
71 * param_2 := obj.Free(mID);
72 */