数据结构设计

LeetCode力扣难度是否完成
146. LRU Cache146. LRU 缓存🟠202050306🟢
460. LFU Cache460. LFU 缓存🔴🔴
729. My Calendar I729. 我的日程安排表 I🟠🔴
950. Reveal Cards In Increasing Order950. 按递增顺序显示卡牌🟠🔴
1700. Number of Students Unable to Eat Lunch1700. 无法吃午餐的学生数量🟢202050307🟢
155. Min Stack155. 最小栈🟠🔴
1670. Design Front Middle Back Queue1670. 设计前中后队列🟠🔴
895. Maximum Frequency Stack895. 最大频率栈🔴🔴
224. Basic Calculator224. 基本计算器🔴🔴
227. Basic Calculator II227. 基本计算器 II🟠🔴

146. LRU 缓存

请设计 最近 最少使用 约束的数据结构

20250307 39 分钟调试完成，需要确认的是，List初始化需要为空，而不是orderList: make([]int, capacity) 这个是创建capacity个0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
type LRUCache struct {
	orderList []int
	cacheMaps map[int]int
	capacity  int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		orderList: make([]int, 0, capacity), // 39 分钟调试完成，需要确认的是，List初始化需要为空，而不是orderList: make([]int, capacity) 这个是创建capacity个0
		cacheMaps: make(map[int]int, capacity),
		capacity:  capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	// key 存在与单独的环境中
	if _, ok := this.cacheMaps[key]; ok {
		this.Update(key)
		return this.cacheMaps[key]
	}
	return -1
}

func (this *LRUCache) Update(key int) {
	// 更新key 到最新位置
	for i := 0; i < len(this.orderList); i++ {
		if this.orderList[i] == key {
			this.orderList = append(this.orderList[:i], append(this.orderList[i+1:], this.orderList[i])...)
		}
	}
}

func (this *LRUCache) Put(key int, value int) {
	if _, ok := this.cacheMaps[key]; ok {
		// 更新key
		this.cacheMaps[key] = value
		this.Update(key)
	}  else if len(this.cacheMaps) >= this.capacity {
        fmt.Println("=",len(this.orderList), len(this.cacheMaps), this.capacity)
		// 删除key
		oldKey := this.orderList[0]
		this.orderList = this.orderList[1:]
		delete(this.cacheMaps, oldKey)
		// 新建key
		this.cacheMaps[key] = value
		this.orderList = append(this.orderList, key)
	}else if len(this.cacheMaps) < this.capacity {
        fmt.Println("<", len(this.orderList), len(this.cacheMaps), this.capacity)
		// 新建key
		this.cacheMaps[key] = value
		this.orderList = append(this.orderList, key)
    }
}

O(1) 方法双向列表，map 中直接保存列表元素指针，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
type LRUCache struct {
	cacheMaps map[int]*list.Element
	orderList *list.List
	capacity  int
}

type entry struct {
	key   int
	value int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		cacheMaps: make(map[int]*list.Element, capacity),
		orderList: list.New(),
		capacity:  capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	if elem, ok := this.cacheMaps[key]; ok {
		this.orderList.MoveToBack(elem)
		return elem.Value.(entry).value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if elem, ok := this.cacheMaps[key]; ok {
		// 更新已存在的键
		elem.Value = entry{key: key, value: value}
		this.orderList.MoveToBack(elem)
	} else {
		// 插入新键
		if len(this.cacheMaps) == this.capacity {
			// 删除最久未使用的键
			frontElem := this.orderList.Front()
			delete(this.cacheMaps, frontElem.Value.(entry).key)
			this.orderList.Remove(frontElem)
		}
		// 插入新键到链表末尾
		newElem := this.orderList.PushBack(entry{key: key, value: value})
		this.cacheMaps[key] = newElem
	}
}

1700. 无法吃午餐的学生数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package leetcode1700  
  
// 9分钟完成  
func countStudents(students []int, sandwiches []int) int {  
    // 栈模拟  
    // 结束条件  
    // 同学中数字都相同，且不等于栈顶元素 [0]  
    for !isEnd(students, sandwiches) {  
       if sandwiches[0] == students[0] {  
          sandwiches = sandwiches[1:]  
          students = students[1:]  
       } else {  
          students = append(students[1:], students[0])  
       }  
    }  
  
    return len(students)  
}  
  
func isEnd(students []int, sandwiches []int) bool {  
    for _, val := range students {  
       if val == sandwiches[0] {  
          return false  
       }  
    }  
    return true  
}