16.3 复合数据结构
return e;
} uf.connect(u, v);
} return vector<int>{-1, -1};
} };
class UF { vector<int> id, size;
public:
UF(int n): id(n), size(n, 1) { iota(id.begin(), id.end(), 0); // iota0n-1
}
int find(int p) { while (p != id[p]) {
id[p] = id[id[p]]; // p = id[p];
} return p;
}
void connect(int p, int q) { int i = find(p), j = find(q);
if (i != j) { //
if (size[i] < size[j]) { id[i] = j;
size[j] += size[i];
} else { id[j] = i;
size[i] += size[j];
} }
}
bool isConnected(int p, int q) { return find(p) == find(q);
} };
16.3
unordered_mapmapvectorlist
146. LRU Cache (Medium)
(least recently used cache, LRU)
n
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);// returns 1 cache.put(3, 3);// evicts key 2
cache.get(2);// returns -1 (not found)
cache.put(4, 4);// evicts key 1 cache.get(1);// returns -1 (not found)
cache.get(3);// returns 3 cache.get(4);// returns 4
list<pair<int, int>>keyvalue un-
ordered_map<int, list<pair<int, int»::iterator> splicecash hit
class LRUCache{ unordered_map<int, list<pair<int, int>>::iterator> hash;
list<pair<int, int>> cache;
int size;
public:
LRUCache(int capacity):size(capacity) {}
int get(int key) { auto it = hash.find(key);
if (it == hash.end()) { return -1;
} cache.splice(cache.begin(), cache, it->second);
return it->second->second;
}
void put(int key, int value) { auto it = hash.find(key);
if (it != hash.end()) { it->second->second = value;
全站分卷索引 · 68 卷
- 11 题目分类
- 22 最易懂的贪心算法
- 32.3 区间问题
- 42.4 练习
- 53 玩转双指针
- 63.2 Two Sum
- 73.4 快慢指针
- 83.5 滑动窗口
- 93.6 练习
- 104 居合斩!二分查找
- 114.3 查找区间
- 124.4 旋转数组查找数字
- 134.5 练习
- 145 千奇百怪的排序算法
- 155.2 快速选择
- 165.3 桶排序
- 175.4 练习
- 186 一切皆可搜索
- 196.3 回溯法
- 206.4 广度优先搜索
- 216.5 练习
- 227 深入浅出动态规划
- 237.3 基本动态规划:二维
- 247.4 分割类型题
- 257.5 子序列问题
- 267.6 背包问题
- 277.7 字符串编辑
- 287.8 股票交易
- 297.9 练习
- 308 化繁为简的分治法
- 318.3 练习
- 329 巧解数学问题
- 339.4 数字处理
- 349.5 随机与取样
- 359.6 练习
- 3610 神奇的位运算
- 3710.3 二进制特性
- 3810.4 练习
- 3911 妙用数据结构
- 4011.2 数组
- 4111.3 栈和队列
- 4211.4 单调栈
- 4311.5 优先队列
- 4411.6 双端队列
- 4511.7 哈希表
- 4611.8 多重集合和映射
- 4711.9 前缀和与积分图
- 4811.10 练习
- 11.10
- 566. Reshape the Matrix (Easy)
- 225. Implement Stack using Queues (Easy)
- 503. Next Greater Element II (Medium)
- 217. Contains Duplicate (Easy)
- 697. Degree of an Array (Easy)
- 594. Longest Harmonious Subsequence (Easy)
- 287. Find the Duplicate Number (Medium)
- 313. Super Ugly Number (Medium)
- 870. Advantage Shuffle (Medium)
- 307. Range Sum Query - Mutable (Medium)
- 4912 令人头大的字符串
- 5012.3 字符串理解
- 5112.4 字符串匹配
- 5212.5 练习
- 5313 指针三剑客之一:链表
- 5413.3 其它链表技巧
- 5513.4 练习
- 5614 指针三剑客之二:树
- 5714.3 层次遍历
- 5814.4 前中后序遍历
- 5914.5 二叉查找树
- 6014.6 字典树
- 6114.7 练习
- 14.7
- 226. Invert Binary Tree (Easy)
- 617. Merge Two Binary Trees (Easy)
- 572. Subtree of Another Tree (Easy)
- 404. Sum of Left Leaves (Easy)
- 513. Find Bottom Left Tree Value (Easy)
- 538. Convert BST to Greater Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Easy)
- 530. Minimum Absolute Difference in BST (Easy)
- 889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)
- 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
- 94. Binary Tree Inorder Traversal (Medium)
- 6215 指针三剑客之三:图
- 6315.3 拓扑排序
- 6415.4 练习
- 6516 更加复杂的数据结构
- 6616.3 复合数据结构
- 6716.4 练习
- 6817 后记