# LeetCode Design Underground System

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

• A customer with id card equal to id, gets in the station stationName at time t.
• A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

• A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation)

• Returns the average time to travel between the startStation and the endStation.
• The average time is computed from all the previous traveling from startStation to endStation that happened directly.
• Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]

Output
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

• There will be at most 20000 operations.
• 1 <= id, t <= 10^6
• All strings consist of uppercase, lowercase English letters and digits.
• 1 <= stationName.length <= 10
• Answers within 10^-5 of the actual value will be accepted as correct.

class UndergroundSystem {
private:
map<string, map<string, pair<int, int>>> system_; // start->end, total time, #travels
map<int, pair<string, int>> starts_; // travel start station
public:
UndergroundSystem() {

}

void checkIn(int id, string stationName, int t) {
starts_[id] = make_pair(stationName, t);
}

void checkOut(int id, string stationName, int t) {
string start_station = starts_[id].first;
int start_time = starts_[id].second;
starts_.erase(id);
if (system_.find(start_station) == system_.end()
|| system_[start_station].find(stationName) == system_[start_station].end()) {
system_[start_station][stationName] = make_pair(0, 0);
}
system_[start_station][stationName].first += (t - start_time);
system_[start_station][stationName].second += 1;
}

double getAverageTime(string startStation, string endStation) {
return system_[startStation][endStation].first / double(system_[startStation][endStation].second);
}
};

# LeetCode Design a Stack With Increment Operation

1381. Design a Stack With Increment Operation

Design a stack which supports the following operations.

Implement the CustomStack class:

• CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
• void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
• int pop() Pops and returns the top of stack or -1 if the stack is empty.
• void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

• 1 <= maxSize <= 1000
• 1 <= x <= 1000
• 1 <= k <= 1000
• 0 <= val <= 100
• At most 1000 calls will be made to each method of incrementpush and pop each separately.

class CustomStack {
private:
vector<int> container;
int msz;
public:
CustomStack(int maxSize) {
msz = maxSize;
}

void push(int x) {
if (container.size() < msz) {
container.push_back(x);
}
}

int pop() {
if (container.size() > 0) {
int val = container[container.size() - 1];
container.pop_back();
return val;
}
else {
return -1;
}
}

void increment(int k, int val) {
for (int i = 0; i < k&&i < container.size(); ++i) {
container[i] += val;
}
}
};

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:
1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.
Example:
Twitter twitter = new Twitter();
// User 1 posts a new tweet (id = 5).
// User 1's news feed should return a list with 1 tweet id -> [5].
// User 1 follows user 2.
// User 2 posts a new tweet (id = 6).
// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
// User 1 unfollows user 2.
// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.


# LeetCode Design Excel Sum Formula

LeetCode Design Excel Sum Formula Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions: Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from ‘A’ to ‘Z’. It represents that the width is the number of characters from ‘A’ to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from ‘A’.   void Set(int row, char column, int val): Change the value at C(row, column) to be val.   int Get(int row, char column): Return the value at C(row, column).   int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, “F7” represents the cell at (7, F). If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.   Example 1:

Excel(3,"C");
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6

Note:
1. You could assume that there won’t be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
2. The test cases are using double-quotes to represent a character.
3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

• Get(int row, char column)，获取坐标为(row,column)的cell的值
• Set(int row, char column, int val)，把坐标为(row,column)的值设置为val
• Sum(int row, char column, List of Strings : numbers)，numbers表示一系列求和公式，把公式计算结果填入坐标(row,column)中，并且当公式中的格子更新时，该公式计算出来的值也要更新。

• 对于get，如果坐标不在formula中，说明该格子是实实在在的值，直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
• 对于set，直接把matrix对应坐标设置为value就好，注意的是，因为set之后就变成了实实在在的值，所以要清空formula中该格子的公式（如果有的话）。
• 对于sum，计算字符串公式的值，把结果填入对应的格子，然后在formula中设置该格子的公式。

# LeetCode LRU Cache

146. LRU Cache

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

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

The cache is initialized with a positive capacity.

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4

1. get(key)，从LRU中获取key对应的value，如果LRU中不存在key，则返回-1
2. put(key,value)，把key和对应的value插入到LRU中，如果LRU满，则要替换掉最近最久没访问的元素

put(key,value)。每当有新<key,value>进入时，如果key已经在cache中，则只需要更新key对应的value，同时，刚访问的元素下次很可能再次访问，所以需要把这个key提到链表的表头（为了不让这个key沉到表尾）。如果key不在cache中，但cache已满，则需要把链表尾部的key对应的数据在cache中删掉，同时也需要在链表中删掉这个尾节点；如果cache不满，则把新key插入到链表表头，同时把<key,value>插入到cache中，且key在链表中的位置是list.begin()。

class LRUCache {
private:
unordered_map<int, pair<int, list<int>::iterator> > cache;
list<int> used;
int _capacity; // 把it节点**剪切**到表头
{
int key = *it;
used.erase(it);
used.push_front(key);
cache[key].second = used.begin();
}
public:
LRUCache(int capacity)
: _capacity(capacity)
{
}
int get(int key)
{
if (cache.find(key) == cache.end())
return -1;
int value = cache[key].first;
return value;
}
void put(int key, int value)
{
if (cache.find(key) != cache.end()) {
cache[key].first = value;
}
else {
if (used.size() == _capacity) {
cache.erase(used.back());
used.pop_back();
}
used.push_front(key);
cache[key] = { value, used.begin() };
}
}
};

头 --> 节 --> 节 --> 节 --> 尾



class LRUCache {
private:
struct Node {
int key, value;
Node *pre, *next;
Node(int k, int v)
: key(k)
, value(v)
, pre(NULL)
, next(NULL){};
};
unordered_map<int, Node*> cache;
int _capacity; // 从原链表中删除节点node（摘下）
void removeFromList(Node* node)
{
node->pre->next = node->next;
node->next->pre = node->pre;
}
// 把节点node放到“表头”（安放）
{
}
// 删除“尾节点”
void removeTail()
{
Node* target = tail->pre;
target->pre->next = target->next;
target->next->pre = target->pre;
delete target;
}

public:
LRUCache(int capacity)
: _capacity(capacity)
{
head = new Node(0, 0); // 辅助头结点
tail = new Node(0, 0); // 辅助尾节点
}
int get(int key)
{
if (cache.find(key) == cache.end())
return -1;
int value = cache[key]->value;
removeFromList(cache[key]);
return value;
}
void put(int key, int value)
{
if (cache.find(key) != cache.end()) {
cache[key]->value = value;
removeFromList(cache[key]);
}
else {
if (cache.size() == _capacity) {
cache.erase(tail->pre->key);
removeTail();
}
Node* node = new Node(key, value);
cache[key] = node;
}
}
};

# LeetCode Design Compressed String Iterator

LeetCode Design Compressed String Iterator Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext. The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string. next() – if the original string still has uncompressed characters, return the next letter; Otherwise return a white space. hasNext() – Judge whether there is any letter needs to be uncompressed. Note: Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details. Example:

StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");
iterator.next(); // return 'L'
iterator.next(); // return 'e'
iterator.next(); // return 'e'
iterator.next(); // return 't'
iterator.next(); // return 'C'
iterator.next(); // return 'o'
iterator.next(); // return 'd'
iterator.hasNext(); // return true
iterator.next(); // return 'e'
iterator.hasNext(); // return false
iterator.next(); // return ' '

# LeetCode Implement Stack using Queues

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• empty() — Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue — which means only push to backpeek/pop from frontsize, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

LeetCode Implement Queue using Stacks正好相反，本题要用队列实现堆栈的效果。 队列是先进先出的，而堆栈是后进先出。如果用队列q保存数据，则要实现堆栈的pop效果时，需要获取到q的队尾元素，可以不断把q的数据从队首弹出，同时压回队尾，重复n-1次，此时队首元素就是原来的队尾元素了。堆栈的top效果和push的实现方法是类似的。 这种题目就是数据不断的倒腾。。。 完整代码如下：

class MyStack {
private:
queue<int> m_q;
public: /** Initialize your data structure here. */
MyStack() {} /** Push element x onto stack. */
void push(int x) { m_q.push(x); } /** Removes the element on top of the stack and returns that element. */
int pop()
{
int sz = m_q.size();
for (int i = 0; i < sz – 1; ++i) {
m_q.push(m_q.front());
m_q.pop();
}
int front = m_q.front();
m_q.pop();
return front;
} /** Get the top element. */
int top()
{
int sz = m_q.size(), front = m_q.front();
for (int i = 0; i < sz; ++i) {
front = m_q.front();
m_q.push(front);
m_q.pop();
}
return front;
} /** Returns whether the stack is empty. */
bool empty() { return m_q.empty(); }
};

class MyStack {
private:
vector<queue<int>> vq_;
int data_queue_id_;
public:
/** Initialize your data structure here. */
MyStack() {
vq_.push_back(queue<int>());
vq_.push_back(queue<int>());
data_queue_id_ = 0;
}

/** Push element x onto stack. */
void push(int x) {
vq_[data_queue_id_].push(x);
}

/** Removes the element on top of the stack and returns that element. */
int pop() {
int another_id = 1 - data_queue_id_;
int last_data = 0;
while (!vq_[data_queue_id_].empty()) {
last_data = vq_[data_queue_id_].front();
vq_[data_queue_id_].pop();
if (!vq_[data_queue_id_].empty()) {
vq_[another_id].push(last_data);
}
}
swap(another_id, data_queue_id_);
return last_data;
}

/** Get the top element. */
int top() {
int another_id = 1 - data_queue_id_;
int last_data = 0;
while (!vq_[data_queue_id_].empty()) {
last_data = vq_[data_queue_id_].front();
vq_[data_queue_id_].pop();
vq_[another_id].push(last_data);
}
swap(another_id, data_queue_id_);
return last_data;
}

/** Returns whether the stack is empty. */
bool empty() {
return vq_[data_queue_id_].empty();
}
};


# LeetCode Implement Queue using Stacks

232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

• You must use only standard operations of a stack — which means only push to toppeek/pop from topsize, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

class MyQueue {
private:
stack<int> stk1, stk2; // 输入来源1,2,3，stk1从栈底到栈顶的顺序是1,2,3，stk2从栈底到栈顶的顺序是3,2,1
public: /** Initialize your data structure here. */
MyQueue() {} /** Push element x to the back of queue. */
void push(int x)
{
while (!stk2.empty()) {
stk1.push(stk2.top());
stk2.pop();
}
stk1.push(x);
} /** Removes the element from in front of queue and returns that element. */
int pop()
{
while (!stk1.empty()) {
stk2.push(stk1.top());
stk1.pop();
}
int top = stk2.top();
stk2.pop();
} /** Get the front element. */
int peek()
{
while (!stk1.empty()) {
stk2.push(stk1.top());
stk1.pop();
}
return stk2.top();
} /** Returns whether the queue is empty. */
bool empty() { return stk1.empty() && stk2.empty(); }
};

class MyQueue {
private:
stack<int> stk1, stk2;
{
while (!stk1.empty()) {
stk2.push(stk1.top());
stk1.pop();
}
}
public: /** Initialize your data structure here. */
MyQueue() {} /** Push element x to the back of queue. */
void push(int x) { stk1.push(x); } /** Removes the element from in front of queue and returns that element. */
int pop()
{
if (stk2.empty())
int ans = stk2.top();
stk2.pop();
return ans;
} /** Get the front element. */
int peek()
{
if (stk2.empty())
};