#include <iostream>
using namespace std;
#include <map>
#include <vector>
class LRUCache {
public:
LRUCache(int capacity) : max_num(capacity), cur(0) {}
int get(int key) {
// print_list();
map<int, int>::iterator it;
it = cache.find(key);
if (it != cache.end())
{
// 将访问元素放在最前
reorder( key);
return it->second;
}
return -1;
}
void set(int key, int value) {
// print_list();
map<int, int>::iterator it;
it = cache.find(key);
// 成功找到元素,将访问元素放在最前
if (it != cache.end())
{
cache[key] = value;
reorder(key);
}
else//没有找到,新插入,
{
// cout << key << endl;
if (cur < max_num) //可以插入新的元素
{
// printf("a\n");
cur++;
insert_head(key);
cache[key] = value;
}
else//删除一个元素,插入新的元素
{
// printf("b\n");
int a = delete_tail();
insert_head(key);
it = cache.find(a);
if (it != cache.end())
cache.erase(it);
cache[key] = value;
// cout << cache.size() << endl;
}
}
}
void print_list()
{
vector<int>::iterator it;
cout << "print_list:";
for (it = head.begin(); it != head.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
}
void reorder(int key)
{
vector<int>::iterator it;
for (it = head.begin(); it != head.end(); ++it)
{
if (*it == key)
{ head.erase(it);
break;
}
}
head.insert(head.begin(), key);
}
void insert_head(int key)
{
vector<int>::iterator it = head.begin();
head.insert(it, key);
}
int delete_tail()
{
int a = head.back();
head.erase(head.end() - 1);
return a;
}
private:
int max_num;
map<int, int> cache;
int cur;
vector<int> head;
};
int main()
{
LRUCache a(2);
a.set(2, 1);
a.set(1, 1);
cout << a.get(2) << endl;
a.set(4, 1);
cout << a.get(1) << endl;
cout << a.get(2) << endl;
}
// 2048, [set(1178, 3401), set(903, 6060), set(1127, 3054), set(1377, 1290), set(2584, 232), set(190, 2287), set(497, 3488), set(1577, 3876), set(1764, 1356), set(1500, 3094), set(1753, 2307), set(628, 4859), set(870, 4196), set(681, 3105), set(2098, 3150), set(1108, 5408), set(2036, 5005), set(873, 3508), set(2166, 1436), set(1686, 1720), set(435, 1250), set(2189, 3682), set(242, 1034), set(1685, 623), set(221, 4144), set(2386, 4927), set(380, 3618), set(583, 313), set(291, 5663), set(1155, 309), set(884, 4891), set(2321, 3152), set(1141, 351), set(1093, 2812), set(1098, 1559), set(287, 1223), set(325, 5784), set(1155, 124), set(1639, 2473), set(424, 761), set(1905, 1679), set(1444, 152), set(1321, 1371), set(1348, 1725), set(1720, 4733), set(409, 3864), set(2449, 3235), set(1040, 4981), set(10, 766), set(1708, 4726), set(426, 3287), set(1922, 1485), set(1351, 2488), set(2415, 6062), set(40, 4927), set(850, 3662), set(452, 5921), set(374, 5218), set(1407, 1307), set(1025, 4782), set(1390, 3110), set(2588, 2307), set(2253, 4487), set(1020, 3179), set(2645, 569), set(958, 2253), set(829, 2567), set(127, 165), set(1621, 949), set(1078, 5195), set(689, 2680), set(483, 2643), set(525, 2194), set(286, 697), set(2533, 753), set(1064, 494), set(380, 3730), set(2116, 5804), set(1209, 5345), set(2423, 3821), set(78, 59), set(179, 2788), set(427, 693), set(1491, 298), set(680, 2796), set(1811, 5924), set(1517, 1690), set(91, 2594), set(1685, 1297), set(2379, 2353), set(2362, 4052), set(2662, 1032), set(2548, 5939), set(1210, 6031), set(304, 478), set(688, 708), set(605, 1140), set(1553, 1341), set(1257, 1241), set(859, 1499), set(1725, 5064), set(2634, 5961), set(483, 4820), set(220, 486), set(2483, 4309), set(2490, 2048), set(1628, 278), set(2141, 1826), set(2002, 310), set(1665, 2884), set(577, 1218), set(1871, 3260), set(2444, 2714), set(179, 1638), set(2647, 1551), set(1784, 3684), set(2611, 5495), set(2493, 4492), set(94, 4244), set(1088, 4012), set(46, 1821), set(1629, 1356), set(349, 5363), set(1825, 3672), set(1506, 2901), set(2446, 6141), set(705, 2041), set(1292, 6016), set(1150, 1223), set(188, 2164), set(1270, 5409), set(1532, 2062), set(2359, 4885), set(1284, 3340), set(361, 3402), set(1130, 623), set(1508, 5644), set(1000, 6073), set(149, 2452), set(523, 5869), set(2169, 59), set(101, 3094), set(2003, 2840), set(460, 2397), set(366, 3554), set(2632, 4150), set(2090, 2424), set(2333, 2711), set(418, 5426), set(1982, 795), set(470, 4312), set(120, 3244), set(1435, 3682), set(1074, 5743), set(74, 1234), set(450, 6052), set(1953, 5485), set(1895, 5463), set(2293, 6056), set(2137, 1671), set(2400, 1120), set(2428, 5397), set(777, 1626), set(2468, 1586), set(454, 2155), set(1745, 4012), set(1069, 3193), set(700, 2937), set(333, 685), set(1083, 3266), set(726, 738), set(471, 2235), set(2062, 3729), set(1171, 655), set(498, 721), set(2233, 5670), set(2036, 6051), set(258, 1775), set(101, 105), set(2446, 1617), set(2079, 4764), set(480, 216), set(2112, 5958), set(956, 5380), set(109, 1065), set(1606, 2850), set(1639, 5910), set(2477, 1118), set(379, 4618), set(121, 5422), set(2020, 2782), set(1780, 3978), set(2285, 2612), set(1671, 5874), set(220, 362), set(2606, 3011), set(30, 5453), set(2334, 3965), set(1880, 1763), set(1169, 6100), set(27, 2420), set(255, 2841), set(2603, 1762), set(484, 2972), set(1311, 5865), set(872, 1204), set(879, 3080), set(638, 2606), set(2448, 1427), set(497, 5300), set(982, 6052), set(79, 5876), set(1252, 1821), set(249, 1542), set(325, 1033), set(1100, 2435), set(1610, 1570), set(1473, 5493), set(814, 2219), set(879, 3253), set(1403, 3474), set(1694, 3729), set(2221, 1699), set(2550, 3523), set(2013, 3569), set(123, 5415), set(288, 1068), set(1706, 5091), set(878, 2786), set(1180, 4298), set(1502, 6047), set(927, 3227), set(1564, 2856), set(2074, 1886), set(898, 3479), set(1242, 2769), set(266, 1238), set(117, 1934), set(2433, 2642), set(1200, 296), set(2265, 2250), set(128, 1139), set(1120, 702), set(2467, 5849), set(2162, 545), set(2393, 5875), set(1721, 1766), set(423, 4311), set(1981, 3662), set(823, 3044), set(746, 4647), set(540, 1598), set(1097, 5199), set(2424, 5779), set(2583, 5218), set(1501, 2409), set(149, 4859), set(974, 5931), set(1179, 604), set(908, 6028), set(479, 2789), set(1025, 1441), set(713, 3354), set(1530, 2378), set(216, 5109), set(38, 4806), set(1331, 2011), set(1536, 3886), set(1905, 3511), set(845, 4449), set(1481, 1561), set(1524, 4721), set(1590, 1265), set(2556, 1480), set(2257, 979), set(900, 1944), set(2507, 4765), set(284, 4521), set(1205, 859), set(1229, 3108), set(2365, 1126), set(239, 199), set(313, 4797), set(2545, 951), set(1735, 4412), set(165, 688), set(1759, 2098), set(854, 2003), set(805, 2494), set(2038, 2856), set(469, 260), set(1559, 1030), set(2226, 3610), set(1877, 2895), set(1588, 5891), set(2428, 3819), set(1506, 4079), set(498, 2359), set(868, 2672), set(1236, 5445), set(2443, 5959), set(1351, 1660), set(2051, 4598), set(342, 3083), set(1203, 5670), set(2079, 2745), set(1254, 705), set(1712, 3090), set(1744, 4993), set(29, 3372), set(2229, 382), set(2275, 5048), set(2070, 34), set(1284, 4212), set(2444, 3825), set(2070, 3358), set(1986, 3193), set(1309, 77), set(230, 3043), set(1830, 4814), set(2016, 5290), set(868, 5735), set(784, 3243), set(1953, 1674), set(1544, 1964), set(39, 3678), set(2230, 4421), set(2485, 4231), set(902, 2447), set(1528, 531), set(518, 4059), set(2652, 4777), set(444, 268), set(1928, 2653), set(2051, 3645), set(1864, 3217), set(2622, 3337), set(1277, 1836), set(1689, 4743), set(1802, 2108), set(341, 5374), set(751, 3322), set(560, 1180), set(1591, 2413), set(838, 5600), set(2118, 2283), set(861, 4483), set(579, 3380), set(2055, 5497), set(807, 4400), set(85, 5214), set(181, 125), set(1230, 2720), set(1043, 3693), set(900, 3990), set(707, 1585), set(1627, 977), set(1006, 3558), set(1496, 6016), set(105, 2145), set(1223, 3112), set(322, 5935), set(983, 760), set(1817, 5387), set(1085, 6077), set(1502, 1275), set(2015, 3337), set(2628, 5087), set(2116, 1163), set(2532, 2441), set(1117, 238), set(719,
没有合适的资源?快使用搜索试试~ 我知道了~
ACM-(ACM模板和一些题目的代码实现).zip
共404个文件
cpp:369个
exe:8个
o:8个
需积分: 1 0 下载量 145 浏览量
2024-04-19
12:15:24
上传
评论
收藏 1.78MB ZIP 举报
温馨提示
ACM模板和一些题目的代码实现
资源推荐
资源详情
资源评论
收起资源包目录
ACM-(ACM模板和一些题目的代码实现).zip (404个子文件)
in.c 26B
robot.cp 1B
LRU_cache.cpp 285KB
上交计算几何模板.cpp 17KB
上交大数模板.cpp 11KB
NOTONLLY的SBT模板.cpp 10KB
上交数论.cpp 9KB
RMQ-ST算法.cpp 9KB
POJ3169Layout差分约束最短路求最大值.cpp 8KB
SBT.cpp 8KB
SBT2.cpp 8KB
POJ 1436 Horizontally Visible Segments 线段树.cpp 7KB
HDU 3642 线段树Get The Treasury.cpp 7KB
后缀数组模板.cpp 7KB
POJ百练2980大整数乘法.cpp 7KB
POJ百练2981大整数加法.cpp 7KB
八数码 (2).cpp 6KB
度限制最小生成树.cpp 6KB
混合图欧拉回路.cpp 6KB
八数码.cpp 6KB
hoj1917Peaceful Commission2-sat.cpp 6KB
HDU 2896 病毒侵袭AC自动机.cpp 6KB
hdu3308 线段树区间合并LCIS.cpp 6KB
hoj2360Redundant Paths双连通.cpp 6KB
最大流dinic.cpp 6KB
poj3468A Simple Problem with Integers.cpp 5KB
hdu 3065 病毒侵袭持续中AC自动机.cpp 5KB
poj3243解高次同余方程.cpp 5KB
poj1201 Intervals差分约束.cpp 5KB
poj2528线段树 Mayor’s posters.cpp 5KB
二维线段树.cpp 5KB
二维线段树.cpp 5KB
HH牛的模板.cpp 4KB
xx.cpp 4KB
hoj peaceful commitions-sat.cpp 4KB
hdu3397线段树区间合并 Sequence operation.cpp 4KB
poj 3225线段树区间合并Help with Intervals.cpp 4KB
左偏树 (2).cpp 4KB
C.cpp 4KB
hdu 3506 Monkey Party.cpp 4KB
poj2429已知gcd和lcm求a,b.cpp 4KB
Dijkstra+heap.cpp 4KB
hoj1966输出欧拉回路Catenyms.cpp 4KB
AC自动机模板.cpp 4KB
POJ-2337 Catenyms 欧拉回路模板.cpp 4KB
poj 1639度限制最小生成树 Picnic Planning.cpp 4KB
HDU 2874(LCA tarjan离线).cpp 4KB
hoj 2524 Allocate Dormitories 二分图的最大匹配.cpp 4KB
poj2942点双连通奇圈-二分图判断Knights of the Round Table.cpp 4KB
字符串散列.cpp 4KB
POJ 1236 Network of Schools强连通分量.cpp 4KB
hoj2021欧拉回路判断Colored Sticks.cpp 4KB
H.cpp 3KB
HDU2243 字典树考研路茫茫――单词情结.cpp 3KB
poj2983差分约束系统.cpp 3KB
hoj2025二分图最佳匹配Going Home.cpp 3KB
KM算法.cpp 3KB
后缀数组.cpp 3KB
第K短路.cpp 3KB
稳定婚姻匹配.cpp 3KB
NOTONLLY的AC自动机模板.cpp 3KB
指数型母函数.cpp 3KB
2_SAT.cpp 3KB
poj 1128 艰难的拓扑排序Frame Stacking.cpp 3KB
poj2689素数距离.cpp 3KB
HDU 2874(LCA tarjan离线)我的版本.cpp 3KB
hoj1819郁闷的出纳员.cpp 3KB
hoj1859二分图匹配Knights.cpp 3KB
高精度整数.cpp 3KB
hdu 3265 Posters矩形面积并 扫描线+线段树.cpp 3KB
LCA-tarjan.cpp 3KB
HDU4454 Stealing a Cake 第37届杭州赛区 B题三分法.cpp 3KB
poj1811整数分解加判素.cpp 3KB
HOJ2741The Busiest Man 强连通分量+缩点+传递闭包 .cpp 3KB
poj 2991线段树成段更新 Crane.cpp 3KB
hdu 2222-Keywords Search.cpp 3KB
poj1986tarjanLCA-Distance Queries - 副本 (2).cpp 3KB
poj1986tarjanLCA-Distance Queries - 副本.cpp 3KB
hoj1624二分图匹配或贪心Sorting Slides.cpp 3KB
zoj AC自动机3430 Detect the Virus.cpp 3KB
poj3641最小树形图.cpp 3KB
POJAC自动机2778 DNA Sequence.cpp 3KB
NOTONLLY的后缀数组模板.cpp 3KB
hdu2815高次同余方程.cpp 3KB
poj 1160 Post Office.cpp 3KB
HH后缀数组模板.cpp 3KB
欧拉回路.cpp 3KB
hoj2501二分加最大匹配Against Mammoths.cpp 3KB
A.cpp 3KB
B.cpp 3KB
最大流SAP.cpp 3KB
hoj1426欧拉回路door man.cpp 3KB
E.cpp 3KB
1743 Musical Theme后缀数组.cpp 3KB
hdu 3065病毒侵袭持续中.cpp 3KB
HDU 4251划分树 The Famous ICPC Team Again.cpp 3KB
hoj1119poj1151 hdu1542线段树扫描线Atlantis 矩形面积求并.cpp 3KB
poj2289二分图多重匹配+二分Jamie's Contact Groups.cpp 3KB
LCA_tarjan.cpp 3KB
最大流.cpp 3KB
共 404 条
- 1
- 2
- 3
- 4
- 5
资源评论
DC头发很茂密
- 粉丝: 1818
- 资源: 600
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功