Data structures
6 min readFeb 4, 2020
Hashtable
641. Design Circular Deque
https://zxi.mytechroad.com/blog/category/data-structure/
From huahua
class MyCircularDeque {
private:
const int k_;
vector<int> q_;
int size_;
int head_;
int tail_;
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k): k_(k), q_(k), size_(0), head_(1), tail_(-1) {}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if (isFull())return false;
head_ = (head_-1+k_)%k_;
q_[head_] = value;
if (size_ == 0) tail_=head_;
size_++;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if(isFull())return false;
tail_ = (tail_+1+k_)%k_;
q_[tail_] = value;
if (size_ == 0) head_ = tail_;
size_++;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if(isEmpty())return false;
head_ = (head_+1+k_)%k_;
size_--;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if(isEmpty())return false;
tail_ = (tail_-1+k_)%k_;
size_--;
return true;
}
/** Get the front item from the deque. */
int getFront() {
if(isEmpty())return -1;
return q_[head_];
}
/** Get the last item from the deque. */
int getRear() {
if(isEmpty())return -1;
return q_[tail_];
}
/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
return size_==0;
}
/** Checks whether the circular deque is full or not. */
bool isFull() {
return size_==k_;
}
};/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/
622. Design Circular Queue
From huahua
http://zxi.mytechroad.com/blog/uncategorized/leetcode-622-design-circular-queue/
deque cheating
// Author: Huahua
// Running time: 20 ms
class MyCircularQueue {
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k): k_(k) {}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if (q_.size() == k_) return false;
q_.push_back(value);
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if (q_.empty()) return false;
q_.pop_front();
return true;
}
/** Get the front item from the queue. */
int Front() {
if (isEmpty()) return -1;
return q_.front();
}
/** Get the last item from the queue. */
int Rear() {
if (isEmpty()) return -1;
return q_.back();
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return q_.empty();
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
return q_.size() == k_;
}
private:
const int k_;
deque<int> q_;
};Non cheating
// Author: Huahua
// Running time: 20 ms
class MyCircularQueue {
private:
const int k_;
int size_;
int tail_;
vector<int> q_;public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k): k_(k),size_(0), tail_(-1), q_(k) {}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if(isFull())return false;
tail_ = (tail_+1+k_)%k_;
q_[tail_] = value;
size_++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if (isEmpty())return false;
//tail_ = (tail_+1+k_)%k_;
size_--;
return true;
}
/** Get the front item from the queue. */
int Front() {
if (isEmpty()) return -1;
return q_[(tail_-size_+1+k_)%k_];
}
/** Get the last item from the queue. */
int Rear() {
if (isEmpty()) return -1;
return q_[tail_];
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return size_==0;
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
return size_ == k_;
}
};
LRU
https://leetcode.com/problems/lru-cache/
// Author: Huahua
class LRUCache {
public:
LRUCache(int capacity) {
capacity_ = capacity;
}
int get(int key) {
const auto it = m_.find(key);
// If key does not exist
if (it == m_.cend()) return -1;
// Move this key to the front of the cache
cache_.splice(cache_.begin(), cache_, it->second);
return it->second->second;
}
void put(int key, int value) {
const auto it = m_.find(key);
// Key already exists
if (it != m_.cend()) {
// Update the value
it->second->second = value;
// Move this entry to the front of the cache
cache_.splice(cache_.begin(), cache_, it->second);
return;
}
// Reached the capacity, remove the oldest entry
if (cache_.size() == capacity_) {
const auto& node = cache_.back();
m_.erase(node.first);
cache_.pop_back();
}
// Insert the entry to the front of the cache and update mapping.
cache_.emplace_front(key, value);
m_[key] = cache_.begin();
}
private:
int capacity_;
list<pair<int,int>> cache_;
unordered_map<int, list<pair<int,int>>::iterator> m_;
};https://leetcode.com/problems/lru-cache/discuss/45976/C++11-code-74ms-Hash-table-+-List
There is a similar example in Java, but I wanted to share my solution using the new C++11 unordered_map and a list. The good thing about lists is that iterators are never invalidated by modifiers (unless erasing the element itself). This way, we can store the iterator to the corresponding LRU queue in the values of the hash map. Since using erase on a list with an iterator takes constant time, all operations of the LRU cache run in constant time.
class LRUCache {
public:
LRUCache(int capacity) : _capacity(capacity) {}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) return -1;
touch(it);
return it->second.first;
}
void set(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) touch(it);
else {
if (cache.size() == _capacity) {
cache.erase(used.back());
used.pop_back();
}
used.push_front(key);
}
cache[key] = { value, used.begin() };
}
private:
typedef list<int> LI;
typedef pair<int, LI::iterator> PII;
typedef unordered_map<int, PII> HIPII;
void touch(HIPII::iterator it) {
int key = it->first;
used.erase(it->second.second);
used.push_front(key);
it->second.second = used.begin();
}
HIPII cache;
LI used;
int _capacity;
};“My solution using 4 functions, 3–4 lines each. Very clear logic.” from below link.
https://leetcode.com/problems/lru-cache/discuss/45976/C++11-code-74ms-Hash-table-+-List/225468
int size;
list<int> lru; // MRU ... LRU
unordered_map<int, list<int>::iterator> mp; // key -> iterator
unordered_map<int, int> kv; // key -> valueLRUCache(int capacity) : size(capacity) {}
int get(int key) {
if (kv.count(key) == 0) return -1;
updateLRU(key);
return kv[key];
}
void put(int key, int value) {
if (kv.size() == size && kv.count(key) == 0)
evict();
updateLRU(key);
kv[key] = value;
}
void updateLRU(int key) {
if (kv.count(key))
lru.erase(mp[key]);
lru.push_front(key);
mp[key] = lru.begin();
}
void evict() {
mp.erase(lru.back());
kv.erase(lru.back());
lru.pop_back();
}
This code is from Huahua
class LRUCache {
private:
int capacity_;
list<pair<int, int>> cache_;
unordered_map<int, list<pair<int, int>>::iterator> m_;
public:
LRUCache(int capacity): capacity_(capacity) {}
int get(int key) {
const auto it = m_.find(key);
//if not find
if(it==m_.cend())return -1;
//if find 1) update list 2) return value
cache_.splice(cache_.begin(), cache_, it->second);
return it->second->second;
}
void put(int key, int value) {
const auto it=m_.find(key);
//if find: update list and update value
if(it != m_.cend()){
it->second->second=value;
cache_.splice(cache_.begin(), cache_, it->second);
//m_[key] = cache_.begin();
return;
}
//if not find
// reach capacity
if(cache_.size()==capacity_){
const auto & node = cache_.back();
m_.erase(node.first);
cache_.pop_back();
}
cache_.emplace_front(key, value);
m_[key] = cache_.begin();
}
};/**
* 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);
*/
LeetCode 460. LFU Cache
LFU
struct CacheNode {
int key;
int value;
int freq;
long tick;
//define the order. Least frequence is smaller. If same frequency, the old will smaller.
bool operator <(const CacheNode & rhs) const {
if(freq<rhs.freq)return true;
if (freq==rhs.freq)return tick<rhs.tick;
return false;
}
};class LFUCache {
private:
long tick_;
int capacity_;
unordered_map<int, CacheNode> m_;
set<CacheNode> cache_;
void touch(CacheNode & node){
cache_.erase(node);//log(capacity)
++node.freq;
node.tick = ++tick_;
cache_.insert(node); //log(capacity)
}
public:
LFUCache(int capacity) : capacity_(capacity), tick_(0) {}
int get(int key) {
auto it=m_.find(key);
//not find
if (it==m_.end())return -1;
int value = it->second.value;
touch(it->second);
return value;
}
void put(int key, int value) {
if (capacity_==0)return;
auto it=m_.find(key);
//key exists. Update the value and set
if(it!=m_.end()){
it->second.value=value;
touch(it->second);
return;
}
//key not exist
//1) reach the capacity
if(capacity_==m_.size()){
const CacheNode& node = *cache_.cbegin();
m_.erase(node.key);
cache_.erase(node);
}
//2) not reach the capacity
CacheNode node{key, value, 1, ++tick_};
m_[key] = node;
cache_.insert(node);
}
};/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
