leetcode 三月每日一题 365.水壶问题(中等)
程序员文章站
2024-03-15 08:34:23
...
题目:
思想:
根据题意,每次可以进入如下的操作,分别是:
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水,直到装满或者倒空
上述三种操作分别对两个水壶进行,则一共有六种操作,如下所示:
- 装满水壶X
- 装满水壶Y
- 清空水壶X
- 清空水壶Y
- 把X的水倒入Y中,其中包含两种情况:(1). X的水倒入Y中还有剩余,(2). X的水倒入Y中没有剩余;
- 把Y的水倒入X中,其中也包含两种情况(1). Y的水倒入X中还有剩余,(2). Y的水倒入X中没有剩余
同时需要注意以下两点:
-
对以上六种情况进行搜索;对应于每一个当前的状态,都会有以上六种情况,我们用栈实现dfs,用队列实现bfs;个人理解dfs返回时的状态是最后一个状态,即和栈类似是先进后出,而bfs是先进先出类型;
-
同时需要设置一个集合保存已经访问过的状态,避免重复访问,陷入死循环。
两种代码,分别是深度优先搜索和广度优先搜索;
下面是dfs:
class Solution:
def canMeasureWater(self, x, y, z):
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
下面是bfs:
广度优先搜索
class Solution:
def canMeasureWater(self, x, y, z):
queue = [(0,0)]
#定义一个记录状态
self.state_queue = set()
while queue:
remain_x, remain_y = queue.pop(0)
if remain_x == z or remain_y == z or remain_y + remain_x == z:
return True
if (remain_x,remain_y) in self.state_queue:
continue
self.state_queue.add((remain_x,remain_y))
#获取当前状态的下一步的所有可能状态
#把X水壶装满
queue.append((x, remain_y))
#把y水壶装满
queue.append((remain_x, y))
#把x水壶清空
queue.append((0, remain_y))
#把y水壶清空
queue.append((remain_x, 0))
#把x的水倒入y中
queue.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))
#把y的水倒入x中
queue.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))
return False
总结:游戏类的搜索问题可以用dfs或者bfs求解,同时,dfs个bfs之间可以灵活变通,只需要在dfs中把栈变为队列既可变为bfs,同时在bfs中把队列变为栈,既可变为dfs。
上一篇: 二维数组的多种遍历方式