程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode]LRU Cache有個相關問題,求大神解答

[LeetCode]LRU Cache有個相關問題,求大神解答

編輯:C++入門知識

題目:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

這是我的代碼:

 1 class LRUCache{
 2 public:
 3     int num;
 4     int max;
 5     list<int> latest_key;         //用於保存使用情況,隊頭是最久未使用的,隊尾是最近使用的
 6     unordered_map<int, int> cache;   //用於保存key,value
 7 
 8     LRUCache(int capacity) {
 9         num = 0;
10         max = capacity;
11     }
12 
13     int get(int key) {
14         unordered_map<int, int>::iterator it = cache.find(key);
15         list<int>::iterator iter;
16         if (it == cache.end())  //如果沒有找到key
17             return -1;
18         else            //如果找到了key,就在對應的最近latest隊列裡面修改key的位置,先把key所在的位置刪除,再把key放到隊尾
19         {
20             iter = latest_key.begin();
21             while (*iter != key)
22                 iter++;
23             latest_key.erase(iter);
24             latest_key.push_back(key);
25             return it->second;
26         }
27     }
28 
29     void set(int key, int value) {
30         unordered_map<int, int>::iterator it = cache.find(key);
31         list<int>::iterator iter;
32         if (it != cache.end())  //如果要插入的已經有key存在,就先在優先隊列裡面找到key出現的位置,刪除,再把key插入隊尾
33         {
34             it->second = value;
35             iter = latest_key.begin();
36             while (*iter != key)
37                 iter++;
38             latest_key.erase(iter);
39             latest_key.push_back(key);
40         }
41         else            //如果要插入的不存在
42         {
43             if (num<max)  //如果不超過cache容量,則直接在cahe中插入,再在隊尾添加該key
44             {
45                 num++;
46                 cache.insert(std::pair< int, int >(key, value));
47                 latest_key.push_back(key);
48             }
49             else      //如果cache已經滿了,則根據隊頭元素,在cache刪除對應鍵值,再在隊列中刪除這個隊頭,之後,把新要插入的鍵值插入cache中,把新key插入隊尾
50             {
51                 int latest = latest_key.front();
52                 cache.erase(latest);
53                 latest_key.pop_front();
54                 cache.insert(std::pair< int, int >(key, value));
55                 latest_key.push_back(key);
56             }
57         }
58     }
59 };

  當我把代碼中出現:

1  iter = latest_key.begin();
2  while (*iter != key)
3     iter++; 

  部分替換為:

1 iter=find(latest_key.begin(),latest_key.end(),key);

  就會報錯:

Time Limit Exceeded

Last executed input: 2048,[set(1178,3401),set(903,6060).....

  我大致查了一下find的實現機制,也是遍歷啊,按理說這兩者效率差不多,為什麼替換之後就不能通過?而替換之前能通過,求大神解答!!

  萬分感謝!!!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved