运用你所掌握的数据结构，设计和实现一个LRU (最近最少使用) 缓存机制。
实现LRUCache类：
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存
int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。
void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在O(1)时间复杂度内完成这两种操作？
思路：双向链表+hash
struct HDNode{
int key;
int val;
HDNode*pre,*next;
HDNode():key(0),val(0),pre(nullptr),next(nullptr){}
HDNode(int k,int v,HDNode*p,HDNode*q):key(k),val(v),pre(p),next(q){}
HDNode(int k,int v):key(k),val(v),pre(nullptr),next(nullptr){}
};
class LRUCache {
unordered_map<int,HDNode*>cache;
HDNode*head;
HDNode*tail;
int size;
int cap;
public:
LRUCache(int capacity) {
head=new HDNode();
tail=new HDNode();
//head->pre=tail;
head->next=tail;
//tail->next=head;
tail->pre=head;
cap=capacity;
size=0;
}
int get(int key) {
if(cache.find(key)==cache.end()){
return -1;
}
HDNode*node=cache[key];
removeNode(node);
moveToHead(node);
return node->val;
}
void put(int key, int value) {
//已存在
if(cache.find(key)!=cache.end())
{
HDNode*node=cache[key];
node->val=value;
//修改原node的前后节点
removeNode(node);
//将此节点移动到头部后
moveToHead(node);
}else{
//插入键值
HDNode*node=new HDNode(key,value);
cache[key]=node;
moveToHead(node);
size++;
if(size>cap)
{
HDNode*removed=removeTail();
cache.erase(removed->key);
delete(removed);
--size;
}
}
}
void moveToHead(HDNode*node)
{
node->pre=head;
node->next=head->next;
head->next->pre=node;
head->next=node;
}
void removeNode(HDNode*node)
{
node->pre->next=node->next;
node->next->pre=node->pre;
}
HDNode*removeTail(){
HDNode*node=tail->pre;
node->pre->next=tail;
tail->pre=node->pre;
return 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);
*/
给你链表的头结点head，请将其按升序排列并返回排序后的链表。
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head, ListNode* tail) {
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortList(head, mid), sortList(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
} else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}
};
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。
pop()—— 删除栈顶的元素。
top()—— 获取栈顶元素。
getMin()—— 检索栈中的最小元素。
class MinStack {
stack<int>st1;
stack<int>st2;
public:
/** initialize your data structure here. */
MinStack() {
st2.push(INT_MAX);
}
void push(int x) {
if(x<=st2.top())
st2.push(x);
st1.push(x);
}
void pop() {
if(st1.top()==st2.top())
{
st1.pop();
st2.pop();
}else{
st1.pop();
}
}
int top() {
return st1.top();
}
int getMin() {
return st2.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
