链接
https://leetcode-cn.com/problems/water-and-jug-problem/
耗时
解题:1 h+
题解:29 min
题意
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。现有一下 3 种操作:
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水,直到装满或者倒空
问能否只通过上述 3 中操作得到恰好 z升 的水,最后用以上水壶中的一或两个来盛放取得的 z升 水。
思路
模拟一下样例,再次读题,可以发现题目可以转化成如下问题:
“若
a
x
+
b
y
=
z
(
0
≤
z
≤
x
+
y
)
ax+by=z(0\leq z \leq x+y)
ax+by=z(0≤z≤x+y),当
x
,
y
,
z
x,y,z
x,y,z 成什么关系时,
a
,
b
a,b
a,b 一定有整数解?”
这个问题还是太抽象,多模拟几组数据,仔细观察可以发现:当
x
,
y
x,y
x,y 互质时,可以得到
[
0
,
x
+
y
]
[0, x+y]
[0,x+y] 之间的任意一个
z
z
z;而
x
,
y
x,y
x,y 不互质时,
z
z
z 只能得到
x
,
y
x,y
x,y 最大公约数的倍数。
详细说明:假设
a
,
b
a,b
a,b 是整数,当
x
,
y
x,y
x,y 互质时,通过调整系数
a
,
b
a,b
a,b 一定能得到
a
x
+
b
y
=
1
ax+by=1
ax+by=1,故而可以得到
[
0
,
x
+
y
]
[0, x+y]
[0,x+y] 之间的任意一个数。当
x
,
y
x,y
x,y 不互质时,通过调整系数
a
,
b
a,b
a,b 在范围内排除
0
0
0 外最小只能得到
a
x
+
b
y
=
g
c
d
(
x
,
y
)
ax+by=gcd(x,y)
ax+by=gcd(x,y)。所以当
x
,
y
x,y
x,y 一定时,可以归结为
a
x
+
b
y
ax+by
ax+by 只能得到
g
c
d
(
x
,
y
)
gcd(x,y)
gcd(x,y) 的倍数(这其实是贝祖定理,孤陋寡闻了)。也就是说当
z
z
z 能整除
g
c
d
(
x
,
y
)
gcd(x,y)
gcd(x,y) 时,
a
,
b
a,b
a,b 一定有整数解。
然而还有一些特殊情况需要处理:
- 根据实际问题
z
>
x
+
y
z > x+y
z>x+y 一定装不下
-
z
=
0
z = 0
z=0 一定正确
-
x
=
0
x=0
x=0 或
y
=
0
y=0
y=0 时,只能得到
0
0
0 或另一只水壶的容量的水。
AC代码
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(z > x+y) return false;
if(z == 0) return true;
if(x == 0 || y == 0) return z%max(x,y) == 0;
return z%__gcd(x,y) == 0;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)