Skip to content

Latest commit

 

History

History
223 lines (206 loc) · 5.63 KB

容器.md

File metadata and controls

223 lines (206 loc) · 5.63 KB
Raw

容器

heap堆

heap 是一个堆的实现。一个堆正常保证了获取/弹出最大（最小）元素的时间为log n、插入元素的时间为log n

  • 堆的接口实现
// src/container/heap.go
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{}   // remove and return element Len() - 1.
}

heap不是开箱即用的，需要某类型实现heap接口，才能使用heap提供的方法

  • heap提供的方法
// 初始化一个堆
func Init(h Interface){}
// push一个元素倒堆中
func Push(h Interface, x interface{}){}
// pop 堆顶元素
func Pop(h Interface) interface{} {}
// 删除堆中某个元素，时间复杂度 log n
func Remove(h Interface, i int) interface{} {}
// 调整i位置的元素位置（位置I的数据变更后）
func Fix(h Interface, i int){}

list链表

list 实现了一个双向链表，链表不需要实现heap 类似的接口，可以直接使用。

  • 链表的构造 func New() *List()
  • 链表提供的方法
// 返回链表的长度
  func (l *List) Len() int {}
  // 返回链表中的第一个元素
  func (l *List) Front() *Element {}
  // 返回链表中的末尾元素
  func (l *List) Back() *Element {}
  // 移除链表中的某个元素
  func (l *List) Remove(e *Element) interface{} {}
  // 在表头插入值为 v 的元素
  func (l *List) PushFront(v interface{}) *Element {}
  // 在表尾插入值为 v 的元素
  func (l *List) PushBack(v interface{}) *Element {}
  // 在mark之前插入值为v 的元素
  func (l *List) InsertBefore(v interface{}, mark *Element) *Element {}
  // 在mark 之后插入值为 v 的元素
  func (l *List) InsertAfter(v interface{}, mark *Element) *Element {}
  // 移动e某个元素到表头
  func (l *List) MoveToFront(e *Element) {}
  // 移动e到队尾
  func (l *List) MoveToBack(e *Element) {}
  // 移动e到mark之前
  func (l *List) MoveBefore(e, mark *Element) {}
  // 移动e 到mark 之后
  func (l *List) MoveAfter(e, mark *Element) {}
  // 追加到队尾
  func (l *List) PushBackList(other *List) {}
  // 将链表list放在队列前
  func (l *List) PushFrontList(other *List) {}
  • list操作的元素封装在Element中，视为统一的ListNode节点
type Element struct {
    // 元素保管的值
    Value interface{}
    // 内含隐藏或非导出字段
}

通过Element.Value获得值，并提供如下方法

// 返回下一个元素
func (e *Element) Next() *Element {}
// 返回上一个元素
func (e *Element) Prev() *Element {}
  • 一个list遍历的例子
// l 为队列，
for e := l.Front(); e != nil; e = e.Next() {
  //通过 e.Value 做数据访问
}

ring循环队列

container 中的循环列表是采用链表实现的

// 构造一个包含N个元素的循环列表
func New(n int) *Ring {}
// 返回列表下一个元素
func (r *Ring) Next() *Ring {}
// 返回列表上一个元素
func (r *Ring) Prev() *Ring {}
// 移动n个元素 （可以前移，可以后移）
func (r *Ring) Move(n int) *Ring {}
// 把 s 链接到 r 后面。如果s 和r 在一个ring 里面，会把r到s的元素从ring 中删掉
func (r *Ring) Link(s *Ring) *Ring {}
// 删除n个元素 （内部就是ring 移动n个元素，然后调用Link)
func (r *Ring) Unlink(n int) *Ring {}
// 返回Ring 的长度，时间复杂度 n
func (r *Ring) Len() int {}
// 遍历Ring，执行 f 方法 （不建议内部修改ring）
func (r *Ring) Do(f func(interface{})) {}

其他容器

数组

切片

map

sync.Map

  • Load
  • Store
  • Delete

容器的使用之LRU

LRU 算法 (Least Recently Used)，在做缓存置换时用的比较多

type node struct {
	k int
	v int
}

type Lru struct {
	size  int
	m     map[int]*list.Element
	cache *list.List
}

func NewLru(k int) *Lru {
	return &Lru{
		size:  k,
		m:     make(map[int]*list.Element, k*2),
		cache: list.New(),
	}
}

func (l *Lru) Get(k int) interface{} {
	// 判断是否已经有k
	if ele, ok := l.m[k]; ok {
		l.cache.MoveToFront(ele)
		return (ele.Value).(*node).v
	}
	// 有则将值移到列表首位，并返回值
	// 无则返回nil
	return nil
}

func (l *Lru) Set(k, v int) {
	// 判断是否已经有k
	// 有，更新k值，移动到列表首位
	if ele, ok := l.m[k]; ok {
		(ele.Value).(*node).v = v
		l.cache.MoveToFront(ele)
		return
	} else { // 无，插入到列表首位，更新m
		e := l.cache.PushFront(&node{k: k, v: v})
		l.m[k] = e
	}

	// 判断是否超过大小，超过则删除列表末尾，更新m
	if l.cache.Len() > l.size {
		delete(l.m, l.cache.Back().Value.(*node).k)
		l.cache.Remove(l.cache.Back())
	}
}

容器使用之heap 最小的K个数

func GetLeastNumbers_Solution( input []int ,  k int ) []int {
    // write code here
    
    result := make([]int, 0)
    if len(input) < k {
        return result
    }
    
    h := &IntHeap{}
    heap.Init(h)
    for _, v := range input {
        heap.Push(h, v)
    }
    
    for i := 0; i < k; i++ {
        v := heap.Pop(h)
        if v == nil {
            break
        }
        result = append(result, v.(int))
    }
    
    
    return result
}

type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}

func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
    return 
}

// Push 和 Pop 会改变 切片，故需要用指针
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
    return
}

func (h *IntHeap) Pop() interface{} {
    if h.Len() == 0 {
        return nil
    } else {
        old := *h
        v := old[old.Len()-1]
        *h = old[:old.Len()-1]
        return v
    }
}