两个水壶相互倒水—水壶问题
水壶问题
有两个容量分别为 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第一印象
乍一看这道题目和题目的示例，以为直接用条件判断就能搞定，于是立刻写了如下非常错误的代码：
public boolean canMeasureWater(int x, int y, int z) {
if( (0.5*x + 0.5*y == z)||(x + y == z)||
(0.5*x + y == z)||(x + 0.5*y == z)||
(x + x == z)||(y + y == z) ){
return true;
}else{
return false;
}
}当然执行的结果是错误的，这里主要烦了两个重要的错误：
- 杯子只能倒空或倒满，不能倒一半（像脑筋急转弯那样）
- 两个杯子，当然可以让水从一个倒入另一个
从上述一开始遇到的错误，可以引出此题的关键：
- 需要不断将水倒来倒去，从而利用容量差得到更多样的容量的水
- 为了减少实现复杂程度，输入的x，y应该按指定顺序，如前小后大
- 对特定情况，能提前排除就提前排除，比如（0,1,2）
进入正题
首先，是问题的抽象，该问题可以转化为问一个三元组r(x,y,z)，按一定规则对x，y进行运算，规则就是：
- x，y只能被赋值不比自身大的数，
- x，y运算过程中，只要有一个状态，或x，或y，或x+y，等于z，则问题得解
- 问题无解的条件？
然后，由特殊推普通，实际计算几个例子，看看有什么规律，杯子x，y每次的状态有：
注意：下面的每一步都是注定的，即‘只有这样操作才对目标的获得有意义’，
目标是什么？目标就是每次操作都要‘利用容量差产生更多样的容量的水’。x=4 y=5
4 5 //初始状态
0 5 //小的倒空，大的倒满【问题I】
4 5-(4-0)=1 //大的将小的倒满，大的会剩余，这里剩余 1
0 1 //小的倒空
1 0 //大的中的剩余倒入小的
1 5 //大的倒满
4 5-(4-1)=2 //大的继续将小的倒满，大的还会剩余，这里剩余 2
0 2 //往复上述操作
2 0
2 5
4 5-(4-2)=3
0 3
3 0
3 5
4 5-(4-3)=4 //x==y，后续会再重新回到开始状态，故这是终止状态【问题II】
0 4
4 0
4 5问题I，为什么小的倒空大的倒满？
因为如果相反，小的满，大的空，水只能从小杯子倒入大杯子，
且小杯子无剩余，故没有利用到容量差，所以这种顺序的操作时无意义的。
问题II，如果x和y不相等，且y>x即剩余的水多于小杯子的容量怎么办？
答：此时归结为【第二种情况】后续会讲到，所以当 y<=x 时可当做【第一种情况】 初步的编码实现
由上述思路作指导，很自然的想到了使用递归这种方式，于是有了以下代码：
class Solution {
public int zx;
public int sm;
public int lg;
public boolean MK = false;
public boolean canMeasureWater(int x, int y, int z) {
if(z == x||z == y||z==x+y||z==0) {
return true;
}
if(z > x && z> y && z>(x+y)){
return false;
}
zx = z;
sm = x;
lg = y;
if(x>y){
int tp = sm;sm = lg;lg = tp;
}else{
recursion(sm,lg-(sm-0));
}
return MK;
}
public void recursion(int x, int y){
if(zx == x+y || zx == x || zx==y)
MK = true;
if(x <= y||y>zx){
if(!MK) MK = false;
return;
}
x = 0;
if(zx == x+y || zx == x || zx==y)
MK = true;
int t = x;x = y;y = t;
x = x;
y = lg;
if(zx == x+y || zx == x || zx==y)
MK = true;
recursion(sm,lg-(sm-x));
}
}补全思路得到新的实现
上述代码不出意外的还是没过，解答出错，为什么呢，原来是原先的思路有问题，思考不全面，如下：
x=4 y=7
4 7
0 7
4 7-(4-0)=3
0 3
3 0
3 7
4 7-(4-3)=6 //上述步骤同先前同理
0 6 //但此时出现 大的里的剩余 比小的容量还大【问题I】
? ?
...问题I 如果大杯子剩余的比小杯子容量大，怎么处理
答：此时应不同于一般情况，一般情况是大的里的剩余是比小的容量小
'所以剩余水可以倒入小的，但此时无法将大杯子的剩余水倒入小杯子，
因为会溢出，那么应该如何操作呢，本着利用‘容量差’的原则，所以：
需要将小杯子用大杯子的剩余水倒满，此时大杯子的水仍有剩余，
如果此时剩余的水还比小杯子的大，那么先倒空小杯子，
然后继续用剩余的水装满小杯子，直到剩余的水 小于小杯子容量，
此时停止，因为此时剩余的水可以倒入小杯子了，所以又回到了第一种情况。下面，我们按刚才说的思路将先前的例子列完：
x=4 y=7
4 7
0 7
4 7-(4-0)=3
0 3
3 0
3 7
4 7-(4-3)=6 //此时，按刚才的思路【第二种情况】继续
0 6 //小杯子倒空
4 6-4=2 //用大杯子剩余的水倒满小杯子，大杯子还剩余 2
0 2 //此时回归【第一种情况】
2 0
2 7
4 7-(4-2)=5 //此时，又回到【第二种情况】
0 5
4 5-4=1 //此时又回归【第一种情况】
0 1
1 0
1 7
4 7-(4-1)=4 //此时xy相等，如果继续，则状态回归初始，故此时终止
上述例子即完整的展现了正确的迭代步骤，即需要分为【两种情况】，所以在先前递归形式的基础上，对每次的迭代中的 x y的大小分情况进入不同的迭代入口即可。然而这一新的实现仍然出错误了：Stack Overflow！
如何避免递归的栈溢出
对于溢出时的测试用例：22003,31237,137，在我本机跑时递归了九千次左右就溢出停止了，但对于一般的小的测试用例，答案已经都是正确的了，所以此时的思路应是正确的，只是实现形式有问题，需要优化！
重新对上一章节中说到的例子进行考究，发现真正有用的（跟Z比较判断的）状态其实只有如下：
x=4 y=7
4 7-(4-0)=3 //【情况一】
4 7-(4-3)=6
4 6-4=2 //【情况二】
4 7-(4-2)=5
4 5-4=1
4 7-(4-1)=4优化情况二：按先前的思路可知，情况二其实不需要迭代操作，其就是在大杯子剩余水多于小杯子容量时，就拿小杯子每次都去装大杯子的剩余水，直到大杯子中剩余的水小于小杯子的容量，抽象为数学运算：
- 取余 y % x == c
实现上，由于需要中间的每个状态（和z比较），所以可以用while循环来完成，优化后的代码：
【情况一】：大水杯里的剩水不断的增加，直到增加到剩水大于小水杯容量；
【情况二】：大水杯剩水不断的减少，直到剩水小于小水杯的容量；
再次明确：情况一时小水杯的容量 >= 大水杯的剩水； 情况二时小水杯的容量 < 大水杯的剩水；
注意：
对于每次迭代，都对两种情况分别对待，然后进行下一次迭代，此时迭代是靠递归驱动的。
class Solution {
public static int zx;
public static int sm;
public static int lgt;
public static boolean MK = false;
public static boolean canMeasureWater(int x, int y, int z) {
sm = x; lgt = y;
if(x > y){
sm = y; lgt = x;
}
zx = z;
recursion(lgt);
return MK;
}
//static int cnt = 0;
public static void recursion(int rs) {
if(sm + rs == zx|| sm + lgt == zx|| sm + rs == zx|| sm == zx|| rs == zx|| zx == 0){
MK = true;
return;
}
if(rs <= 0){
if(!MK) MK = false;
return;
}
if(sm <= rs){
int tmp = rs;
for(int i = 1; tmp >= sm;i ++){
tmp = tmp - sm;
}
recursion(tmp); //情况一
}else{
int tmp = rs;
for(int i = 1; tmp < sm;i ++){
tmp = lgt - (sm - tmp);
}
recursion(tmp); //情况一
}
}
}终极优化，递归的转化
上述代码仍然存在栈溢出的错误，所以还是递归的锅，显然，不是题目的测试样例刁钻，而是有些情况就是需要迭代几万次，即用递归是错误的实现方式。故转念一想，如何将递归转化为循环？
1234567 | x=4 y=74 7-(4-0)=3 //【情况一】4 7-(4-3)=6 4 6-4=2 //【情况二】 4 7-(4-2)=5 4 5-4=1 4 7-(4-1)=4 |
|---|
在此回顾上述的内容，发现其实代码中的递归已经没有复杂的处理逻辑，且退化成了驱动迭代的一种结构，所以显然可以改成循环。由于原递归可以连续执行，所以转为循环理所应当的 最外层是 while(true)来制造连续迭代，然后循环的退出可以用return 或者break都可以，对于两种情况的处理还是要分别采用不同的实现，综上，去掉递归改用循环的代码：
public static boolean canMeasureWater(int x, int y, int z) {
if(z == 0) return true;
if((x == 0 || y == 0))
return (x + y == z);
if(x > y)
int t = x; x = y; y = t;
int rs = y;
while(true){
if(x + rs == z|| x + y == z|| x + rs == z|| x == z|| rs == z|| z == 0)
return true;
if(rs <= 0)
return false;
int tmp = rs;
if(x <= rs){
while(tmp >= x){
tmp = tmp - x;
//System.out.println((++cnt)+"\tb\tr("+x+","+tmp+")"+"\t"+z);
if(x + tmp == z|| x + y == z|| x + tmp == z|| x == z|| tmp == z|| z == 0){
return true;
}
}
rs = tmp;
}else{
while(tmp < x){
tmp = y - (x - tmp);
if(x + tmp == z|| x + y == z|| x + tmp == z|| x == z|| tmp == z|| z == 0){
return true;
}
}
rs = tmp;
}
}
}精益求精
上述代码终于是得到了绿绿的通过，然而其执行速度却是最慢的，查看代码其实发现在判断停止的条件的语句上过于冗余了，然后有些变量还做了无畏的赋值，于是继续精简，最后得到如下代码：
public static boolean canMeasureWater(int x, int y, int z) {
if(z == 0|| x + y == z)
return true;
if((x == 0 || y == 0))
return (x + y == z);
if(x > y){
int t = x; x = y; y = t;
}
int rs = y;
while(true){
if(rs <= 0)
return false;
if(x <= rs){
while(rs >= x){
rs = rs - x;
if( x + rs == z|| rs == z)
return true;
}
}else{
while(rs < x){
rs = y - (x - rs);
if( x + rs == z|| rs == z)
return true;
}
}
}
}上述代码的执行速度得到了不少的提升，由原先的21ms提升到了 8ms，如下图所示，现在下图提交的所有代码中，我的代码还成了第二个和第五个柱状图即8ms和21ms的样例程序，想想还有点小激动。
附第一梯队代码
当然，对于第一梯队的代码，使用到了 gcd() 函数对最大公约数进行求解，技巧性比较强，速度当然也快。相比之下，我这里其实相当于实现了一下gcd函数。但一般的小白（比如我）是很难将这个问题抽象成求解最大公约数的，所以我的思路其实更笨一点，但也更符合思考的逻辑。 下面是第一梯队的样例代码和解读。
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (z==x+y || z==x || z==y || z==0)
return true;
if (x==0 || y==0 || z>x+y || z%gcd(x, y)!= 0)
return false;
return true;
}
private int gcd(int a, int b){
return b == 0? a : gcd(b, a%b);
}
}此种题解的解题思路，转自网络
这道问题其实可以转换为有一个很大的容器，我们有两个杯子，容量分别为x和y，问我们通过用两个杯子往里倒水，和往出舀水，问能不能使容器中的水刚好为z升。那么我们可以用一个公式来表达： z = m x + n y 其中m，n为舀水和倒水的次数，正数表示往里舀水，负数表示往外倒水，那么题目中的例子可以写成: 4 = (-2) 3 + 2 5，即3升的水罐往外倒了两次水，5升水罐往里舀了两次水。那么问题就变成了对于任意给定的x,y,z，存不存在m和n使得上面的等式成立。根据裴蜀定理，ax + by = d的解为 d = gcd(x, y)，那么我们只要只要z % d == 0，上面的等式就有解，所以问题就迎刃而解了，我们只要看z是不是x和y的最大公约数的倍数就行了，别忘了还有个限制条件x + y >= z，因为x和y不可能称出比它们之和还多的水。
由于这道题前前后后想了两天多，且期间不断地修正自己的想法，修改对应的实现，最后AC。虽然只是一道普通的题目，但以前还真没真真正正的不借助参考的独立思考过这样难度的题目，所以就在这里啰嗦了一大堆，看来以后还是得多独立思考，正应那句话：“不是不会做，而是不去想” 啊！