Golang实现LFU缓存
既然上一篇写了LRU，那这一篇我们就来搞一下LFU吧。LFU，Least Frequently Used，最近最少使用，其核心思想是，“如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小”。本文基于 LeetCode 460. LFU 缓存 进行，解法不是最优，但是实现了Get和Put操作的时间复杂度均为O(1)。这里我们使用一个HashMap实现Get操作的O...
既然上一篇写了LRU，那这一篇我们就来搞一下LFU吧。LFU，Least Frequently Used，最近最少使用，其核心思想是，“如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小”。本文基于 LeetCode 460. LFU 缓存 进行，解法不是最优，但是实现了Get和Put操作的时间复杂度均为O(1)。这里我们使用一个HashMap实现Get操作的O...
LRU，Least Recently Used的缩写，即“最近最少使用”，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。这里，我们基于 LeetCode 146. LRU 缓存 ，使用Golang实现，并使其Get、Put操作的时间复杂度均为O(1)。思路很简单，使用HashMap保存Cache，保证其Get的复杂度为O(1)，使用一个双向链表，保证Put操作维护使用顺序...
介绍trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。说白了，Trie树是一种N叉树，除根节点外，每个节点都保存了这...
介绍二叉查找树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查...
介绍层序遍历，顾名思义，不难理解，就是一层一层地遍历Golang实现此处分为递归实现（DFS，深度优先算法）和迭代实现（BFS，广度优先算法）本文以Leetcode102题为例：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/递归实现（DFS）递归实现需要储存每层的级数实现起来主要分为以下几个步骤递归跳出条...