数据结构设计专题

数据结构设计

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

146. LRU 缓存

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

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

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 中直接保存列表元素指针，

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. 无法吃午餐的学生数量

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  
}