首页 / PYTHON / LeetCode | 0365. Water and Jug Problem水壶问题【Python】

LeetCode | 0365. Water and Jug Problem水壶问题【Python】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode | 0365. Water and Jug Problem水壶问题【Python】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2261字，纯文字阅读大概需要4分钟。

内容图文

LeetCode 0365. Water and Jug Problem水壶问题【Medium】【Python】【BFS】【数学】

Problem

LeetCode

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

  • Fill any of the jugs completely with water.
  • Empty any of the jugs.
  • Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

问题

力扣

有两个容量分别为 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

思路

解法一

BFS

每次水壶都有三个操作：加满水、清空水、相互倒。
Python3代码
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        # solution one: BFS
        from collections import deque
        queue = deque([[0, 0]])
        visited = set([(0, 0)])

        while queue:
            cur_x, cur_y = queue.pop()
            if z in [cur_x, cur_y, cur_x + cur_y]:
                return True
            for item in [
                # x 加满水，y 加满水
                (x, cur_y), (cur_x, y),
                # x 清空水，y 清空水
                (0, cur_y), (cur_x, 0),
                # 把 x 壶的水灌进 y 壶，直至灌满或倒空
                (cur_x + cur_y - y, y) if cur_x + cur_y >= y else (0, cur_x + cur_y),
                # 把 X 壶的水灌进 Y 壶，直至灌满或倒空
                (x, cur_x + cur_y - x) if cur_x + cur_y >= x else (cur_x + cur_y, 0)]:
                if item not in visited:
                    queue.appendleft(item)  # 从队列左边加入元素
                    visited.add(item)
        return False
解法二

裴蜀定理

能否找到整数 a，b 使得方程 ax + by = z 有解。
有整数解时，当且仅当 z 是 a 和 b 的最大公约数 d 的倍数。
Python3代码
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        # solution two: 裴蜀定理
        import math
        if x + y < z:
            return False
        if x == z or y == z or x + y == z:
            return True
        return z % math.gcd(x, y) == 0

GitHub链接

Python

参考

暴力 + 数学

内容总结

以上是互联网集市为您收集整理的LeetCode | 0365. Water and Jug Problem水壶问题【Python】全部内容，希望文章能够帮你解决LeetCode | 0365. Water and Jug Problem水壶问题【Python】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/636922.html

来源：【匿名】