题目描述
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。 你允许： 装满任意一个水壶 清空任意一个水壶 从一个水壶向另外一个水壶倒水，直到装满或者倒空
Example1:
输入: x = 3, y = 5, z = 4 输出: True
Example2:
输入: x = 2, y = 6, z = 5 输出: False
解题思路
- 不知道怎么写的 先记上
- 参考
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(z<0||z>x+y)
return false;
if(!z) return true;//边界
int g;
if(x==0||y==0)//除数不为0
g=x+y;
else
g=gcd(x,y);
return !(z%g);
}
int gcd(int a,int b)//辗转相除法
{
if(a%b==0)
return b;
return gcd(b,a%b);
}
};
