C/C++每日一练(20230225)

目录

1. 工龄问题求解  ★

2. 字符图形输出  ★★

3. LRU 缓存机制  ★★★

---

1. 工龄问题求解

给定公司N名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。输入首先给出正整数N，即员工总人数； 随后给出N个整数，即每个员工的工龄，范围在[0, 99]。其中，0-9为第1个工龄段，10-19为第2个工龄段，…，90-99为第10个工龄段。按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为0则不输出该项。

代码：

#include <stdio.h>
int main()
{int i,n,a[11]= {0},x;scanf("%d",&n);for(i=0; i<n; i++){scanf("%d",&x);if(x<=9)a[1]++;else if(x>9&&x<=19)a[2]++;else if(x>19&&x<=29)a[3]++;else if(x>29&&x<=39)a[4]++;else if(x>39&&x<=49)a[5]++;else if(x>49&&x<=59)a[6]++;else if(x>59&&x<=69)a[7]++;else if(x>69&&x<=79)a[8]++;else if(x>79&&x<=89)a[9]++;elsea[10]++;}for(i=0;i<=10;i++){if(a[i]>0){printf("%d-%d:%d\n",i*10-10,i*10-1,a[i]);}}
}

2. 字符图形输出

编程实现把输入任意整数n后，可打印出n行三角字符阵列图形。例如，输入整数5时，程序运行结果如下：

ENTER A NUMBER：5<回车>
A  C  F  J  O
B  E  I  N
D  H  M
G  L
K

代码： 

#include <iostream>
using namespace std;
char a[100][100];
int main()
{char c = 'A';int n = 5;for (int i = 0; i < n; i++){for (int j = i; j >= 0; j--){a[j][i-j] = c++;}}for (int i = 0; i < n; i++){for (int j = 0; j < n - i; j++){cout << a[i][j] << " ";}cout << endl;}
}

3. LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制

实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释 
LRUCache lRUCache = new LRUCache(2); 
lRUCache.put(1, 1); // 缓存是 {1=1} 
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} 
lRUCache.get(1); // 返回 1 
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} 
lRUCache.get(2); // 返回 -1 (未找到) 
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} 
lRUCache.get(1); // 返回 -1 (未找到) 
lRUCache.get(3); // 返回 3 
lRUCache.get(4); // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

代码：

#include <bits/stdc++.h>
using namespace std;
class LRUCache
{
private:int _cap;list<pair<int, int>> cache;unordered_map<int, list<pair<int, int>>::iterator> umap;
public:LRUCache(int capacity){_cap = capacity;}int get(int key){auto iter = umap.find(key);if (iter == umap.end())return -1;pair<int, int> kv = *umap[key];cache.erase(umap[key]);cache.push_front(kv);umap[key] = cache.begin();return kv.second;}void put(int key, int value){auto iter = umap.find(key);if (iter != umap.end()){cache.erase(umap[key]);cache.push_front(make_pair(key, value));umap[key] = cache.begin();return;}if (cache.size() == _cap){auto iter = cache.back();umap.erase(iter.first);cache.pop_back();cache.push_front(make_pair(key, value));umap[key] = cache.begin();}else{cache.push_front(make_pair(key, value));umap[key] = cache.begin();}}
};int main()
{LRUCache Cache = LRUCache(2);Cache.put(1, 1); // 缓存是 {1=1}Cache.put(2, 2); // 缓存是 {1=1, 2=2}cout << Cache.get(1) << endl;    // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}cout << Cache.get(2) << endl;    // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}cout << Cache.get(1) << endl;    // 返回 -1 (未找到)cout << Cache.get(3) << endl;    // 返回 3cout << Cache.get(4) << endl;    // 返回 4return 0;
} 

以下代码摘自CSDN博客的不同文章(已附原文出处链接)

代码2：

#include <bits/stdc++.h>
using namespace std;class LRUCache {struct node{int key;int value;struct node *pre;struct node *next;node(int k,int v):key(k),value(v),pre(NULL),next(NULL){}};int cap=0; //表示当前容量node *head,*tail;void push_front(node *cur) //头部插入{if(cap==0){head=cur;tail=cur;cap++;}else{cur->next=head;head->pre=cur;head=cur;cap++;}	}void push_back(node *cur) //尾部插入{if(cap==0){head=cur;tail=cur;cap++;}else{cur->pre=tail;tail->next=cur;tail=cur;cap++;}	}void pop_front() //头部弹出 {if(cap==0) return;node *p=head;head=p->next;delete p;cap--;}void pop_back() //尾部弹出 {if(cap==0) return;node *p=tail;tail=p->pre;delete p;cap--;}void sethead(node *p) //将p结点变为新的头部{if(p==head) return;else if(p==tail){p->pre->next=NULL;tail=p->pre;p->next=head;head->pre=p;p->pre==NULL;head=p;}else{p->pre->next=p->next;p->next->pre=p->pre;p->next=head;head->pre=p;p->pre=NULL;head=p;}}
public:LRUCache(int capacity): m_capacity(capacity){}int get(int key) {if(!m.count(key)) return -1; //不在哈希表中，直接返回-1node *p=m[key];sethead(p);//提到链表头部return head->value;}void put(int key, int value) {if(!m.count(key)) //如果不在缓存中{node *cur=new node(key,value);m[key]=cur; //加入哈希表//1.容量已满，去掉尾结点从头插入if(cap==m_capacity){m.erase(tail->key);//将要弹出的尾结点对应映射从哈希表中删除 pop_back();push_front(cur); //头部插入}//2.容量未满，直接头部插入else  push_front(cur); }else //在缓存中 ,旧值更新 {node *p=m[key];p->value=value;sethead(p); //提到链表头部}}
private:int m_capacity;unordered_map<int,node*>m;
};int main()
{LRUCache Cache = LRUCache(2);Cache.put(1, 1); // 缓存是 {1=1}Cache.put(2, 2); // 缓存是 {1=1, 2=2}cout << Cache.get(1) << endl;    // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}cout << Cache.get(2) << endl;    // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}cout << Cache.get(1) << endl;    // 返回 -1 (未找到)cout << Cache.get(3) << endl;    // 返回 3cout << Cache.get(4) << endl;    // 返回 4return 0;
} 

 来源：LRU缓存机制的实现（C++版本）_作者：一坨大西瓜

代码3：

#include <bits/stdc++.h>
using namespace std;class LRUCache {
public:struct ListNode {//使用结构体建立双向链表，包含前驱、后继、key-value和构造函数ListNode *pre;ListNode *next;int key;int val;ListNode(int _key, int _val) : pre(NULL), next(NULL), key(_key), val(_val) {};};LRUCache(int capacity) : max_cnt(capacity), cnt(0) {head = new ListNode(-1, -1);tail = new ListNode(-1, -1);head->next = tail;//首尾相接tail->pre = head;}void update(ListNode *p) {//更新链表if (p->next == tail) return;//将p与前后连接断开p->pre->next = p->next;p->next->pre = p->pre;//将p插入尾节点p->pre = tail->pre;p->next = tail;tail->pre->next = p;tail->pre = p;}int get(int key) {//获取值unordered_map<int, ListNode*>::iterator it = m.find(key);if (it == m.end()) return -1;ListNode *p = it->second;//提取p的value后更新pupdate(p);return p->val;}void put(int key, int value) {if (max_cnt <= 0) return;unordered_map<int, ListNode*>::iterator it = m.find(key);//查找key值是否存在//先延长链表再判断，如果超出，则删除节点if (it == m.end()) {//如果不存在，则放在双向链表头部，即链表尾ListNode *p = new ListNode(key, value);//初始化key和valuem[key] = p;//建立新的map//在尾部插入新节点p->pre = tail->pre;tail->pre->next = p;tail->pre = p;p->next = tail;cnt++;//计数+1if (cnt > max_cnt) {//如果计数大于了缓存最大值//删除头结点ListNode *pDel = head->next;head->next = pDel->next;pDel->next->pre = head;//在链表中删除后，需要在map中也删除掉unordered_map<int, ListNode*>::iterator itDel = m.find(pDel->key);m.erase(itDel);//delete pDel;cnt--;}}else {//如果存在ListNode *p = it->second;//因为map的second存储的是key对应的链表地址，所以将其赋给pp->val = value;//计算p内存块中的value值update(p);//更新p}}private:int max_cnt;//最大缓存数量int cnt;//缓存计数unordered_map<int, ListNode*> m;//记录数据和其链表地址ListNode *head;//链表头ListNode *tail;//链表尾
};int main()
{LRUCache Cache = LRUCache(2);Cache.put(1, 1); // 缓存是 {1=1}Cache.put(2, 2); // 缓存是 {1=1, 2=2}cout << Cache.get(1) << endl;    // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}cout << Cache.get(2) << endl;    // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}cout << Cache.get(1) << endl;    // 返回 -1 (未找到)cout << Cache.get(3) << endl;    // 返回 3cout << Cache.get(4) << endl;    // 返回 4return 0;
} 

来源：C++ 实现LRU缓存机制_作者：SanfordZhu

代码4：

#include <bits/stdc++.h>
using namespace std;class LRUCache {
public:int cap;list<pair<int,int>> li;unordered_map<int, list<pair<int,int>>::iterator > up;LRUCache(int capacity) {cap=capacity;}int get(int key) {if(up.find(key)!=up.end()){auto tmp= *up[key];    //获取该元素值li.erase(up[key]);     //在链表中去除该元素，erase参数为迭代器li.push_front(tmp);    //将该元素放在链表头部up[key]=li.begin();    //重新索引该元素return tmp.second;     //返回值}return -1;}void put(int key, int value) {if(up.find(key)!=up.end()){auto tmp=*up[key];li.erase(up[key]);tmp.second=value;li.push_front(tmp);up[key]=li.begin();}else{if(up.size()>=cap){auto tmp=li.back();li.pop_back();up.erase(tmp.first);              }li.push_front(make_pair(key,value));up[key]=li.begin();              }      }
};int main()
{LRUCache Cache = LRUCache(2);Cache.put(1, 1); // 缓存是 {1=1}Cache.put(2, 2); // 缓存是 {1=1, 2=2}cout << Cache.get(1) << endl;    // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}cout << Cache.get(2) << endl;    // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}cout << Cache.get(1) << endl;    // 返回 -1 (未找到)cout << Cache.get(3) << endl;    // 返回 3cout << Cache.get(4) << endl;    // 返回 4return 0;
} 

来源：[LeetCode][C++] LRU缓存机制_作者：消失男孩

---

附录

页面置换算法

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。 置换算法的好坏， 将直接影响到系统的性能。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会再访问的页面调出。存在着许多种置换算法，它们都试图更接近于理论上的目标。

最近最少使用（LRU）

是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

最佳置换算法（OPT）

这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。

先进先出置换算法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

最少使用（LFU）置换算法

在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。

——以上附录文字来源于百度百科