首页 > 编程语言 >四种语言刷算法之LRU 缓存

四种语言刷算法之LRU 缓存

时间:2023-06-30 22:22:36浏览次数:47  
标签:tmp 缓存 self tail 算法 right LRU key left

力扣146. LRU 缓存

1、C

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} LRUCache;

LRUCache* usr = NULL;
int size = 0;

LRUCache* lRUCacheCreate(int capacity) {
    size = capacity;
    return usr;
}

int lRUCacheGet(LRUCache* obj, int key) {
    LRUCache *tmp = NULL;
    HASH_FIND_INT(usr,&key,tmp);
    if(tmp){
        HASH_DEL(usr,tmp);
        HASH_ADD_INT(usr,key,tmp);
        return tmp->val;
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    LRUCache *tmp = NULL;
    HASH_FIND_INT(usr,&key,tmp);
    if(tmp){
        HASH_DEL(usr,tmp);
        tmp->val = value;
        HASH_ADD_INT(usr,key,tmp);
    }
    else{
        int count = HASH_COUNT(usr);
        LRUCache* tmp,*next;
        if(size==count){
            HASH_ITER(hh,usr,tmp,next){
                HASH_DEL(usr,tmp);
                free(tmp);
                break;
            }
        }
        LRUCache* newtmp = (LRUCache*)malloc(sizeof(LRUCache));
        newtmp->key = key;
        newtmp->val =value;
        HASH_ADD_INT(usr,key,newtmp);
    }
}

void lRUCacheFree(LRUCache* obj) {
    LRUCache* tmp,*next;
    HASH_ITER(hh,usr,tmp,next){
                HASH_DEL(usr,tmp);
                free(tmp);
            }
}

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/

2、C++

class LRUCache {
public:
    struct Node{
        int key;
        int val;
        Node* left,*right;
        Node():key(0), val(0), left(NULL), right(NULL) {}
    };
    Node* head = NULL;
    Node* tail = NULL;
    unordered_map<int,Node*> hash;
    int n = 0;

    LRUCache(int capacity) {
        n = capacity;
        head = new Node();
        tail = new Node();
        head->right = tail;
        tail->left = head;
    }
    
    int get(int key) {
        if(hash.count(key)){
            hash[key]->right->left = hash[key]->left;
            hash[key]->left->right = hash[key]->right;
            hash[key]->left = tail->left;
            tail->left->right = hash[key];
            hash[key]->right = tail;
            tail->left = hash[key];  
            return hash[key]->val;
        }
        return -1;
    }
 
    void put(int key, int value) {
        if(hash.count(key)){
            hash[key]->right->left = hash[key]->left;
            hash[key]->left->right = hash[key]->right;
            hash[key]->val = value;
            hash[key]->left = tail->left;
            tail->left->right = hash[key];
            hash[key]->right = tail;
            tail->left = hash[key]; 
        }
        else{
            if(hash.size()==n){
                Node * tmp = head->right;
                tmp->right->left = tmp->left;
                tmp->left->right = tmp->right;
                hash.erase(tmp->key);
                delete tmp;
            }
            Node *tempNode = new Node();
            tempNode->val = value;
            tempNode->key = key;
            tempNode->left = tail->left;
            tail->left->right = tempNode;
            tempNode->right = tail;
            tail->left = tempNode;
            hash[key] = tempNode;
            
        }
    }
};
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

3、JAVA

class LRUCache {
    class Node{
        int key;
        int val;
        Node left;
        Node right;
        Node(){
            key = -1;
            val = -1;
            left = null;
            right = null;
        }
    }
    int n = 0;
    Node head = null;
    Node tail = null;
    
    Map<Integer,Node> map = new HashMap<Integer,Node>();

    public LRUCache(int capacity) {
        n = capacity;
        head = new Node();
        tail = new Node();
        head.right = tail;
        tail.left = head;
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            Node tmp = map.get(key);
            tmp.left.right = tmp.right;
            tmp.right.left = tmp.left;
            tmp.left = tail.left;
            tmp.left.right = tmp;
            tail.left = tmp;
            tmp.right = tail;
           return tmp.val; 
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node tmp = map.get(key);
            tmp.left.right = tmp.right;
            tmp.right.left = tmp.left;
            map.get(key).val = value;
            tmp.left = tail.left;
            tmp.left.right = tmp;
            tail.left = tmp;
            tmp.right = tail; 
        }
        else{
            if(n==map.size()){
                Node tmp = head.right;
                tmp.left.right = tmp.right;
                tmp.right.left = tmp.left;
                map.remove(tmp.key);
            }
            Node tmp = new Node();
            tmp.key = key;
            tmp.val = value;
            map.put(key,tmp);
            tmp.left = tail.left;
            tmp.left.right = tmp;
            tmp.right = tail; 
            tail.left = tmp;
        }
    }
}
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

4、Python

class Node(object):
    def __init__(self,key,value,left=None,right=None):
        self.key = key
        self.val = value
        self.left = left
        self.right = right

class LRUCache(object):


    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.m = {}
        self.n = capacity
        self.head = Node(-1,-1)
        self.tail = Node(-1,-1)
        self.head.right = self.tail
        self.tail.left = self.head


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.m:
            tmp = self.m[key]
            tmp.left.right = tmp.right
            tmp.right.left = tmp.left
            tmp.left = self.tail.left
            self.tail.left.right = tmp
            tmp.right = self.tail
            self.tail.left = tmp
            return self.m[key].val
        return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.m:
            tmp = self.m[key]
            tmp.left.right = tmp.right
            tmp.right.left = tmp.left
            tmp.val = value
            tmp.left = self.tail.left
            self.tail.left.right = tmp
            tmp.right = self.tail
            self.tail.left = tmp
        else:
            if self.n==len(self.m):
                tmp = self.head.right
                tmp.left.right = tmp.right
                tmp.right.left = tmp.left
                del self.m[tmp.key]
            tmp = Node(key,value)
            tmp.left = self.tail.left
            self.tail.left.right = tmp
            tmp.right = self.tail
            self.tail.left = tmp
            self.m[key] = tmp

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

标签:tmp,缓存,self,tail,算法,right,LRU,key,left
From: https://www.cnblogs.com/cmkbk/p/17393408.html

相关文章

  • 万字长文解析最常见的数据库恢复算法: ARIES
    万字长文解析最常见的数据库恢复算法:ARIES首发地址:https://mp.weixin.qq.com/s/Kc13g8OHK1h_f7eMlnl4AwIntroduction上图中为基于WAL的数据库的一种可能的架构情况。其中,In-MemoryData为数据库数据在内存中的组织形式,可以是B树,也可以是hashtable或者其他可能的......
  • PID 的搜索算法(PSA)附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 【基础算法】八大排序算法:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序(快排)
    ✔️前言......
  • 数据结构和算法的关系
    1.数据结构是一门研究组织数据方式的学科,有了编程呢个语言也就有了数据结构,学好数据结构可以编写出更加漂亮,更加有效率的代码2.要学好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决3.程序=数据结构+算法4.数据结构是算法的基础,换言之,要学好算法,需要把数据结构学......
  • 数据结构与算法
    数据结构和算法的重要性:1.算法是程序的灵魂,优秀的程序可以在海量数据计算时,依然保持高速计算。2.一般来讲,程序会使用了内存计算框架(比如Spark)和缓存技术(比如Redis等)来优化程序,再深入的思考一下,这些计算框架和缓存技术,他的核心功能是哪个部分呢?3.拿实际工作经历来说,在Unix下开发......
  • JavaScript aglo 算法 时间复杂度
    https://www.bigocheatsheet.com/https://www.hello-algo.com/chapter_preface/about_the_book/ gpt的回答好的,下面给出这些算法的JavaScript例子,并给出它们的时间复杂度分析:O(1)-常数时间复杂度:javascriptCopyCodefunctionconstantTimeAlgorithm(n){return2+......
  • C#实现所有经典排序算法
    C#实现所有经典排序算法//选择排序classSelectionSorter{privateintmin;publicvoidSort(int[]arr){for(inti=0;i<arr.Length-1;++i){min=i;for(intj=i+1;j<......
  • 保龄球Split算法
    需求:剩下两个或两个以上的球瓶它们之间没有球瓶;例如:7-9或者3-10剩下两个或两个以上的球瓶,他们前面的球瓶被击倒,例如:5-6保龄球位置信息如下图: privateintSplitBall(stringpositionStr){//第一个球必须倒并且未倒的球大于1个......
  • 一种基于DeltaE(CIE 1976)的找色算法
    //QuickFinder.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。//#include<iostream>#define_USE_MATH_DEFINES#include<cmath>#include<ctime>unsignedcharbuf[1080][1920][3];constfloatparam_13=1.0f/3.0f;constfloatparam_1......
  • 深入学习 JVM 算法 - 引用计数法
    博主介绍:✌博主从事应用安全和大数据领域,有8年研发经验,5年面试官经验,Java技术专家✌......