LeetCode 365. Water and Jug Problem

简介: 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?

v2-d193b7fab7f00c0c2b28ccee297cef3f_r.jpg

Description



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


思路


  • 因为每次都只能填满桶或清空桶,那么如果可以通过 x ,y 得到 z,就可以记 z = a * x + b * y,此时 a,b 为整数。
  • 根据裴蜀定理,z = a * x + b * y 有整数解时当且仅当 z 是 x 及 y 的最大公约数的倍数。
  • 那么我们只需要判断 z 是否是 x,y 的公因式即可。
  • 举例说明等式的含义,当 x = 3,y = 5,z = 4,时,有 4 = 5*2-3*2。正号表示填满桶,负号表示清空桶。
  1. 将容量为 5 的桶填满,全部倒入容量为 3 桶中(由于 3 小于 5,所以将 3 填满,倒出,将剩下的倒入),此时容量为 3 的桶剩余 2.
  2. 将容量为 5 的桶填满,将水倒入容量为 3 的桶,由于此时 3 桶中有水量为 2 的水,所以容量为 5 的桶倒出一份即可将 3 填满,此时 5 中剩余 4.
  • 再举一例,x = 13,y = 11, z = 1, 有 1 ==6 * 11 - 5 *13;
  1. 将 y 的 11 填满,全部倒入 x 的 13 中(此时 x 剩余 11);
  2. 将 y 的 11 填满,全部倒入 x 的 13 中(x 中原本剩余 11;将 y 的 11份水 中的 2 份倒入 x,将 x 全部倒出,再将 y 中的 9 份倒入 13; 此时 x 剩余 9);
  3. 将 y 的 11 填满,全部倒入 x 的 13 中(此时 x 剩余 7);
  4. 将 y 的 11 填满,全部倒入 x 的 13 中(此时 x 剩余 5);
  5. 将 y 的 11 填满,全部倒入 x 的 13 中(此时 x 剩余 3);
  6. 将 y 的 11 填满,全部倒入 x 的 13 中(此时 x 剩余 1);


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-06-13 11:03:29
# @Last Modified by:   何睿
# @Last Modified time: 2019-06-13 12:20:44
class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if z == 0 or (z <= x + y and z % self.__gcd(x, y) == 0):
            return True
        return False
    def __gcd(self, x: int, y: int) -> int:
        return x if y == 0 else self.__gcd(y, x % y)

源代码文件在 这里


目录
相关文章
|
6月前
|
人工智能 算法 ice
【2024美赛】D题(中英文):五大湖水资源问题Problem Problem D: Great Lakes Water Problem
【2024美赛】D题(中英文):五大湖水资源问题Problem Problem D: Great Lakes Water Problem
78 1
Leetcode 365. Water and Jug Problem
一句话理解题意:有容积为x和y升的俩水壶,能不能量出z升的水。 我刚开始看到这题,立马就想了下暴力搜索的可能性,但考虑了下数据大小,立马放弃这个暴力的想法,于是意识到肯定有比较简单的数学方法,其实我自己没想到,后来看还是看了别人的代码,很多博客都直接给出了解法, 但没介绍为什么能这么解。所以我决定解释下我自己的思路。
48 0
The Preliminary Contest for ICPC China Nanchang National Invitational A题 PERFECT NUMBER PROBLEM
The Preliminary Contest for ICPC China Nanchang National Invitational A题 PERFECT NUMBER PROBLEM
70 0
HDU-1057,A New Growth Industry(理解题意)
HDU-1057,A New Growth Industry(理解题意)