门户网站开发工具,高性能标准网站建设进阶指南 pdf,我的百度账号,网页游戏平台返利143.环形链表ii
快慢指针 至于入环点的计算 设链表中环外部分的长度为 a。slow 指针进入环后#xff0c;又走了 b 的距离与 fast 相遇。此时#xff0c;fast 指针已经走完了环的 n 圈#xff0c;因此它走过的总距离为 an(bc)ba(n1)bnc。 任意时刻#xff0c;fast 指针走过…143.环形链表ii
快慢指针 至于入环点的计算 设链表中环外部分的长度为 a。slow 指针进入环后又走了 b 的距离与 fast 相遇。此时fast 指针已经走完了环的 n 圈因此它走过的总距离为 an(bc)ba(n1)bnc。 任意时刻fast 指针走过的距离都为 slow 指针的 2 倍。因此有 a(n1)bnc2(ab)⟹ac(n−1)(bc) 因此 从相遇点到入环点的距离加上 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 k0, int v0): key(k), value(v){}
}需要实现get_node()函数将指定值的node找到从原位置删除放到链表的开头哨兵节点后
void remove(node* x){x-prev-nextx-next;x-next-prevx-prev;}void push_front(node* x){x-prev dummy;x-next dummy-next;x-prev-nextx;x-next-prevx;}node* get_node(int key){auto it key_to_node.find(key);if(itkey_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 k0, int v0): key(k), value(v){}
};
class LRUCache {
private:int capacity;node *dummy;unordered_mapint,node* key_to_node;void remove(node* x){x-prev-nextx-next;x-next-prevx-prev;}void push_front(node* x){x-prev dummy;x-next dummy-next;x-prev-nextx;x-next-prevx;}node* get_node(int key){auto it key_to_node.find(key);if(itkey_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-prevdummy;dummy-nextdummy;}int get(int key) {auto nodeget_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_nodedummy-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);*/
