# LeetCode First Unique Number

LeetCode First Unique Number

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

• FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
• int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
• void add(int value) insert value to the queue.

Example 1:

Input:
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:


[null,2,null,2,null,3,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2);            // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3);            // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1

Example 2:

Input:
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:


[null,-1,null,null,null,null,null,17]

Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17

Example 3:

Input:
[[[809]],[],[809],[]]
Output:


[null,809,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^8
• 1 <= value <= 10^8
• At most 50000 calls will be made to showFirstUnique and add.

class FirstUnique {
private:
list<int> uniques_;
unordered_map<int, list<int>::iterator> hash;
public:
FirstUnique(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
}
}

int showFirstUnique() {
if (uniques_.empty())return -1;
else return uniques_.front();
}

if (hash.find(value) == hash.end()) {
uniques_.push_back(value);
hash[value] = --uniques_.end();
}
else {
if (hash[value] != uniques_.end()) {
uniques_.erase(hash[value]);
hash[value] = uniques_.end();
}
}
}
};

# LeetCode Design Search Autocomplete System

LeetCode Design Search Autocomplete System Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except ‘#’, you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
3. If less than 3 hot sentences exist, then just return as many as you can.
4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
Your job is to implement the following functions: The constructor function: AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical dataSentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data. Now, the user wants to input a new sentence. The following function will provide the next character the user types: List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.   Example: Operation: AutocompleteSystem([“i love you”, “island”,”ironman”, “i love leetcode”], [5,3,2,2]) The system have already tracked down the following sentences and their corresponding times: "i love you" : 5 times "island" : 3 times "ironman" : 2 times "i love leetcode" : 2 times Now, the user begins another search: Operation: input(‘i’) Output: [“i love you”, “island”,”i love leetcode”] Explanation: There are four sentences that have prefix "i". Among them, “ironman” and “i love leetcode” have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, “i love leetcode” should be in front of “ironman”. Also we only need to output top 3 hot sentences, so “ironman” will be ignored. Operation: input(‘ ‘) Output: [“i love you”,”i love leetcode”] Explanation: There are only two sentences that have prefix "i ". Operation: input(‘a’) Output: [] Explanation: There are no sentences that have prefix "i a". Operation: input(‘#’) Output: [] Explanation: The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.   Note:
1. The input sentence will always start with a letter and end with ‘#’, and only one blank space will exist between two words.
2. The number of complete sentences that to be searched won’t exceed 100. The length of each sentence including those in the historical data won’t exceed 100.
3. Please use double-quote instead of single-quote when you write test cases even for a character input.
4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see herefor more details.

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 Encode and Decode TinyURL

LeetCode Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

# 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())
int ans = stk2.top();
return ans;
} /** Returns whether the queue is empty. */
bool empty() { return stk1.empty() && stk2.empty(); }
};

# LeetCode Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

class MinStack {
private:
stack<int> allStack, minStack;

public: /** initialize your data structure here. */
MinStack() {}
void push(int x)
{
if (minStack.empty()) {
minStack.push(x);
}
else if (x <= minStack.top()) { // 注意是<=而不是<
minStack.push(x);
}
allStack.push(x);
}
void pop()
{
int top = allStack.top();
allStack.pop();
if (top == minStack.top()) {
minStack.pop();
}
}
int top() { return allStack.top(); }
int getMin() { return minStack.top(); }
};

class MinStack {
private:
stack<int> allStack, minStack;
public: /** initialize your data structure here. */
MinStack() {}
void push(int x)
{
if (minStack.empty() || x < minStack.top()) {
minStack.push(x);
}
else {
minStack.push(minStack.top());
}
allStack.push(x);
}
void pop()
{
allStack.pop();
minStack.pop();
}
int top() { return allStack.top(); }
int getMin() { return minStack.top(); }
};