一，LRU数据结构
1，链表实现
头文件
class LRU
{
private:struct node{int key;int value;node* last;node* next;node(int x, int y) : key(x), value(y), last(nullptr), next(nullptr) {};};node* head;node* tail;int size;int num;void moveToHead(node*);
public:LRU(int x);~LRU();int find(int);void insert(int x, int y);void printItself();
};源文件
//class LRU
LRU::LRU(int x) : head(NULL), tail(NULL), size(x),num(0) {};
LRU::~LRU()
{node* current = head;while (current){node* next = current->next;delete current;current = next;}
}int LRU::find(int x)
{node* current = head;while (current){if (current->key == x){moveToHead(current);return current->value;}else current = current->next;}return 404;
}void LRU::moveToHead(node* p)
{if (p == tail){node* temp = tail->last;temp->next = NULL;tail = temp;}else{node* lastnode = p->last;node* nextnode = p->next;lastnode->next = nextnode;nextnode->last = lastnode;}p->last = NULL;p->next = head;head->last = p;head = p;
}void LRU::insert(int key, int value)
{if (num + 1 > size){tail = tail->last;delete tail->next;tail->next = NULL;num--;}if (head){head->last = new node(key, value);node* temp = head;head = head->last;head->next = temp;}else head = tail = new node(key, value);num++;
}void LRU::printItself()
{node* current = head;while (current){std::cout << current->value << " ";current = current->next;}std::cout << std::endl;
}二，获取数据流的中位数
先展示错误
void MidNumber::insert(int value)
{if (left.empty()){left.push(value);}if (value > left.top()){right.push(value);}else{left.push(value);}balance();}知道为什么第一次插入时左右两个堆都会插入，因为错误使用两个if语句，第一个元素被重复插入了。
正确
头文件
class MidNumber
{
private:std::priority_queue<int, std::vector<int>, std::greater<int>> right;std::priority_queue<int, std::vector<int>, std::less<int>> left;void balance();
public:MidNumber();void insert(int);double getMidNumber();void printItself();
};源文件
//class MidNumber
MidNumber::MidNumber() {};
void MidNumber::insert(int value)
{if (left.empty()||value < left.top()){left.push(value);}else{right.push(value);}balance();
}void MidNumber::balance()
{if (std::abs((int)left.size() - (int)right.size()) > 1){if (left.size() > right.size()){right.push(left.top());left.pop();}else{left.push(right.top());right.pop();}}
}double MidNumber::getMidNumber()
{if (left.size() == right.size()){return (left.top() + right.top()) / 2.0;}else{if (left.size() > right.size()){return left.top();}else{return right.top();}}}void MidNumber::printItself()
{std::cout << left.size() << " " << right.size() << std::endl;while (!left.empty()){std::cout << left.top() << " ";left.pop();}std::cout << " " << std::endl;while (!right.empty()){std::cout << right.top() << " ";right.pop();}std::cout << std::endl;
}三，最大频率栈
我写的
头文件
class MaxFrequentStack
{
private:std::unordered_map<int, int> frequency;std::unordered_map<int, std::list<int>> stack;int maxfreq;public:MaxFrequentStack():maxfreq(0){}void push(int x);int getMax();
};源文件
//MaxFrequentStack
void MaxFrequentStack::push(int x)
{int freq;if (frequency.find(x) == frequency.end()){freq = 1;}else freq = frequency[x] + 1;frequency[x] = freq;maxfreq = maxfreq > freq ? maxfreq : freq;if (stack.find(freq) == stack.end()){std::list<int> list;list.push_back(x);stack[freq] = list;}else{stack[freq].push_back(x);}
}int MaxFrequentStack::getMax()
{int max = stack[maxfreq].back();stack[maxfreq].pop_back();if (stack[maxfreq].empty()){stack.erase(maxfreq);maxfreq--;}return max;
}AI写的
#include <iostream>
#include <unordered_map>
#include <stack>
#include <vector>class FreqStack {
private:// 记录每个元素的出现频率std::unordered_map<int, int> freq;// 记录每个频率对应的栈std::unordered_map<int, std::stack<int>> group;// 当前最大频率int maxFreq;public:FreqStack() : maxFreq(0) {}// 压入元素 xvoid push(int x) {// 增加元素 x 的频率freq[x]++;// 获取元素 x 的当前频率int f = freq[x];// 更新最大频率if (f > maxFreq) {maxFreq = f;}// 将元素 x 压入对应频率的栈中group[f].push(x);}// 移除并返回栈中出现频率最高的元素int pop() {// 获取最大频率对应的栈std::stack<int>& s = group[maxFreq];// 取出栈顶元素int x = s.top();s.pop();// 减少元素 x 的频率freq[x]--;// 如果最大频率对应的栈为空，降低最大频率if (s.empty()) {maxFreq--;}return x;}
};四，最大/小频率字符串
源文件实现
//class FreqString void FreqString::insert(Bucket* bucket1, Bucket* bucket2)
{// 在 bucket1 后面插入一个桶 bucket2Bucket* temp = bucket1->next;bucket1->next = bucket2;bucket2->next = temp;if (temp != nullptr){temp->last = bucket2;}bucket2->last = bucket1;
}void FreqString::remove(Bucket* bucket)
{if (bucket == Llimit || bucket == Rlimit){return; // 不删除边界哨兵节点}Bucket* left = bucket->last;Bucket* right = bucket->next;left->next = right;right->last = left;delete bucket;
}FreqString::FreqString()
{Llimit = new Bucket(0, "");Rlimit = new Bucket(std::numeric_limits<int>::max(), "");Llimit->next = Rlimit;Rlimit->last = Llimit;
}FreqString::~FreqString()
{Bucket* current = Llimit->next;while (current != Rlimit){Bucket* next = current->next;delete current;current = next;}delete Llimit;delete Rlimit;
}void FreqString::inc(const std::string& str)
{if (map.find(str) == map.end()){Bucket* temp = Llimit->next;if (temp->freq != 1){insert(Llimit, new Bucket(1, str));map[str] = Llimit->next;}else{temp->bucket.insert(str);map[str] = temp;}}else{Bucket* temp = map[str];Bucket* nextBucket = temp->next;if (nextBucket == Rlimit || nextBucket->freq != temp->freq + 1){insert(temp, new Bucket(temp->freq + 1, str));map[str] = temp->next;}else{nextBucket->bucket.insert(str);map[str] = nextBucket;}temp->bucket.erase(str);if (temp->bucket.empty()){remove(temp);}}
}void FreqString::dec(const std::string& str)
{if (map.find(str) == map.end()){return; // 如果字符串不存在，直接返回}Bucket* temp = map[str];if (temp->freq == 1){map.erase(str);temp->bucket.erase(str);if (temp->bucket.empty()){remove(temp);}}else{Bucket* prevBucket = temp->last;if (prevBucket == Llimit || prevBucket->freq != temp->freq - 1){insert(prevBucket, new Bucket(temp->freq - 1, str));map[str] = prevBucket->next;}else{prevBucket->bucket.insert(str);map[str] = prevBucket;}temp->bucket.erase(str);if (temp->bucket.empty()){remove(temp);}}
}std::string FreqString::getMaxfreq()
{Bucket* temp = Rlimit->last;if (temp == Llimit){std::cout << "error, the container is empty \n";return "";}std::string ans = *temp->bucket.begin();return ans;
}std::string FreqString::getMinfreq()
{Bucket* temp = Llimit->next;if (temp == Rlimit){std::cout << "error, the container is empty \n";return "";}std::string ans = *temp->bucket.begin();return ans;
}
