leetcode每日一题48

143.环形链表ii

快慢指针
至于入环点的计算

设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n
圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。
任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

因此
从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇

146.LRU缓存

因为get和put都需要快速找到节点，所以使用哈希表，将key映射到链表对应的位置
get和put都是O(1)，所以使用双向链表，同时使用一个哨兵节点，让每个节点的pre和next都不为空
构造双向链表节点类

class node{
public:int key, value;node *prev, *next;node(int k=0, int v=0): key(k), value(v){}
}

需要实现get_node()函数，将指定值的node找到，从原位置删除，放到链表的开头（哨兵节点后）

void remove(node* x){x->prev->next=x->next;x->next->prev=x->prev;}void push_front(node* x){x->prev = dummy;x->next = dummy->next;x->prev->next=x;x->next->prev=x;}node* get_node(int key){auto it = key_to_node.find(key);if(it==key_to_node.end())return nullptr;auto node = it->second;remove(node);push_front(node);return node;}

class node{
public:int key, value;node *prev, *next;node(int k=0, int v=0): key(k), value(v){}
};
class LRUCache {
private:int capacity;node *dummy;unordered_map<int,node*> key_to_node;void remove(node* x){x->prev->next=x->next;x->next->prev=x->prev;}void push_front(node* x){x->prev = dummy;x->next = dummy->next;x->prev->next=x;x->next->prev=x;}node* get_node(int key){auto it = key_to_node.find(key);if(it==key_to_node.end())return nullptr;auto node = it->second;remove(node);push_front(node);return node;}public:LRUCache(int capacity):capacity(capacity),dummy(new node()) {dummy->prev=dummy;dummy->next=dummy;}int get(int key) {auto node=get_node(key);return node?node->value:-1;}void put(int key, int value) {auto node1 = get_node(key);if(node1){node1->value = value;return;}node1 = new node(key,value);key_to_node[key] = node1;push_front(node1);if(key_to_node.size()>capacity){auto back_node=dummy->prev;key_to_node.erase(back_node->key);remove(back_node);delete back_node;}}
};/*** 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);*/