leetcode

type DoublyNode ¶

type DoublyNode struct {
	Val  int
	Next *DoublyNode
	Prev *DoublyNode
}

type LRUCache ¶

type LRUCache struct {
	Capacity int
	Data     map[int]int
	// contains filtered or unexported fields
}

146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Runtime: 1053 ms, faster than 28.52% of Go online submissions for LRU Cache. Memory Usage: 73.6 MB, less than 75.90% of Go online submissions for LRU Cache.

func Constructor(capacity int) LRUCache

func (this *LRUCache) Get(key int) int

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

type LRUQueue ¶

type LRUQueue struct {
	Head *DoublyNode
	Tail *DoublyNode
	// contains filtered or unexported fields
}

func NewLRUQueue() *LRUQueue

func (q *LRUQueue) Flush(val int)

func (q *LRUQueue) Pop() (val int, ok bool)

type ListNode ¶

type ListNode = structure.ListNode

type Node ¶

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

138. Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list. For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y. Return the head of the copied linked list. The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where: * val: an integer representing Node.val * random_index: the index of the node (range from 0 to n-1) that the random pointer points to, * or null if it does not point to any node. Your code will only be given the head of the original linked list.

Runtime: 0 ms, faster than 100.00% of Go online submissions for Copy List with Random Pointer. Memory Usage: 3.7 MB, less than 13.85% of Go online submissions for Copy List with Random Pointer.

type TreeNode ¶

type TreeNode = structure.TreeNode

type Trie ¶

type Trie struct {
	// contains filtered or unexported fields
}

func Constructor3() Trie

func (this *Trie) Insert(word string)

func (this *Trie) Search(word string) bool

func (this *Trie) StartsWith(prefix string) bool

type TrieNode ¶

type TrieNode struct {
	// contains filtered or unexported fields
}

208. Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Runtime: 57 ms, faster than 94.05% of Go online submissions for Implement Trie (Prefix Tree). Memory Usage: 18.6 MB, less than 27.50% of Go online submissions for Implement Trie (Prefix Tree).

func NewTrieNode() *TrieNode

func (this *TrieNode) ContainsKey(ch byte) bool

func (this *TrieNode) Get(ch byte) *TrieNode

func (this *TrieNode) IsEnd() bool

func (this *TrieNode) Put(ch byte, node *TrieNode)

func (this *TrieNode) SetEnd()