海南省旅游专业网站发展电子商务缺乏强大的专业产业资源做后盾杭州seo网络推广

目录

1  148. 排序链表

2  23. 合并 K 个升序链表

3  146. LRU 缓存

3.1  解题思路

3.2  详细过程

3.3  完整代码

---

菜鸟做题第三周，语言是 C++

1  148. 排序链表

解题思路：

1. 遍历链表，把每个节点的 val 都存入数组中
2. 用 sort 函数对数组进行排序
3. 遍历链表，更新每个节点的 val

class Solution {
public:ListNode* sortList(ListNode* head) {ListNode * p = head;vector<int> vals;while (p) {vals.push_back(p->val);p = p->next;}sort(vals.begin(), vals.end());p = head;int i = 0;while (p) {p->val = vals[i];p = p->next;++i;}return head;}
};

2  23. 合并 K 个升序链表

解题思路：

1. 遍历所有链表，把每个节点的 val 都存入数组中
2. 用 sort 函数对数组进行排序
3. 构造新的链表，并放入数组中的值

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {vector<int> vals;int n = lists.size();if (n == 0) return nullptr;for (int i = 0; i < n; ++i) {ListNode * p = lists[i];while (p) {vals.push_back(p->val);p = p->next;}}sort(vals.begin(), vals.end());ListNode * dummy = new ListNode(0);ListNode * p = dummy;for (auto &val:vals) {ListNode * t = new ListNode(val);p->next = t;p = t;}return dummy->next;}
};

3  146. LRU 缓存

3.1  解题思路

• 构造双向链表，用于表示某节点最近是否被使用
• 构造哈希表，用于快速定位节点位置

Q：如何表示某节点最近是否被访问？

A：在我的解法中，将最近被使用的节点链在链表尾部。由此，越靠近头部的节点越少被使用。

Q：什么叫被使用？

A：被使用包含两种：最新被插入到链表中的节点、最新被访问的节点。

Q：为什么一定要构造双向链表？

A：哈希表中存储的是节点的地址，帮助我们快速定位。但是定位只能定位到节点本身，而不能定位到节点的前一个节点，因此使用单向链表将无法完成节点的删除。

3.2  详细过程

① 定义双向链表结构体

struct DListNode {int key, value;DListNode * prev, * next;DListNode() : key(0), value(0), prev(nullptr), next(nullptr) {}DListNode(int x, int y) : key(x), value(y), prev(nullptr), next(nullptr) {}
};

照抄力扣定义的结构体即可，只不过多了一个 prev 前向指针。

② 定义变量

int cap = 0, size = 0;
unordered_map<int, DListNode *> hashtable;
DListNode * head, * tail;

• cap 表示缓存的容量，size 表示缓存目前被占用的量
• hashtable 的键是节点的 key，值是节点的地址 DListNode *
• head 和 tail 是虚拟节点，辅助节点的插入和删除

③ 定义函数

void addToTail(int key, int value) {DListNode * node = new DListNode(key, value);hashtable[key] = node;node->next = tail;node->prev = tail->prev;tail->prev->next = node;tail->prev = node;++size;
}void moveToTail(int key) {DListNode * node = hashtable[key];node->prev->next = node->next;node->next->prev = node->prev;--size;addToTail(key, hashtable[key]->value);
}void delHeadNode() {DListNode * node = head->next;node->next->prev = head;head->next = node->next;delete node;
}

• addToTail：是指在链尾插入新的节点
• moveToTail：是指将最近使用到的节点删除，再插入到链尾
• delHeadNode：是指缓存空间不够时，删除头节点

由于在我的解法中 “越靠近头部的节点越少被使用”，所以每次被替换掉的是头节点。

3.3  完整代码

class LRUCache {
public:struct DListNode {int key, value;DListNode * prev, * next;DListNode() : key(0), value(0), prev(nullptr), next(nullptr) {}DListNode(int x, int y) : key(x), value(y), prev(nullptr), next(nullptr) {}};int cap = 0, size = 0;unordered_map<int, DListNode *> hashtable;DListNode * head, * tail;LRUCache(int capacity) {cap = capacity;head = new DListNode();tail = new DListNode();head->next = tail;tail->prev = head;}int get(int key) {if (hashtable.count(key)) {moveToTail(key);return hashtable[key]->value;}return -1;}void put(int key, int value) {if (hashtable.count(key)) {hashtable[key]->value = value;moveToTail(key);} else if (!hashtable.count(key)) {if (size < cap) {addToTail(key, value);} else if (size >= cap) {hashtable.erase(head->next->key);delHeadNode();addToTail(key, value);}}}void addToTail(int key, int value) {DListNode * node = new DListNode(key, value);hashtable[key] = node;node->next = tail;node->prev = tail->prev;tail->prev->next = node;tail->prev = node;++size;}void moveToTail(int key) {DListNode * node = hashtable[key];node->prev->next = node->next;node->next->prev = node->prev;--size;addToTail(key, hashtable[key]->value);}void delHeadNode() {DListNode * node = head->next;node->next->prev = head;head->next = node->next;delete node;}
};