一、题目
1、题目描述
有两个水壶,容量分别为
jug1Capacity
和jug2Capacity
升。水的供应是无限的。确定是否有可能使用这两个壶准确得到targetCapacity
升。如果可以得到
targetCapacity
升水,最后请用以上水壶中的一或两个来盛放取得的targetCapacity
升水。你可以:
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水,直到装满或者倒空
2、接口描述
class Solution {
public:
bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
}
};
3、原题链接
二、解题报告
1、思路分析
由于每次倒出都是整壶的倒,倒入一定倒满则可以等效为直接倒了一壶
所以最终水量一定为sx+ty
根据初等数论的内容可以知道x,y最大公因数d可以表示为sx+ty=d并且d是能被这样表示的最小正整数,那么sx+ty=z成立当仅当z整除x和y最大公因数
2、复杂度
时间复杂度: O(1) 空间复杂度:O(1)
3、代码详解
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;
}
};