11.7 哈希表
dq.pop_back();
} dq.push_back(i);
if (i >= k - 1) { ans.push_back(nums[dq.front()]);
} }
return ans;
}
11.7
O¹nº O¹1º
C++unordered_set unordered_map
26
template <typename T> class HashTable {
private:
vector<list<T>> hash_table;
// int myhash(const T & obj) const {
return hash(obj, hash_table.size());
}
public:
// size HashTable(int size=31) {
hash_table.reserve(size);
hash_table.resize(size);
}
~HashTable() {}
// bool contains(const T & obj) {
int hash_value = myhash(obj);
const list<T> & slot = hash_table[hash_value];
std::list<T>::const_iterator it = slot.cbegin();
for (; it != slot.cend() && *it != obj; ++it);
return it != slot.cend();
}
// bool insert(const T & obj) {
if (contains(obj)) { return false;
int hash_value = myhash(obj);
std::list<T> & slot = hash_table[hash_value];
slot.push_front(obj);
return true;
}
// bool remove(const T & obj) {
list<T> & slot = hash_table[myhash(obj)];
auto it = find(slot.begin(), slot.end(), obj);
if (it == slot.end()) { return false;
} slot.erase(it);
return true;
} };
// int hash(const int & key, const int &tableSize) {
return key % tableSize;
}
set/map unordered_set/unordered_map
1. Two Sum (Easy)
2
Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1]
02179
i target - nums[i]target
vector<int> twoSum(vector<int>& nums, int target) { //
unordered_map<int, int> hash;
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
auto pos = hash.find(target - num);
if (pos == hash.end()) { hash[num] = i;
} else { ans.push_back(pos->second);
ans.push_back(i);
break;
} }
return ans;
}
128. Longest Consecutive Sequence (Hard)
Input: [100, 4, 200, 1, 3, 2] Output: 4
[1,2,3,4]
int longestConsecutive(vector<int>& nums) { unordered_set<int> hash;
for (const int & num: nums) { hash.insert(num);
} int ans = 0;
while (!hash.empty()) { int cur = *(hash.begin());
hash.erase(cur);
int next = cur + 1, prev = cur - 1;
while (hash.count(next)){ hash.erase(next++);
} while (hash.count(prev)) {
hash.erase(prev--);
ans = max(ans, next - prev - 1);
return ans;
149. Max Points on a Line (Hard)
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] ^
| | o
|oo |o
| oo +------------------->
0 1 2 3 4 5 6 Output: 4
y = 5x
ii ii
int maxPoints(vector<vector<int>>& points) { unordered_map<double, int> hash; // <,>
int max_count = 0, same = 1, same_y = 1;
for (int i = 0; i < points.size(); ++i) { same = 1, same_y = 1;
for (int j = i + 1; j < points.size(); ++j) { if (points[i][1] == points[j][1]) {
++same_y;
if (points[i][0] == points[j][0]) { ++same;
} } else {
double dx = points[i][0] - points[j][0], dy = points[i][1] - points[j][1];
++hash[dx/dy];
max_count = max(max_count, same_y);
for (auto item : hash) {
全站分卷索引 · 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 后记