建设服装网站目的,营销app,wordpress标题翻译插件,大连图文设计有限公司目录
1. 工龄问题求解 ★
2. 字符图形输出 ★★
3. LRU 缓存机制 ★★★ 1. 工龄问题求解
给定公司N名员工的工龄#xff0c;要求按工龄增序输出每个工龄段有多少员工。输入首先给出正整数N#xff0c;即员工总人数#xff1b; 随后给出N个整数#xff0c;即每个员工…
目录
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(i0; in; i){scanf(%d,x);if(x9)a[1];else if(x9x19)a[2];else if(x19x29)a[3];else if(x29x39)a[4];else if(x39x49)a[5];else if(x49x59)a[6];else if(x59x69)a[7];else if(x69x79)a[8];else if(x79x89)a[9];elsea[10];}for(i0;i10;i){if(a[i]0){printf(%d-%d:%d\n,i*10-10,i*10-1,a[i]);}}
} 2. 字符图形输出
编程实现把输入任意整数n后可打印出n行三角字符阵列图形。例如输入整数5时程序运行结果如下
ENTER A NUMBER5回车
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); // 缓存是 {11}
lRUCache.put(2, 2); // 缓存是 {11, 22}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4提示
1 capacity 30000 key 100000 value 105最多调用 2 * 105 次 get 和 put
代码
#include bits/stdc.h
using namespace std;
class LRUCache
{
private:int _cap;listpairint, int cache;unordered_mapint, listpairint, int::iterator umap;
public:LRUCache(int capacity){_cap capacity;}int get(int key){auto iter umap.find(key);if (iter umap.end())return -1;pairint, 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); // 缓存是 {11}Cache.put(2, 2); // 缓存是 {11, 22}cout Cache.get(1) endl; // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}cout Cache.get(2) endl; // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}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 cap0; //表示当前容量node *head,*tail;void push_front(node *cur) //头部插入{if(cap0){headcur;tailcur;cap;}else{cur-nexthead;head-precur;headcur;cap;} }void push_back(node *cur) //尾部插入{if(cap0){headcur;tailcur;cap;}else{cur-pretail;tail-nextcur;tailcur;cap;} }void pop_front() //头部弹出 {if(cap0) return;node *phead;headp-next;delete p;cap--;}void pop_back() //尾部弹出 {if(cap0) return;node *ptail;tailp-pre;delete p;cap--;}void sethead(node *p) //将p结点变为新的头部{if(phead) return;else if(ptail){p-pre-nextNULL;tailp-pre;p-nexthead;head-prep;p-preNULL;headp;}else{p-pre-nextp-next;p-next-prep-pre;p-nexthead;head-prep;p-preNULL;headp;}}
public:LRUCache(int capacity): m_capacity(capacity){}int get(int key) {if(!m.count(key)) return -1; //不在哈希表中直接返回-1node *pm[key];sethead(p);//提到链表头部return head-value;}void put(int key, int value) {if(!m.count(key)) //如果不在缓存中{node *curnew node(key,value);m[key]cur; //加入哈希表//1.容量已满去掉尾结点从头插入if(capm_capacity){m.erase(tail-key);//将要弹出的尾结点对应映射从哈希表中删除 pop_back();push_front(cur); //头部插入}//2.容量未满直接头部插入else push_front(cur); }else //在缓存中 ,旧值更新 {node *pm[key];p-valuevalue;sethead(p); //提到链表头部}}
private:int m_capacity;unordered_mapint,node*m;
};int main()
{LRUCache Cache LRUCache(2);Cache.put(1, 1); // 缓存是 {11}Cache.put(2, 2); // 缓存是 {11, 22}cout Cache.get(1) endl; // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}cout Cache.get(2) endl; // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}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_mapint, 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_mapint, 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_mapint, 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_mapint, ListNode* m;//记录数据和其链表地址ListNode *head;//链表头ListNode *tail;//链表尾
};int main()
{LRUCache Cache LRUCache(2);Cache.put(1, 1); // 缓存是 {11}Cache.put(2, 2); // 缓存是 {11, 22}cout Cache.get(1) endl; // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}cout Cache.get(2) endl; // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}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;listpairint,int li;unordered_mapint, listpairint,int::iterator up;LRUCache(int capacity) {capcapacity;}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.secondvalue;li.push_front(tmp);up[key]li.begin();}else{if(up.size()cap){auto tmpli.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); // 缓存是 {11}Cache.put(2, 2); // 缓存是 {11, 22}cout Cache.get(1) endl; // 返回 1Cache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}cout Cache.get(2) endl; // 返回 -1 (未找到)Cache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}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次是等效的。
——以上附录文字来源于百度百科
