Leetcode刷题笔记--Hot51-60

1--环形链表II

主要思路：

        快慢指针，快指针每次走两步，慢指针每次走一步；

        第一次相遇时，假设慢指针共走了 f 步，则快指针走了 2f 步；

        假设起点到环入口结点的长度为 a（不包括入口结点），环的结点数为 b；快指针比慢指针多走的步数肯定全在环中，则有 2f - f = f = nb；则慢指针共走了 nb 步；

        由于慢指针共走了 nb 步，而起点到环入口结点的步数为 a，则实际慢指针在环内走了 nb - a 步；

        此时让慢指针从起点重新出发走 a 步，每次走 1 步；快指针从相遇的地方出发，每次也走 1 步，快慢指针必然在环入口结点相遇；因此快指针相当于也走了 a 步，恰好与 nb - a 步互补，构成完整圈数的 nb 环；

#include <iostream>
#include <vector>struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == nullptr) return head;ListNode *slow = head;ListNode *fast = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if(fast == slow) break; // 第一次相遇}if(fast == NULL || fast->next == NULL) return NULL; // 没有环// 从头开始走slow = head;while(slow != fast){slow = slow->next;fast = fast->next;}// 第二次相遇就是环的入口return slow;}
};int main(int argc, char *argv[]) {// head = [3, 2, 0, -4], pos = 1ListNode *Node1 = new ListNode(3);ListNode *Node2 = new ListNode(2);ListNode *Node3 = new ListNode(0);ListNode *Node4 = new ListNode(-4);Node1->next = Node2;Node2->next = Node3;Node3->next = Node4;Node4->next = Node2;Solution S1;ListNode* res = S1.detectCycle(Node1);if(res != nullptr) std::cout << res->val << std::endl;else std::cout << "nullptr" << std::endl;return 0;
}

2--LRU缓存

主要思路：

        基于双向链表和哈希表；

        访问元素时，若元素不存在则返回；若元素存在，则将元素记录，并将元素移动到双向链表头部；（确保访问热度最高的元素放在双向链表头部，访问热度最低的元素放在双向链表尾部）；

        插入元素时，若元素不存在：当容量已满时，先移除双向链表尾部的元素，再将新元素插入到双向链表头部；若元素存在，则取出元素并更新元素的值，将更新后的元素插入到双向链表头部；

#include <iostream>
#include <unordered_map>class LRUCache {
public:struct ListNode{ListNode(int key, int val){this->key = key;this->val = val;}ListNode* pre = nullptr;ListNode* next = nullptr;int val = 0;int key = 0;};LRUCache(int capacity) {this->cap = capacity; // 容量head = new ListNode(-1, -1);tail = new ListNode(-1, -1);head->next = tail;tail->pre = head;}int get(int key) {if(hash.count(key) == 0) return -1; // 元素不存在ListNode* ptr = hash[key]; // 取出元素remove(ptr); // 从双向链表中删除元素insert(ptr); // 将元素插入到双向链表头部return ptr->val; // 返回元素的值}void put(int key, int value) {if(hash.count(key) == 0){ // 元素不存在if(hash.size() == cap){ // 容量已满ListNode* ptr = tail->pre;remove(ptr); // 去除尾部节点hash.erase(ptr->key);delete(ptr);}ListNode* new_node = new ListNode(key, value); // 新建节点insert(new_node); // 插入新节点到头部hash[new_node->key] = new_node;return;}else{ // 元素存在ListNode* ptr = hash[key]; // 取出元素ptr->val = value; // 更新元素remove(ptr); // 先删除元素insert(ptr); // 再将元素插入到头部return;}}void remove(ListNode* ptr){// 取出前驱和后驱元素ListNode* a = ptr->pre;ListNode* b = ptr->next;// 更新前驱和后驱元素的指向a->next = b;b->pre = a;ptr->pre = ptr->next = nullptr;}void insert(ListNode* ptr){ListNode* tmp = head->next; // 头指针的下一个元素// 将元素插入到双向链表头部ptr->pre = head;head->next = ptr;ptr->next = tmp;tmp->pre = ptr;}
private:int cap = 0; // 容量std::unordered_map<int, ListNode*> hash; // 哈希表ListNode* head; // 双向链表哨兵头节点ListNode* tail; // 双向链表哨兵尾节点
};int main(int argc, char argv[]){return 0;
}