题目
实现一个缓存机制。很多人的写法都是使用HashTable, Map,Dictionary 或者别的工具。
但是我，自己硬核手写了一个可插入删除的AVL树，并且把这道题目给过了
代码实在有点偏长,以后再重构代码。
过程中Wa了很多次，最后一次的AC的感觉，真是找到以前比赛时候的感觉。
代码语言：javascript复制struct Node
{
int key;
Node* next;
Node* pre;
Node(int key)
{
this->key=key;
next=NULL;
pre=NULL;
}
};
struct Tree
{
Tree* leftChild;
Tree* rightChild;
Tree* father;
Node* x;
int key;
int value;
int leftHeight;
int rightHeight;
};
void LeftSpin(Tree*& root)
{
Tree* father = root->father;
Tree* temp = root;
if(root->rightChild==NULL)
return;
Tree* temp2 = root->rightChild->leftChild;
root = temp->rightChild;
root->leftChild = temp;
root->father = father;
temp->father = root;
temp->rightChild = temp2;
if(temp2!=NULL)
temp2->father = temp;
root->leftChild->rightHeight = root->leftChild->rightChild==NULL?0:max(root->leftChild->rightChild->leftHeight,root->leftChild->rightChild->rightHeight) 1;
root->leftHeight = max(root->leftChild->leftHeight,root->leftChild->rightHeight) 1;
}
void RightSpin(Tree*& root)
{
Tree* father = root->father;
Tree* temp = root;
if(root->leftChild==NULL)
return;
Tree* temp2 = root->leftChild->rightChild;
root = temp->leftChild;
root->rightChild = temp;
root->father = father;
temp->father = root;
temp->leftChild = temp2;
if(temp2!=NULL)
temp2->father = temp;
root->rightChild->leftHeight =root->rightChild->leftChild==NULL?0:max(root->rightChild->leftChild->leftHeight,root->rightChild->leftChild->rightHeight) 1;
root->rightHeight = max(root->rightChild->leftHeight,root->rightChild->rightHeight) 1;
}
void LeftRightSpin(Tree*& root)
{
LeftSpin(root->leftChild);
RightSpin(root);
}
void RightLeftSpin(Tree*& root)
{
RightSpin(root->rightChild);
LeftSpin(root);
}
void Rebalance(Tree*& root)
{
if(root->leftHeight > root->rightHeight 1)
{
if(root->leftChild->leftHeight < root->leftChild->rightHeight)
{
LeftRightSpin(root);
}
else
RightSpin(root);
}
else if(root->leftHeight<root->rightHeight-1)
{
if(root->rightChild->rightHeight<root->rightChild->leftHeight)
{
RightLeftSpin(root);
}
else
LeftSpin(root);
}
}
void Insert(Tree*& father, Tree*& root,int key,int value,Node*& x)
{
if(root==NULL)
{
root = new Tree;
root->leftChild=NULL;
root->rightChild=NULL;
root->key = key;
root->value = value;
root->leftHeight = 0;
root->rightHeight = 0;
root->father = father;
root->x =x;
return;
}
if(key == root->key)
{
root->value = value;
return;
}
if(key < root->key)
{
Insert(root,root->leftChild,key,value,x);
root->leftHeight = max(root->leftChild->leftHeight,root->leftChild->rightHeight) 1;
Rebalance(root);
}
else if(key > root->key){
Insert(root,root->rightChild, key,value,x);
root->rightHeight = max(root->rightChild->leftHeight,root->rightChild->rightHeight) 1;
Rebalance(root);
}
}
int Get(Tree* root,int key)
{
if(root==NULL)
return -1;
if(key<root->key&&root->leftChild!=NULL)
{
return Get(root->leftChild,key);
}
if(key>root->key&&root->rightChild!=NULL)
{
return Get(root->rightChild,key);
}
if(key==root->key)
{
return root->value;
}
return -1;
}
void dis(int& value)
{
if(value==0)
return;
if(value>0)
value--;
}
Node* GetNode(Tree* root,int key)
{
if(key<root->key&&root->leftChild!=NULL)
{
return GetNode(root->leftChild,key);
}
if(key>root->key&&root->rightChild!=NULL)
{
return GetNode(root->rightChild,key);
}
if(key==root->key)
{
return root->x;
}
return NULL;
}
void DeleteNode(Tree*& root,int tag)
{
if(root->leftChild!=NULL)
{
if(tag==0)
{
if(root->father == root)
root->leftChild = NULL;
else
{
root->father->leftChild = root->leftChild;
root->father = root->father->father;
//root->father->leftChild->father = root->father;
}
}
else if(tag==1)
{
if(root->father == root)
root->rightChild = NULL;
else
{
root->father->rightChild = root->leftChild;
root->father = root->father->father;
//root->father->rightChild->father = root->father;
}
}
}
else if(root->rightChild!=NULL)
{
if(tag==0)
{
if(root->father == root)
{
root->leftChild = NULL;
}
else
{
root->father->leftChild = root->rightChild;
root->father = root->father->father;
// root->father->leftChild->father = root->father;
}
}
else if(tag==1)
{
if(root->father == root)
{
root->rightChild = NULL;
}
else
{
root->father->rightChild = root->rightChild;
root->father = root->father->father;
//root->father->rightChild->father = root->father;
}
}
}
else
{
if(tag==0)
{
if(root->father == root)
root = NULL;
else
root->father->leftChild=NULL;
}
else if(tag==1)
{
if(root->father == root)
root=NULL;
else
root->father->rightChild=NULL;
}
}
}
void LeftScoper(Tree*& source, Tree*& root,int tag)
{
if(root->leftChild!=NULL)
{
LeftScoper(source,root->leftChild,0);
if(root->leftChild!=NULL)
root->leftHeight = max(root->leftChild->leftHeight,root->leftChild->rightHeight) 1;
else
dis(root->leftHeight);
Rebalance(root);
}
else
{
source->key = root->key;
source->value = root->value;
source->x = root->x;
DeleteNode(root,tag);
}
}
void RightScoper(Tree*& source, Tree*& root,int tag)
{
if(root->rightChild!=NULL)
{
RightScoper(source,root->rightChild,1);
if(root->rightChild!=NULL)
root->rightHeight = max(root->rightChild->leftHeight,root->rightChild->rightHeight) 1;
else
dis(root->rightHeight);
Rebalance(root);
}
else
{
source->key = root->key;
source->value = root->value;
source->x = root->x;
DeleteNode(root, tag);
}
}
void Remove(Tree*& root,int key,int tag)
{
if(root==NULL)
return;
if(key == root->key)
{
if(root->leftChild==NULL&&root->rightChild==NULL)
{
DeleteNode(root,tag);
}
else
{
if(root->rightChild!=NULL)
{
LeftScoper(root,root->rightChild,1);
if(root->rightChild!=NULL)
root->rightHeight = max(root->rightChild->leftHeight,root->rightChild->rightHeight) 1;
else
dis(root->rightHeight);
Rebalance(root);
}
else if(root->leftChild!=NULL)
{
RightScoper(root,root->leftChild,0);
if(root->leftChild!=NULL)
root->leftHeight = max(root->leftChild->leftHeight,root->leftChild->rightHeight) 1;
else
dis(root->leftHeight);
Rebalance(root);
}
}
return;
}
if(key<root->key)
{
Remove(root->leftChild,key,0);
if(root->leftChild!=NULL)
root->leftHeight = max(root->leftChild->leftHeight,root->leftChild->rightHeight) 1;
else
dis(root->leftHeight);
Rebalance(root);
}
if(key>root->key)
{
Remove(root->rightChild,key,1);
if(root->rightChild!=NULL)
root->rightHeight = max(root->rightChild->leftHeight,root->rightChild->rightHeight) 1;
else
dis(root->rightHeight);
Rebalance(root);
}
}
class LRUCache {
public:
Tree* root;
Tree* term;
int num;
int num2=0;
Node* head;
Node* rear;
LRUCache(int capacity) {
term = NULL;
root=NULL;
head=NULL;
rear=NULL;
num=capacity;
num2=0;
}
int get(int key) {
int x = Get(root,key);
if(x==-1)
return x;
Node* temp = GetNode(root,key);
if(temp == rear)
{
return x;
}
if(temp->pre!=NULL)
{
temp->pre->next = temp->next;
temp->next->pre = temp->pre;
}
else
{
head = temp->next;
head->pre =NULL;
}
temp->next=NULL;
rear->next = temp;
temp->pre = rear;
rear = rear->next;
return x;
}
void put(int key, int value) {
int x = Get(root,key);
if(x!=-1)
{
Node* temp2;
Insert(root ,root,key,value,temp2);
Node* temp3 = GetNode(root,key);
if(temp3 == rear)
{
return;
}
if(temp3->pre!=NULL)
{
temp3->pre->next = temp3->next;
temp3->next->pre = temp3->pre;
}
else
{
head = temp3->next;
head->pre =NULL;
}
temp3->next=NULL;
rear->next = temp3;
temp3->pre = rear;
rear = rear->next;
return;
}
if(num2==num)
{
Remove(root,head->key,0);
head = head->next;
if(head!=NULL)
head->pre =NULL;
num2--;
}
Node* temp =new Node(key);
if(head==NULL&&rear==NULL)
{
head = rear = temp;
}
else
{
rear->next = temp;
temp->pre = rear;
rear = rear->next;
}
Insert(root,root,key,value,temp);
num2 ;
}
};
