「LeetCode每日一题」——365. 水壶问题
365. 水壶问题
链接：https://leetcode-cn.com/problems/water-and-jug-problem/
难度：中等
题目
有两个容量分别为 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
思路
理解这道题的题意，有两个水壶，容量分别是X，Y，我们通过这两个水壶的操作可以做以下的事情：
给空壶加满水，总量为 X或者Y倒掉一壶满水，总量减少 X或者Y倒掉一壶不满的水，总量变成X或者Y或者0往不满的壶里加水，总量变为X或者Y或者X+Y从一个壶往另外一个壶倒水，总量不变
由上面五个情况可以看到，总量一定是ax+by(a,b为整数)，
所以z=ax+by
这里引入一个定理： 贝祖定理
贝祖定理：若x,y是整数,且gcd(x,y)=d，那么对于任意的整数a,b,ax+by都一定是d的倍数，特别地，一定存在整数a,b，使ax+by=d成立
由贝祖定理知道，z一定是x,y最大公约数的整数倍，这题就转换成了求判断z是否为x,y最大公约数的整数倍。
具体见解决方案。
方案代码
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原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/242.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」—— 1111. 有效括号的嵌套深度
1111. 有效括号的嵌套深度 链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-par…
-
「LeetCode每日一题」——836. 矩形重叠
836. 矩形重叠 链接：https://leetcode-cn.com/problems/rectangle-overlap/难度：简单 题目 矩形以列表 [x1, y1, x2…
-
「LeetCode每日一题」—— 1248. 统计「优美子数组」
1248. 统计「优美子数组」 链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays/难度：中等 题…
-
「LeetCode每日一题」—— LCOF.56 – I. 数组中数字出现的次数
LCOF.56 – I. 数组中数字出现的次数 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-d…
-
「LeetCode每日一题」—— 542. 01 矩阵
542. 01 矩阵 链接：https://leetcode-cn.com/problems/01-matrix/难度：中等 题目 点击原文链接跳转查看题目 思路 这道题求的就是每…
-
「LeetCode每日一题」——169. 多数元素
169. 多数元素 链接：https://leetcode-cn.com/problems/majority-element/难度：简单 题目 给定一个大小为 n 的数组，找到其中…
-
「LeetCode每日一题」—— LCCI.08.11. 硬币
LCCI.08.11. 硬币 链接：https://leetcode-cn.com/problems/coin-lcci/难度：中等 题目 点击原文链接跳转查看题目 思路 这题是完…
-
「LeetCode每日一题」—— 151. 翻转字符串里的单词
151. 翻转字符串里的单词 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string/难度：中等 题目 给定一个…
-
「LeetCode每日一题」—— 72. 编辑距离
72. 编辑距离 题目链接：https://leetcode-cn.com/problems/edit-distance/难度：困难 题目 给你两个单词 word1 和&…
-
「LeetCode每日一题」—— 42. 接雨水
42. 接雨水 链接：https://leetcode-cn.com/problems/trapping-rain-water/难度：困难 题目 给定 n 个非负整数表示…
您必须登录才能发表评论。