# 剑指 Offer 36. 二叉搜索树与双向链表

class Solution {
private:
void DFS(Node *root) {
if(root == NULL) return;

DFS(root->left);
else pre->right = root;

root->left = pre;
pre = root;
DFS(root->right);
}
public:
Node* treeToDoublyList(Node* root) {

if(root == NULL) return NULL;

DFS(root);

}
};

# 剑指 Offer 06. 从尾到头打印链表

0 <= 链表长度 <= 10000

class Solution {
public:
vector<int> ans;
}
int i = 0, j = ans.size() - 1;
while(i < j) {
swap(ans[i++], ans[j--]);
}
return ans;
}
};

# 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 Queries on a Permutation With Key

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

• In the beginning, you have the permutation P=[1,2,3,...,m].
• For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1]
Explanation: The queries are processed as follow:
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5].
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5].
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5].
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5].
Therefore, the array containing the result is [2,1,2,1].


Example 2:

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]


Example 3:

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]


Constraints:

• 1 <= m <= 10^3
• 1 <= queries.length <= m
• 1 <= queries[i] <= m

class Solution {
public:
vector<int> processQueries(vector<int>& queries, int m) {
list<int> lst;
for (int i = 1; i <= m; ++i)lst.push_back(i);
vector<int> ans;
for (int i = 0; i < queries.size(); ++i) {
int val = queries[i];
int j = 0;
list<int>::iterator it = lst.begin();
while (it != lst.end()) {
if (*it == val) {
ans.push_back(j);
lst.erase(it);
lst.push_front(val);
break;
}
else {
++it;
++j;
}
}
}
return ans;
}
};

# LeetCode Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.


Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.


Note:

• The number of nodes in the given list will be between 1 and 100.

class Solution {
public:
while (fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == NULL)break;
}
return slow;
}
};

# LeetCode Design Log Storage System

LeetCode Design Log Storage System You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers. Design a log storage system to implement the following functions: void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system. int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017. Example 1:

put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note:
1. There will be at most 300 operations of Put or Retrieve.
2. Year ranges from [2000,2017]. Hour ranges from [00,23].
3. Output for Retrieve has no order required.

"2016:00:00:00:00:00"

"2017:12:31:23:59:59"

# 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 Sort List

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4


Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

class Solution {
private:
ListNode* mergeList(ListNode* h1, ListNode* h2)
{
if (!h1)
return h2;
else if (!h2)
return h1;
while (h1 && h2) {
if (h1->val < h2->val) {
h->next = h1;
h1 = h1->next;
}
else {
h->next = h2;
h2 = h2->next;
}
h = h->next;
}
if (h1)
h->next = h1;
else if (h2)
h->next = h2;
}
public:
{
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
ListNode* right = sortList(fast);
return mergeList(left, right);
}
};

class Solution {
public:
while (fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
ListNode *left = sortList(head), *right = sortList(slow);
ListNode *dummy = new ListNode(0);
ListNode *lst = dummy;
while (left != NULL || right != NULL) {
int l = left != NULL ? left->val : INT_MAX;
int r = right != NULL ? right->val : INT_MAX;
if (l < r) {
lst->next = left;
left = left->next;
}
else {
lst->next = right;
right = right->next;
}
lst = lst->next;
}
return dummy->next;
}
};

# LeetCode Reorder List

143. Reorder List

Given a singly linked list LL0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

class Solution {
public:
{
return; // find mid node
while (slow->next != NULL && fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
// reverse [mid,end]
ListNode *par = new ListNode(0), *tail;
while (slow) {
tail = slow->next;
slow->next = par->next;
par->next = slow;
slow = tail;
}
//merge 2 list
par = par->next;
h->next = par;
par = par->next;
}
else {
h = h->next;
h->next = par;
par = par->next;
}
h = h->next;
}
}
};

# LeetCode Copy List with Random Pointer

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]


Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]


Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]


Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.


Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.

class Solution {
public:
{
unordered_map<RandomListNode*, int> hash;
vector<RandomListNode*> array_for_list;
int idx = 0;
while (h1) {
hash[h1] = idx++;
RandomListNode* node = new RandomListNode(h1->label);
array_for_list.push_back(node);
h2->next = node;
h1 = h1->next;
h2 = h2->next;
}
while (h1) {
if (h1->random) {
h2->random = array_for_list[hash[h1->random]];
}
h1 = h1->next;
h2 = h2->next;
}
}
};

class Solution {
public:
{
while (iter) {
RandomListNode* node = new RandomListNode(iter->label);
node->next = iter->next;
iter->next = node;
iter = node->next;
}
while (iter) {
if (iter->random) {
iter->next->random = iter->random->next;
}
iter = iter->next->next;
}
RandomListNode* copy_head = new RandomListNode(0); // dummy
RandomListNode *copy_iter = iter->next, *copy_tail = copy_head;
while (iter) {
copy_tail->next = copy_iter;
copy_tail = copy_tail->next;
iter->next = copy_iter->next;
iter = iter->next;
if (iter) {
copy_iter->next = iter->next;
copy_iter = copy_iter->next;
}
}
}
};

class Solution {
public:

// 拷贝主干节点
while (l1 != NULL) {
Node *cur = new Node(l1->val);
cur->next = l1->next;
l1->next = cur;
l1 = cur->next;
}

//连接random指针
while (l1 != NULL) {
if (l1->random != NULL) {
l1->next->random = l1->random->next;
}
l1 = l1->next->next;
}

//拆分
};