纪念与杰哥的第一次coding~

题目链接

要熟悉双向链表的各种操作,哈希表,LRU的简单原理理解。

list

List ——一种序列化容器, 内部实现了双向链表,下面为List 的几个常见操作。

  1. begin()end() ,返回对应位置的迭代器iterator。

  2. push_back() push_front() , 向列表插入一个元素, 还有 emplace_back()emplace_front()

  3. splice()

    C ++ 列表拼接函数用于将元素从列表 y 转移到指定位置的列表容器中,这导致两个列表的大小都发生改变。

    • void splice(iterator pos, list& y);将整个y列表转移到指定列表的对应位置。

      1
      2
      3
      4
      5
      6
      7
      list<int> li={1,2,3,4};
      list<int> li1={5,6,7,8};
      list<int>::iterator itr=li.begin();
      li.splice(itr,li1);
      for(list<int>::iterator itr=li.begin();itr!=li.end();++itr)
      std::cout << *itr <<" ";
      output: 5 6 7 8 1 2 3 4
    • void splice(iterator pos, list& y, iterator pos1); 将y列表对应位置特定元素转移

      1
      2
      3
      4
      5
      6
      7
      8
      9
      list<int> li={9,11,12,13};
      list<int> li1={10,6,7,8};
      list<int>::iterator itr=li.begin();
      list<int>::iterator itr1=li1.begin();
      ++itr;
      li.splice(itr,li1,itr1);
      for(list<int>::iterator itr=li.begin();itr!=li.end();++itr)
      std::cout << *itr <<" ";
      output: 9 10 11 12 13
    • void splice(iterator pos, list& y, iterator first, iterator last);, 将y列表对应区间转移

      1
      2
      3
      4
      5
      6
      7
      8
      9
      list<string> li={"programming language"};
      list<string> li1={"java","is","a","language"};
      list<string>::iterator itr=li.begin();
      list<string>::iterator itr1=li1.begin();
      advance(itr1,3);
      li.splice(itr,li1,li1.begin(),itr1);
      for(list<string>::iterator itr=li.begin();itr!=li.end();++itr)
      std::cout << *itr <<" ";
      output:java is a programming language

unordered_map

unordered_map, 无序map容器, unordered_mapmap 仅有一点不同,即 map 中存储的数据是有序的,而 unordered_map 是无序的。

  1. iterator find( const Key& key ); , 查找以 key 为键的键值对,如果找到,则返回一个指向该键值对的正向迭代器;反之,则返回一个指向容器中最后一个键值对之后位置的迭代器end()。
  2. size_type erase( const Key& key ); Removes the element (if one exists) with the key equivalent to key.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class LRUCache {
public:
LRUCache(int capacity):_capacity(capacity){}
int get(int key){
auto it = _table.find(key);
int res = -1;
if(it!=_table.end()){
_lru.splice(_lru.begin(),_lru,it->second);
res = it->second->second;
}
return res;
}
void put(int key, int value) {
auto it = _table.find(key);
if(it!=_table.end()){ // find it
_lru.splice(_lru.begin(), _lru, it->second);
it->second->second=value;
}else{ // not find, insert first
_lru.emplace_front(std::make_pair(key,value));
_table[key] = _lru.begin();
if(_table.size()>_capacity){
_table.erase(_lru.back().first);
_lru.pop_back();
}
}
}
private:
int _capacity;
std::list<std::pair<int,int>> _lru;
std::unordered_map<int,std::list<std::pair<int,int>>::iterator> _table;
};
/**
* 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);
*/

reference

  1. https://en.cppreference.com/
  2. https://www.geeksforgeeks.org/list-splice-function-in-c-stl/