面试手撕优化

LRU 缓存

 1 /*
 2     每次get一个key有两种情况，要么链表里面没有这个key那么可以直接返回-1，
 3     如果链表里面有这个key，我们需要把查到的这个节点给移到链表头部，
 4     对于put操作，我们直接通过调用get返回结果：
 5     如果返回不是-1，说明链表里面已有key，那么我们的get函数会给他排到链表前面去。
 6     如果返回-1，说明链表里面没有key，那么我们需要插入这个key，分两种情况:
 7     如果容量满了，就删除最后一个节点再把新的key加进来作为链表头结点
 8     否则直接加入当前的key到链表头结点
 9 */
10 class LRUCache {
11 public:
12     int cap;
13     list<int>st;//使用C++自带的双向链表list
14     unordered_map<int,list<int>::iterator>mp;//key需要映射到链表元素的迭代器
15     unordered_map<int,int>mp1;//保存key-value键值对，方便查询元素value
16     LRUCache(int capacity) {
17         cap=capacity;
18     }
19     int get(int key) {
20         if(mp.count(key)){
21             auto it=mp[key];
22             //splice(const_iterator pos, list& other, const_iterator it)表示把结点it移到other链表的pos位置之前
23             st.splice(st.begin(),st,it);
24             return mp1[key];
25         }
26         else return -1;
27     }
28     void put(int key, int value) {
29         if(get(key)!=-1){  
30             mp1[key]=value;
31         }
32         else{
33             if(mp.size()==cap){ //如果容量满了，就删除最后一个再把新的key加进来作为链表头结点
34                 int x=st.back();
35                 mp.erase(x);
36                 st.pop_back();
37                 st.push_front(key);
38                 mp1[key]=value;
39                 auto it=st.begin();
40                 mp[key]=it;
41             }
42             else{  //否则直接加入当前的key到链表头结点
43                 st.push_front(key);
44                 mp1[key]=value;
45                 auto it=st.begin();
46                 mp[key]=it;
47             }
48         }
49     }
50 };

 删除链表的倒数第 N 个结点

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* removeNthFromEnd(ListNode* head, int n) {
14         ListNode *p = head, *q = head, *pre = head;
15         if (!p->next) {
16             delete(head);
17             head = nullptr;
18             return head;
19         }
20         int cnt = 0;
21         while (q) {
22             if (cnt < n) {
23                 cnt++;
24                 q = q->next;
25             }
26             else {
27                 q = q->next;
28                 pre = p;
29                 p = p->next;
30             }
31         }
32         if (pre == p) {
33             p = p->next;
34             delete(head);
35             head = p;
36             return head;
37         }
38         pre->next = p->next;
39         delete(p);
40         return head;
41     }
42 };