ACM模板和一些题目的代码实现

#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,