Documentation ¶
Index ¶
- func BFS(root *TreeNode) []int
- func BooleanPointer(b bool) *bool
- func InitDP(m, n int) [][]int
- func IntMax(a, b int) int
- func IntMin(a, b int) int
- func IntsMax(nums ...int) int
- func IntsMin(nums ...int) int
- func LargestValuesV1(root *TreeNode) []int
- func LargestValuesV2(root *TreeNode) []int
- type BSTIterator
- type BSTIteratorReversed
- type BinaryTrie
- type BinaryTrieNode
- type CBTInserter
- type Container
- type DCLinkedList
- type DCNode
- type DNode
- type DoubleNode
- type Item
- type KthLargest
- type LRUCache
- type LinkedList
- type MagicDictionary
- type MapSum
- type MaxHeap
- type MinIntHeap
- type MovingAverage
- type MyCalendar
- type Node
- type PrefixTree
- type RecentAverage
- type TreeNode
- type Trie
- type TrieNode
- type TrieNodeWithValue
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BooleanPointer ¶
func LargestValuesV1 ¶
---------- 二叉树中每层的最大值 ---------- 使用变量保存当前层和下一层的节点数,这样就能确定当前层是否遍历完成。
func LargestValuesV2 ¶
用两个队列实现,把不同层的节点放入不同的队列中。 queue1 : 存放当前层的节点 queue2 : 存放下一层的节点
Types ¶
type BSTIterator ¶
type BSTIterator struct {
// contains filtered or unexported fields
}
---------- 二叉搜索树迭代器 ----------
func NewBSTIterator ¶
func NewBSTIterator(root *TreeNode) *BSTIterator
NewBSTIterator 输入二叉搜索树的根节点初始化该迭代器
type BSTIteratorReversed ¶
type BSTIteratorReversed struct {
// contains filtered or unexported fields
}
func NewBSTIteratorReversed ¶
func NewBSTIteratorReversed(root *TreeNode) *BSTIteratorReversed
type BinaryTrie ¶
type BinaryTrie struct {
// contains filtered or unexported fields
}
func NewBinaryTrie ¶
func NewBinaryTrie() *BinaryTrie
type BinaryTrieNode ¶
type BinaryTrieNode struct {
// contains filtered or unexported fields
}
func NewBinaryTrieNode ¶
func NewBinaryTrieNode() *BinaryTrieNode
type CBTInserter ¶
type CBTInserter struct {
// contains filtered or unexported fields
}
---------- 在完全二叉树中添加节点 ---------- 完全二叉树中第n层的节点数:2^(n-1)。 按照广度优先的顺序,找出第1个左子树或者右子树为空的节点, 空着的位置就是待插入节点的位置。 效率优化,每次插入节点的时候不需要从根节点开始遍历,记住上面待插入节点的父节点, 然后判断它的左右子树是否已经满,如果没有满直接插入,否则插入广度优先搜索的下一个节点。
func NewCBTInserter ¶
func NewCBTInserter(root *TreeNode) *CBTInserter
func (*CBTInserter) Insert ¶
func (t *CBTInserter) Insert(val int) *TreeNode
func (*CBTInserter) Root ¶
func (t *CBTInserter) Root() *TreeNode
type Container ¶
---------- 插入、删除和随机访问都是 O(1) 的容器 ---------- 使用map作为所用来,key保存值,value保存值在数组中的下标 使用数组来保存实际的数据
func NewContainer ¶
func NewContainer() Container
type DCLinkedList ¶
type DCLinkedList struct {
// contains filtered or unexported fields
}
func NewDCLinkedList ¶
func NewDCLinkedList(value []int) *DCLinkedList
func (*DCLinkedList) AddChild ¶
func (l *DCLinkedList) AddChild(value int, child *DCNode)
func (*DCLinkedList) AddNode ¶
func (l *DCLinkedList) AddNode(value int)
type DCNode ¶
type DCNode struct {
// contains filtered or unexported fields
}
Double Linked List with a chain
type DoubleNode ¶
type DoubleNode struct {
// contains filtered or unexported fields
}
---------- 最近最少使用缓存(LRU) ---------- 如下两个操作的时间复杂度是 O(1):
- get(key)
- put(key,value)
常规的哈希表无法找到最近最少使用的,因此需要稍微改造一下。 把存入的元素按照访问的先后顺序存入链表中。每次访问一个元素, 该元素都被移到链表的尾部。这样,位于链表头部的元素就是最近最少使用的。
- 把节点从原来的位置删除(需要知道节点的前一个链表,因此使用双链表,O(1)的时间复杂度)
- 把节点添加到链表尾部
func NewDoubleNode ¶
func NewDoubleNode(key int, value int) *DoubleNode
type KthLargest ¶
type KthLargest struct {
// contains filtered or unexported fields
}
----------- 数据流的第k大数字 ----------
func NewKthLargest ¶
func NewKthLargest(nums []int, k int) *KthLargest
type LRUCache ¶
type LRUCache struct {
// contains filtered or unexported fields
}
LRUCache (Least Recently Used)
func NewLRUCache ¶
type LinkedList ¶
type LinkedList struct {
// contains filtered or unexported fields
}
func NewLinkList ¶
func NewLinkList(values []int) *LinkedList
func (*LinkedList) AddNode ¶
func (l *LinkedList) AddNode(value int)
type MagicDictionary ¶
type MagicDictionary struct {
// contains filtered or unexported fields
}
---------- 神奇字典 ----------
func NewMagicDictionary ¶
func NewMagicDictionary() *MagicDictionary
type MaxHeap ¶
type MaxHeap []*item
func (*MaxHeap) Less ¶
Less reports whether the element with index i must sort before the element with index j.
If both Less(i, j) and Less(j, i) are false, then the elements at index i and j are considered equal. Sort may place equal elements in any order in the final result, while Stable preserves the original input order of equal elements.
Less must describe a transitive ordering:
- if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
- if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
Note that floating-point comparison (the < operator on float32 or float64 values) is not a transitive ordering when not-a-number (NaN) values are involved. See Float64Slice.Less for a correct implementation for floating-point values.
type MinIntHeap ¶
type MinIntHeap []int
func (*MinIntHeap) Len ¶
func (h *MinIntHeap) Len() int
Len is the number of elements in the collection.
func (*MinIntHeap) Less ¶
func (h *MinIntHeap) Less(i int, j int) bool
Less reports whether the element with index i must sort before the element with index j.
If both Less(i, j) and Less(j, i) are false, then the elements at index i and j are considered equal. Sort may place equal elements in any order in the final result, while Stable preserves the original input order of equal elements.
Less must describe a transitive ordering:
- if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
- if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
Note that floating-point comparison (the < operator on float32 or float64 values) is not a transitive ordering when not-a-number (NaN) values are involved. See Float64Slice.Less for a correct implementation for floating-point values.
func (*MinIntHeap) Pop ¶
func (h *MinIntHeap) Pop() any
func (*MinIntHeap) Push ¶
func (h *MinIntHeap) Push(x any)
func (*MinIntHeap) Swap ¶
func (h *MinIntHeap) Swap(i int, j int)
Swap swaps the elements with indexes i and j.
type MovingAverage ¶
type MovingAverage struct {
// contains filtered or unexported fields
}
func NewMovingAverage ¶
func NewMovingAverage(size int) *MovingAverage
func (*MovingAverage) Capacity ¶
func (m *MovingAverage) Capacity() int
func (*MovingAverage) Next ¶
func (m *MovingAverage) Next(val int) float64
func (*MovingAverage) Size ¶
func (m *MovingAverage) Size() int
type MyCalendar ¶
type MyCalendar struct {
// contains filtered or unexported fields
}
---------- 日程表 ------------
func NewMyCalendar ¶
func NewMyCalendar() *MyCalendar
type PrefixTree ¶
type RecentAverage ¶
type RecentAverage struct {
// contains filtered or unexported fields
}
---------- 最近请求次数 ----------
func RecentCounter ¶
func RecentCounter(size int) *RecentAverage
func (*RecentAverage) Len ¶
func (r *RecentAverage) Len() int
type TreeNode ¶
type TreeNode struct {
// contains filtered or unexported fields
}
func NewTreeNode ¶
type TrieNode ¶
type TrieNode struct {
// contains filtered or unexported fields
}
func NewTrieNode ¶
func NewTrieNode() *TrieNode
type TrieNodeWithValue ¶
type TrieNodeWithValue struct {
// contains filtered or unexported fields
}
---------- 单词之和 ----------
func NewTrieNodeWithValue ¶
func NewTrieNodeWithValue() *TrieNodeWithValue