我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 365. 水壶问题
题目
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)--电影《龙胆虎威》的一段剧情
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
解题思路
思路1-我无法证明的一生二、二生四、四生万物算法...
- 我的想法：x、y、x+y、|x-y|是四个基本数（去重后可能更少），若再更相递减能再获得一个不重复数（总数大于4个），说明由xy能获得的z范围是[1,x+y],否则z的值只能由四个基本数组合获得；
- 按想法实现的算法通过了，效率不高，但是我好像不会证明这个东西；
- 看了官解，感觉我这个跟贝祖定理有点靠近...有可以证明我这个想法数学实现的大佬麻烦指教一下；
思路2-贝祖定理+GCD（算法思路说明来自LeetCode官方解答）
预备知识：贝祖定理
我们认为，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。
你可能认为这有问题：如果往一个不满的桶里放水，或者把它排空呢？那变化量不就不是 x 或者 y 了吗？接下来我们来解释这一点：
-
首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的；
-
其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；
-
再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。
因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a, b，使得
- ax + by = z
而只要满足 z ≤ x+y，且这样的 a,b 存在，那么我们的目标就是可以达成的。这是因为：
-
若 a≥0,b≥0，那么显然可以达成目标。
-
若 a<0，那么可以进行以下操作：
-
往 y 壶倒水；
-
把 y 壶的水倒入 x 壶；
-
如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。
-
重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。
- 若 b<0，方法同上，x 与 y 互换。
而贝祖定理告诉我们，ax+by=z 有解当且仅当 z 是 x, y 的最大公约数的倍数。因此我们只需要找到 x,y 的最大公约数并判断 z 是否是它的倍数即可。
复杂度分析
时间复杂度：O(log(min(x,y)))，取决于计算最大公约数所使用的辗转相除法。
空间复杂度：O(1)，只需要常数个变量。
总结：数学很强大，数学是算法的基石啊...
算法源码示例
package leetcode;
import java.util.Iterator;
import java.util.TreeSet;
/**
* @author ZhouJie
* @date 2020年3月21日 下午1:59:07
* @Description: 365. 水壶问题
*
*/
public class LeetCode_0365 {
}
class Solution_0365 {
/**
* @author: ZhouJie
* @date: 2020年3月21日 下午2:39:59
* @param: @param x
* @param: @param y
* @param: @param z
* @param: @return
* @return: boolean
* @Description: 1-除去xy本身，x y互相加减及递归一次的加减值组成的set，
* 若set总数大于4说明可以生成1~x+y之间的任意z数，否则z只能是set的某两个散列数的组合
* ::这个无法证明...但是算法通过了，虽然效率不高。
*
*/
public boolean canMeasureWater_1(int x, int y, int z) {
if (z == 0 || z == x || z == y) {
return true;
}
if (z > (x + y)) {
return false;
}
TreeSet<Integer> treeSet = new TreeSet<Integer>();
int a = Math.abs(x + y);
int b = Math.abs(x - y);
int c = Math.abs(x - b);
int d = Math.abs(y - b);
treeSet.add(a);
treeSet.add(b);
treeSet.add(c);
treeSet.add(d);
treeSet.add(x);
treeSet.add(y);
treeSet.remove(0);
int min = treeSet.first();
int size = treeSet.size();
if (size > 4) {
return true;
} else if (z < min) {
return false;
} else {
Iterator<Integer> ite = treeSet.iterator();
while (ite.hasNext()) {
if (treeSet.contains(z - ite.next().intValue())) {
return true;
}
}
return false;
}
}
/**
* @author: ZhouJie
* @date: 2020年3月21日 下午3:16:54
* @param: @param x
* @param: @param y
* @param: @param z
* @param: @return
* @return: boolean
* @Description: 2-贝祖定理+GCD
*
*/
public boolean canMeasureWater_2(int x, int y, int z) {
if (z == 0 || z == x || z == y) {
return true;
} else if (z > (x + y)) {
return false;
} else {
return z % gcd(x, y) == 0;
}
}
private int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
}