题目：
有两个容量分别为 *x*升 和* y*升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 *z*升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 *z升 *水。
你允许：
* 装满任意一个水壶
* 清空任意一个水壶
* 从一个水壶向另外一个水壶倒水，直到装满或者倒空
**示例 1:
输入: x = 3, y = 5, z = 4
输出: True
**示例 2:**
输入: x = 2, y = 6, z = 5
输出: False</pre>
题目的理解：
起初设想的解决方式：
（1）x和y的相差，求得所有相差的值，即每一个值与所有的值相减，直到不会产生新的值。
（2）得到的所有的值进行每一个值与所有值相加，得到一个集合B。
（3）集合B去除大于x加y的值，得到集合C。
（4）判断z是否在C中。
实现为：
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
attribute = {x, y}
pre_length = len(attribute)
while True:
minus_list = list(attribute)
for i in range(pre_length):
for j in range(i, pre_length):
minus = abs(minus_list[i] - minus_list[j])
minus_list.append(minus)
attribute = set(minus_list)
if pre_length == len(attribute):
break
else:
pre_length = len(attribute)
add_list = list(attribute)
for i in range(pre_length):
for j in range(i, pre_length):
add = add_list[i] + add_list[j]
add_list.append(add)
result_list = set(add_list)
result_list = filter(lambda s: s <= x + y, result_list)
return z in result_list
结果是计算超时。!_! 计算量太大了。
优化了方法：
（1）记录所有存在的可能，并用x和y对值进行判断，获取新值。
（2）仅仅对新值进行判断，如果值已经计算过，直接跳过。
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if z in [0, x, y, (x + y), abs(x - y)]:
return True
attribute = {x, y, abs(x - y)}
pre_length = len(attribute)
whole_nums = list(attribute)
while True:
minus_list = list(attribute)
new_set = list()
for i in range(pre_length):
temp = list()
value = minus_list[i]
if x > value:
temp.append(value + y)
if value > y:
new_set.append(value - y)
temp.append(value - y)
if x - value > y:
new_set.append(x - value + y)
temp.append(x - value + y)
temp.append(x - value + y + y)
else:
new_set.append(y - x + value)
temp.append(y - x + value)
temp.append(y - x + value + x)
if y > value:
temp.append(value + x)
if value > x:
new_set.append(value - x)
temp.append(value - x)
if y - value > x:
new_set.append(y - value + x)
temp.append(y - value + x)
temp.append(y - value + x + x)
else:
new_set.append(x - y + value)
temp.append(x - y + value)
temp.append(x - y + value + y)
if z in temp:
return True
attribute = list(filter(lambda x: x not in whole_nums, new_set))
whole_nums += attribute
if 0 >= len(attribute):
break
else:
pre_length = len(attribute)
return False
但是结果还是可悲的失败了，计算超时。!_!
还是看题解吧，伤心了！！！
python实现
解法1. 列举所有的操作的可能：
在任意一个时刻，我们可以且仅可以采取以下几种操作：
把 X 壶的水灌进 Y 壶，直至灌满或倒空；
把 Y 壶的水灌进 X 壶，直至灌满或倒空；
把 X 壶灌满；
把 Y 壶灌满；
把 X 壶倒空；
把 Y 壶倒空。
代码
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
stack = [(0, 0)]
self.seen = set()
while stack:
remain_x, remain_y = stack.pop()
if remain_x == z or remain_y == z or remain_x + remain_y == z:
return True
if (remain_x, remain_y) in self.seen:
continue
self.seen.add((remain_x, remain_y))
# 把 X 壶灌满。
stack.append((x, remain_y))
# 把 Y 壶灌满。
stack.append((remain_x, y))
# 把 X 壶倒空。
stack.append((0, remain_y))
# 把 Y 壶倒空。
stack.append((remain_x, 0))
# 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))
# 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))
return False
看解题思路非常的清晰易懂，将所有的可操作的步骤来一遍。
解法2. 最大公约数
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if x + y < z:
return False
if x == 0 or y == 0:
return z == 0 or x + y == z
return z % math.gcd(x, y) == 0
此题目的解法满足最大公约数的问题。
提交
还是要多做类似的题目才能想到这些方法，按自己的思想暴力破解，一般都会存在运算超时啊。
// END 只有勤奋才是对自己最好的嘉赏
网友评论