算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！今天和大家聊的问题叫做 水壶问题，我们先来看题面：https://leetcode-cn.com/problems/water-and-jug-problem/You are given two jugs with capacities jug1Capacity and jug2Capacity liters. There is an infinite amount of water supply available. Determine whether it is possible to measure exactly targetCapacity liters using these two jugs.If targetCapacity liters of water are measurable, you must have targetCapacity liters of water contained within one or both buckets by the end.Fill any of the jugs with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full, or the first jug itself is empty.
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例
示例 1:
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
解题
这是一道数学题了。水量 z 是两个水壶容量的最大公约数的倍数，且 z <= x+yclass Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(z > x+y)
return false;
int r;
while(y != 0)//循环结束后，最大公约数是x
{
r = x%y;
x = y;
y = r;
}
return (z==0 || z%x == 0);
}
};
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
