［抄题］：
简而言之：只能对 杯子中全部的水/容量-杯子中全部的水进行操作
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:
- Fill any of the jugs completely 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.
Example 1: (From the famous “Die Hard” example)
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
ab直接倒入c/a+b=c
［思维问题］：
没啥思路：倒水问题其实就是倍数问题，可以从gcd角度想想。
［英文数据结构或算法，为什么不用别的数据结构或算法］：
［一句话思路］：
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- gcd最后b = 0了，因此要求返回a
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
倒水问题是倍数问题，倍数问题想想gcd
［复杂度］：Time complexity: O(n) Space complexity: O(1)
［算法思想：迭代/递归/分治/贪心］：
［关键模板化代码］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
[是否头一次写此类driver funcion的代码] ：
[潜台词] ：
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
//exit case
if (x + y < z) return false; //corner case
if (x == z || y == z || x + y == z) return true; //calculate
return z % gcd(x, y) == 0;
} public int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}
