算法合集

type LRUCache struct {
    len int
    capacity int
    cache map[int]*Node
    head, tail *Node
}

type Node struct {
    key, value int
    prev, next *Node
}


func Constructor(capacity int) LRUCache {
    head, tail := &Node{}, &Node{}
    head.next = tail
    tail.prev = head
    return LRUCache{
        capacity: capacity,
        cache: make(map[int]*Node),
        head: head,
        tail: tail,
    }
}


func (this *LRUCache) Get(key int) int {
    node, ok := this.cache[key]
    if !ok {
        return -1
    }
    deleteNode(node)
    addHead(this.head, node)
    return node.value
}


func (this *LRUCache) Put(key int, value int)  {
    node, ok := this.cache[key]
    if ok {
        node.value = value
        deleteNode(node)
        addHead(this.head, node)
        return
    }
    node = &Node{key:key, value:value}
    if this.len < this.capacity {
        addHead(this.head, node)
        this.cache[key] = node
        this.len++
    } else {
        lastNode := this.tail.prev
        delete(this.cache, lastNode.key)
        deleteNode(lastNode)
        addHead(this.head, node)
        this.cache[key] = node
    }
}

func addHead(head, node *Node) {
    head.next.prev = node
    node.next = head.next
    head.next = node
    node.prev = head
}

func deleteNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func ThreeQuickSort(nums []int, left, right int) {
    if left >= right {
        return
    }

    pivot := nums[rand.Intn(right-left+1)+left]
    
    start := left
    end := right
    i := left

    for i <= end {
        if nums[i] < pivot {
            nums[start], nums[i] = nums[i], nums[start]
            start++
            i++
        } else if  nums[i] == pivot {
            i++
        } else {
            nums[end], nums[i] = nums[i], nums[end]
            end--
        }
    }

    ThreeQuickSort(nums, left, start-1)
    ThreeQuickSort(nums, end+1, right)
}