题目
数学解法
裴蜀定理：对于两个数x,y, 存在a,b使得ax+by = z成立当且仅当z是x与y最大公因数的倍数。
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if (x + y < z) return false;
if (x == 0 || y == 0) return z == 0 || x + y == z;
return z % gcd(x, y) == 0;
}
};
深度优先搜索
每次我们只有下面6种操作：
- 装满x
- 装满y
- 倒空x
- 倒空y
- 把x倒入y
- 把y倒入x
为了避免相同情况被计算多次，维护一个set保存已经出现过的组合。
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
auto hashfuc = [](const pair<int,int>& o){
return hash<int>()(o.first)^hash<int>()(o.second);
}; // lambda表达式 - 用于生成pair<int,int>的hashcode
unordered_set<pair<int,int>,decltype(hashfuc)> seen(0,hashfuc);
stack<pair<int,int>> stack;
stack.push({0,0});
while(!stack.empty()) {
auto p = stack.top();
if(seen.count(p)) { // 判断是否已经在set中
stack.pop();
continue;
}
if(p.first == z || p.second == z || p.first+p.second == z)
return true;
seen.emplace(p); // set的插入操作
// auto [x_remain,y_remain] = p; // C++17 Structured Binding
stack.push({x,p.second});
stack.push({p.first,y});
stack.push({0,p.second});
stack.push({p.first,0});
stack.push({p.first-min(p.first,y-p.second),p.second+min(p.first,y-p.second)});
stack.push({p.first+min(p.second,x-p.first),p.second-min(p.second,x-p.first)});
}
return false;
}
};