List

List (Double Linked List in C++ STL)

splice(iterator of list1, list2)

copy whole list2 into where iterator points at in list1 and empty list2.

splice(iterator1 of list1, list2, iterator2 of list2)

copy the only element where iterator2 at in list2 into where iterator1 at in list1.

splice(iterator1 of list1, list2, start-iter of list2, end-iter of list2)

copy the all elements in the range of start to end iterators in list2 and put them into where iterator1 at in list1.

remove(key)

vector doesn't have this function.

delete specific value in the list.

erase(key)

delete specific position in the list, usually need to use iterator.

pop_back() & pop_front()

push_back() & push_front()

front() & back()

[Medium] No.146 LRU Cache

Approach1: List

Time Complexity: O(1) both for get and put.

Space Complexity: O(N), where N is the capacity.

class LRUCache { public: int cap; list<int>key_list; //stores only keys unordered_map<int,int>mp; // stores keys and corresponding values. LRUCache(int capacity) { cap = capacity; } int get(int key) { //no this key if(mp.find(key) == mp.end() ) return -1; //have this key else{ key_list.remove(key); key_list.push_back(key); return mp[key]; } } void put(int key, int value) { //have this key, remove it first and then add it if(mp.find(key) != mp.end() ){ mp.erase(key); key_list.remove(key); } //reach the capacity if(key_list.size() == cap){ int temp = key_list.front(); key_list.pop_front(); mp.erase(temp); } mp[key] = value; key_list.push_back(key); } };

Approach2: List + Splice (faster than approach 1)

Time Complexity: O(1) both for get and put.

Space Complexity: O(N), where N is the capacity.

class LRUCache{ public: int m_capacity; //m_map_iter->first: key, m_map_iter->second: list iterator; unordered_map<int, list<pair<int, int>>::iterator> m_map; //m_list_iter->first: key, m_list_iter->second: value; list<pair<int, int>> m_list; LRUCache(int capacity) { m_capacity = capacity; } int get(int key) { auto found_iter = m_map.find(key); //not found if (found_iter == m_map.end()) return -1; //move the node corresponding to key to front //found_iter->second is the iterator points to m_list, and the specific node will //move to m_list.begin() m_list.splice(m_list.begin(), m_list, found_iter->second); //return value of the node return found_iter->second->second; } void put(int key, int value) { auto found_iter = m_map.find(key); //found if (found_iter != m_map.end()) { //move the node corresponding to key to front m_list.splice(m_list.begin(), m_list, found_iter->second); //update value of the node found_iter->second->second = value; return; } if (m_map.size() == m_capacity) { int key_to_del = m_list.back().first; m_list.pop_back(); //remove node in list; m_map.erase(key_to_del); //remove key in map } m_list.push_front({key, value}); //create new node in list m_map[key] = m_list.begin(); //create correspondence between key and node } };

find()

find(deque.begin(),deque.end(),target) == deque.end() means the target doesn't exist in the deque.

[Medium] No.353 Design Snake Game

class SnakeGame { public: list<pair<int,int>> snake; vector<vector<int>> foodie; int food_num = 0; int col = 0; int row = 0; SnakeGame(int width, int height, vector<vector<int>>& food) { this->foodie = food; this->col = width; this->row = height; snake.push_front({0,0}); } int move(string direction) { int curi = snake.front().first; int curj = snake.front().second; int offseti = 0; int offsetj = 0; if(direction == "D") offseti = 1; else if (direction == "U") offseti = -1; else if (direction == "L") offsetj = -1; else if (direction == "R") offsetj = 1; else ; int newi = curi + offseti; int newj = curj + offsetj; //pop back FIRST!!! because when you check if your new step collide on your body //you tail should be move forward already, that's why we should pop tail first pair<int,int> back = snake.back(); snake.pop_back(); // if(newi < 0 || newi >= row || newj < 0 || newj >= col) return -1; // if(find(snake.begin(), snake.end(), pair(newi, newj)) != snake.end()) return -1; //found food, snake body increases by 1 if(foodie.size() > 0 && newi == foodie[0][0] && newj == foodie[0][1]) { snake.push_front({newi, newj}); snake.push_back(back); foodie.erase(foodie.begin()); food_num++; }else { snake.push_front({newi, newj}); } return food_num; } };