网站设置快捷方式,温州网站建设方案报价,广东省建设厅网站可以查,管理咨询公司取名. - 力扣#xff08;LeetCode#xff09;
有两个水壶#xff0c;容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。
你可以#xff1a;
装满任意一个水壶清空任意一个水壶将水从一个水壶倒入另一个水壶#xff0c;直到接水壶已…. - 力扣LeetCode
有两个水壶容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。
你可以
装满任意一个水壶清空任意一个水壶将水从一个水壶倒入另一个水壶直到接水壶已满或倒水壶已空。
典型的搜索问题在任意一个时刻我们可以且仅可以采取以下几种操作
把 X 壶的水灌进 Y 壶直至灌满或倒空 把 Y 壶的水灌进 X 壶直至灌满或倒空 把 X 壶灌满 把 Y 壶灌满 把 X 壶倒空 把 Y 壶倒空。
采用深度优先搜索来解决。不过可能会陷入无限递归。需要使用哈希表去重。
using PII pairint, int;class Solution {
public:bool canMeasureWater(int x, int y, int z) {stackPII stk;stk.emplace(0, 0);auto hash_function [](const PII o) {return hashint()(o.first) ^ hashint()(o.second);};unordered_setPII, decltype(hash_function) seen(0, hash_function);while (!stk.empty()) {if (seen.count(stk.top())) {stk.pop();continue;}seen.emplace(stk.top());auto [remain_x, remain_y] stk.top();stk.pop();if (remain_x z || remain_y z || remain_x remain_y z) {return true;}// 把 X 壶灌满。stk.emplace(x, remain_y);// 把 Y 壶灌满。stk.emplace(remain_x, y);// 把 X 壶倒空。stk.emplace(0, remain_y);// 把 Y 壶倒空。stk.emplace(remain_x, 0);// 把 X 壶的水灌进 Y 壶直至灌满或倒空。stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y min(remain_x, y - remain_y));// 把 Y 壶的水灌进 X 壶直至灌满或倒空。stk.emplace(remain_x min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));}return false;}
};
哈希表存储pair分别表示xy壶中的元素。
如果一个类型没有提供哈希函数那么需要实现一个哈希函数否则无法存放进对应的桶中标准库的和一些标量都实现了这个函数所以不需要重载如果是自定义类型想要存放在桶里必须实现这个函数否则无法正常存放。所以代码中使用lambda表达式定义了哈希函数。
即 auto hash_function [](const PII o) {return hashint()(o.first) ^ hashint()(o.second);};
然后使用 unordered_setPII, decltype(hash_function) seen(0, hash_function);定义哈希表。decltype关键字表示自动类型推导。
auto hash_function [](const PII o) {return hash()(o.first) ^ hash()(o.second);}; 这行代码定义了一个lambda表达式 hash_function用于计算PII类型假设PII是一个具有两个成员变量的结构体或类的哈希值。这个lambda表达式接受一个PII对象 o 作为输入并使用 hash() 函数分别计算 o.first 和 o.second 的哈希值然后使用异或操作符 ^ 结合这两个哈希值。
unordered_setPII, decltype(hash_function) seen(0, hash_function); 这行代码创建了一个无序集合 seen其元素类型为PII使用之前定义的 hash_function 作为哈希函数。第一个模板参数指定集合中元素的类型为PII而第二个模板参数 decltype(hash_function) 指定了哈希函数类型即使用之前定义的 hash_function。
注意这里的 0 是作为集合的初始容量传递的表示集合的初始大小为0。
因此这段代码的目的是创建一个无序集合 seen用于存储PII类型的对象并使用自定义的哈希函数来计算元素的哈希值。这样可以在集合中快速查找、插入和删除元素并确保元素的唯一性。
