算法-综合

1. LRU 缓存机制(中等)

type LRUCache struct {
    Capacity int
    Map map[int]int
    List []int
}


func Constructor(capacity int) LRUCache {
  return LRUCache{
        Capacity : capacity,
        Map : make(map[int]int, 0),
        List : make([]int, 0),
    }
}

func DelKey(a []int, key int) []int{
    for i := 0; i < len(a); i++ {
		if a[i] == key {
            return append(a[:i], a[i+1:]...)
		}
	}
	return a[1:len(a)]
}

func (this *LRUCache) Get(key int) int {
    if val, ok := this.Map[key]; ok{
        this.List = DelKey(this.List, key)
        this.List = append(this.List, key)
        return val
    }
    return -1
}


func (this *LRUCache) Put(key int, value int)  {

    if _, ok := this.Map[key]; ok{
        this.Map[key] = value
        this.List = DelKey(this.List, key)
        this.List = append(this.List, key)
        return 
    }

    if len(this.Map) >= this.Capacity{
        delKey := this.List[0]      
        this.List = DelKey(this.List, key)
        delete(this.Map, delKey)
    }

    this.Map[key] = value
    this.List = append(this.List, key)
}

2. 顺时针打印矩阵

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 || len(matrix[0]) == 0{
        return []int{}
    }

    res := []int{}
    l := 0
    r := len(matrix[0]) - 1
    t := 0
    b :=  len(matrix) - 1

    for {
        // 左到右
        for i := l ; i <= r; i++ {
            res = append(res, matrix[t][i])
        }
        t++
        if t > b {
           break 
        }

        // 右到下
        for i := t; i <= b; i++ {
            res = append(res, matrix[i][r])
        }

        r--
        if l > r {
            break
        }

        // 下到左
        for i := r; i >= l; i-- {
            res = append(res, matrix[b][i])
        }
        b--
        if t > b {
           break 
        }


        // 左到上
        for i := b; i >= t; i-- {
            res = append(res, matrix[i][l])
        }
        l++
        if l > r {
            break
        }
    }

    return res
}