golang刷leetcode技巧之如何实现全 O(1) 的数据结构

背景介绍

在解决 LeetCode 的问题时，我们经常遇到需要设计全 O(1) 的数据结构的问题。这种数据结构的基本操作（增删改查）都可以在常数时间内完成。在 Golang 中实现这样的数据结构需要运用一些巧妙的技巧和数据结构。

使用 Hash 表

Hash 表是实现全 O(1) 数据结构的常用方法之一。Golang 中的 map 数据结构就是一种哈希表实现。通过使用 map，我们可以将操作的时间复杂度降低到 O(1)。以下是一些使用 Hash 表实现全 O(1) 数据结构的具体方法：

1. 使用 map 存储数据和对应的计数，实现支持增删查的数据结构。

type MyDataStructure struct {
    data map[int]int     // 存储数据的 map
}

func Constructor() MyDataStructure {
    return MyDataStructure{
        data: make(map[int]int),
    }
}

func (this *MyDataStructure) Add(key int) {
    this.data[key]++
}

func (this *MyDataStructure) Remove(key int) {
    if count, ok := this.data[key]; ok {
        if count > 1 {
            this.data[key]--
        } else {
            delete(this.data, key)
        }
    }
}

func (this *MyDataStructure) Exists(key int) bool {
    _, ok := this.data[key]
    return ok
}

Golang

复制
2. 使用 map 存储数值到位置的映射，实现栈、队列等数据结构。

type MyStack struct {
    data   []int       // 存储数据的切片
    values map[int]int // 存储数值到位置的映射
}

func Constructor() MyStack {
    return MyStack{
        data:   make([]int, 0),
        values: make(map[int]int),
    }
}

func (this *MyStack) Push(val int) {
    this.data = append(this.data, val)
    this.values[val] = len(this.data) - 1
}

func (this *MyStack) Pop() int {
    length := len(this.data)
    val := this.data[length-1]
    delete(this.values, val)
    this.data = this.data[:length-1]
    return val
}

func (this *MyStack) Peek() int {
    return this.data[len(this.data)-1]
}

func (this *MyStack) Empty() bool {
    return len(this.data) == 0
}

Golang

复制

使用双向链表和 Hash 表

双向链表是解决某些特定问题的全 O(1) 数据结构的另一种常用方法。通过结合哈希表和双向链表，我们可以实现一些复杂的数据结构。

1. 使用双向链表和 Hash 表实现支持增删查的数据结构。

type ListNode struct {
    Val  int
    Prev *ListNode
    Next *ListNode
}

type MyDataStructure struct {
    head  *ListNode             // 头节点
    tail  *ListNode             // 尾节点
    nodes map[int]*ListNode     // 存储值到节点的映射
}

func Constructor() MyDataStructure {
    head := &ListNode{}
    tail := &ListNode{}
    head.Next = tail
    tail.Prev = head
    return MyDataStructure{
        head:  head,
        tail:  tail,
        nodes: make(map[int]*ListNode),
    }
}

func (this *MyDataStructure) Add(key int) {
    if _, ok := this.nodes[key]; !ok {
        node := &ListNode{Val: key}
        this.nodes[key] = node
        this.addAfter(node, this.tail.Prev)
    }
}

func (this *MyDataStructure) Remove(key int) {
    if node, ok := this.nodes[key]; ok {
        this.remove(node)
        delete(this.nodes, key)
    }
}

func (this *MyDataStructure) Exists(key int) bool {
    _, ok := this.nodes[key]
    return ok
}

func (this *MyDataStructure) addAfter(node *ListNode, prev *ListNode) {
    node.Prev = prev
    node.Next = prev.Next
    prev.Next.Prev = node
    prev.Next = node
}

func (this *MyDataStructure) remove(node *ListNode) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
    node.Prev = nil
    node.Next = nil
}

Golang

复制
2. 使用双向链表和 Hash 表实现 LRU Cache。

type LRUCache struct {
    head  *Node               // 头节点
    tail  *Node               // 尾节点
    nodes map[int]*Node       // 存储键到节点的映射
    capacity int              // 缓存容量
}

type Node struct {
    Key   int
    Value int
    Prev  *Node
    Next  *Node
}

func Constructor(capacity int) LRUCache {
    head := &Node{}
    tail := &Node{}
    head.Next = tail
    tail.Prev = head
    return LRUCache{
        head:     head,
        tail:     tail,
        nodes:    make(map[int]*Node),
        capacity: capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    if node, ok := this.nodes[key]; ok {
        this.moveToHead(node)
        return node.Value
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if node, ok := this.nodes[key]; ok {
        node.Value = value
        this.moveToHead(node)
        return
    }

    if len(this.nodes) >= this.capacity {
        this.removeTail()
    }

    node := &Node{
        Key:   key,
        Value: value,
    }
    this.nodes[key] = node
    this.addToHead(node)
}

func (this *LRUCache) addToHead(node *Node) {
    node.Prev = this.head
    node.Next = this.head.Next
    this.head.Next.Prev = node
    this.head.Next = node
}

func (this *LRUCache) remove(node *Node) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
    node.Prev = nil
    node.Next = nil
}

func (this *LRUCache) moveToHead(node *Node) {
    this.remove(node)
    this.addToHead(node)
}

func (this *LRUCache) removeTail() {
    node := this.tail.Prev
    this.remove(node)
    delete(this.nodes, node.Key)
}

Golang

复制

通过以上的方法，我们可以在 Golang 中实现全 O(1) 的数据结构，适用于解决 LeetCode 中的相关问题。