点击此处快速跳到程序部分

水壶问题

有两个容量分别为 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
2
3
4
5
6
7
8
9
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每次的状态有:

注意:下面的每一步都是注定的,即‘只有这样操作才对目标的获得有意义’,
目标是什么?目标就是每次操作都要‘利用容量差产生更多样的容量的水’。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 时可当做【第一种情况】 

初步的编码实现

由上述思路作指导,很自然的想到了使用递归这种方式,于是有了以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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));
}
}

补全思路得到新的实现

上述代码不出意外的还是没过,解答出错,为什么呢,原来是原先的思路有问题,思考不全面,如下:

1
2
3
4
5
6
7
8
9
10
11
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 如果大杯子剩余的比小杯子容量大,怎么处理
答:此时应不同于一般情况,一般情况是大的里的剩余是比小的容量小
'所以剩余水可以倒入小的,但此时无法将大杯子的剩余水倒入小杯子,
因为会溢出,那么应该如何操作呢,本着利用‘容量差’的原则,所以:

需要将小杯子用大杯子的剩余水倒满,此时大杯子的水仍有剩余,
如果此时剩余的水还比小杯子的大,那么先倒空小杯子,
然后继续用剩余的水装满小杯子,直到剩余的水 小于小杯子容量,

此时停止,因为此时剩余的水可以倒入小杯子了,所以又回到了第一种情况。

下面,我们按刚才说的思路将先前的例子列完:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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!

<< 更多精彩尽在『程序萌部落』>>
<< https://www.cxmoe.com >>

如何避免递归的栈溢出

对于溢出时的测试用例:22003,31237,137,在我本机跑时递归了九千次左右就溢出停止了,但对于一般的小的测试用例,答案已经都是正确的了,所以此时的思路应是正确的,只是实现形式有问题,需要优化!

重新对上一章节中说到的例子进行考究,发现真正有用的(跟Z比较判断的)状态其实只有如下:

1
2
3
4
5
6
7
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循环来完成,优化后的代码:
【情况一】:大水杯里的剩水不断的增加,直到增加到剩水大于小水杯容量;
【情况二】:大水杯剩水不断的减少,直到剩水小于小水杯的容量;
再次明确:情况一时小水杯的容量 >= 大水杯的剩水; 情况二时小水杯的容量 < 大水杯的剩水;
注意:
对于每次迭代,都对两种情况分别对待,然后进行下一次迭代,此时迭代是靠递归驱动的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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); //情况一
}
}
}

终极优化,递归的转化

上述代码仍然存在栈溢出的错误,所以还是递归的锅,显然,不是题目的测试样例刁钻,而是有些情况就是需要迭代几万次,即用递归是错误的实现方式。故转念一想,如何将递归转化为循环?

1
2
3
4
5
6
7
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

在此回顾上述的内容,发现其实代码中的递归已经没有复杂的处理逻辑,且退化成了驱动迭代的一种结构,所以显然可以改成循环。由于原递归可以连续执行,所以转为循环理所应当的 最外层是 while(true)来制造连续迭代,然后循环的退出可以用return 或者break都可以,对于两种情况的处理还是要分别采用不同的实现,综上,去掉递归改用循环的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
}
}
}

精益求精

上述代码终于是得到了绿绿的通过,然而其执行速度却是最慢的,查看代码其实发现在判断停止的条件的语句上过于冗余了,然后有些变量还做了无畏的赋值,于是继续精简,最后得到如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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函数。但一般的小白(比如我)是很难将这个问题抽象成求解最大公约数的,所以我的思路其实更笨一点,但也更符合思考的逻辑。
下面是第一梯队的样例代码和解读。

1
2
3
4
5
6
7
8
9
10
11
12
13
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。虽然只是一道普通的题目,但以前还真没真真正正的不借助参考的独立思考过这样难度的题目,所以就在这里啰嗦了一大堆,看来以后还是得多独立思考,正应那句话:“不是不会做,而是不去想” 啊!



😒 留下您对该文章的评价 😄



 评论




全站共计 313.7k 字,自豪地使用 Volantis 主题

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议