In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-01-19 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Internet Technology >
Share
Shulou(Shulou.com)06/01 Report--
This article mainly shows you "sample analysis of LRU caching mechanism in leetcode", which is easy to understand and well-organized. I hope it can help you solve your doubts. Let the editor lead you to study and learn the article "sample analysis of LRU caching mechanism in leetcode".
Design and implement a LRU (least recently used) caching mechanism. It should support the following operations: get data get and write data put.
Get data get (key)-if the key (key) exists in the cache, the value of the key (always positive) is obtained, otherwise-1 is returned.
Write data put (key, value)-if the key does not exist, its data value is written. When the cache capacity reaches the limit, it should delete the least recently used data values before writing new data, leaving room for new data values.
Advanced:
Can you do these two operations within O (1) time complexity?
Example:
LRUCache cache = new LRUCache (2 / * cache capacity * /)
Cache.put (1,1); cache.put (2,2); cache.get (1); / return 1cache.put (3,3); / / this operation will invalidate key 2 cache.get (2); / / return-1 (not found) cache.put (4,4); / / this operation will invalidate key 1 cache.get (1) / / return-1 (not found) cache.get (3); / return 3cache.get (4); / / return 4
Ideas for solving the problem:
1, store and find
Seeing the title requires us to implement a data structure that can store data in the form of key-value, and can record the recently accessed key value. The first thing that comes to mind is to use a dictionary to store the key-value structure, so the time complexity of the search operation is O (1) O (1).
But because the dictionary itself is unordered, we also need a queue-like structure to record the order of visits, which needs to support the following operations:
Add an item at the end
Remove the front-end item
Move an item in the queue to the end
First consider the list structure.
2the realization of LRU
Using two-way linked list to realize
A feature of the two-way linked list is that its linked list is two-way. We define the head node and tail node, and then use first-in, first-out (FIFO), and the recently placed data will be the first to be obtained. It mainly involves adding, accessing, modifying and deleting operations. The first is to add, if it is a new element, put it directly above the chain header, and the other elements move down in order; if accessed, the one at the head node can be ignored, and if it is in the middle position or tail, the data should be moved to the head node; the same is true for the modification operation: after modifying the original value, the data is moved to the head; if deleted, the other elements are moved sequentially
Type LRUCache struct {capacity int len int hashMap map [int] * Node head * Node tail * Node}
Type Node struct {Prev * Node Next * Node Val int Key int}
Func Constructor (capacity int) LRUCache {m:=make (map [int] * Node) lru:= LRUCache {capacity:capacity,hashMap:m,head:&Node {}, tail:&Node {}} lru.head.Next=lru.tail lru.tail.Prev=lru.head return lru}
Func (this * LRUCache) Get (key int) int {if v Reynolds okGaneshashMap [key]; ok {v.Prev.Next=v.Next v.Next.Prev=v.Prev n:=this.head.Next this.head.Next=v v.Prev=this.head n.Prev=v v.Next=n return v.Val} return-1}
Func (this * LRUCache) Put (key int, value int) {if v. OKH. HashMap [key]; ok {v.Prev.Next=v.Next v.Next.Prev=v.Prev n:=this.head.Next this.head.Next=v v.Prev=this.head n.Prev=v v.Next=n v.Val=value return} if this.len
Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.
Views: 0
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.