365. 水壶问题

2020-03-22  本文已影响0人  Chiduru

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

如果可以,最后请用以上水壶中的一或两个来盛放取得的 *z升 *水。

你允许:

示例1:
输入: x = 3, y = 5, z = 4
输出: True

示例2:
输入: x = 3, y = 5, z = 4
输出: True

【Idea】
先考虑特殊情况:
z==0(直接输出true) / x+y <z (直接凑不了)/ x, y有一方=0, 只能靠另一方凑
然后进入正题。
目标函数: ax+by=z
假设x<=y,那么a可以取负值,对应操作:x壶灌满水后倒入y壶里 | 0<=b<=1
那么操作主要是:

  1. 灌满x, 结束;=> +x
  2. 灌满y, 结束;=> +y
  3. 灌满x后倒入y(y未满)=> +(y-x)
    结合以上三种增量,把y-x 变换成: -x+y就是ax+by(a=-1, b=1)的一个示例。
    因此可以套入贝祖定理(若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立)
    所以最后就是求x,y的最小公约数,用z整除求解即可。

(其实最开始写的时候也不知道这个定理,就是感觉x, y,和y-x求个最小公约数就OK了。 看题解才知道这还是个定理,还挺没文化的hh

【Solution】

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if z == 0:
            return True
        if x+y < z:
            return False
        if min(x, y)==0 and max(x, y) != z:
            return False
        gongyue = 1
        for i in range(1, min(x, y)+1):
            if x%i == 0 and y%i == 0:
                gongyue = i
        if z % gongyue == 0:
            return True
        else:
            return False

上一篇 下一篇

猜你喜欢

热点阅读