365.水壶问题

有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

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

你可以：

  • 装满任意一个水壶
  • 清空任意一个水壶
  • 从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1:

输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true

示例 2:

输入: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
输出: false

示例 3:

输入: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
输出: true

提示：

  • 1 <= jug1Capacity, jug2Capacity, targetCapacity <= 10^6

Related Topics

  • 深度优先搜索
  • 广度优先搜索
  • 数学

题目链接: link

解答

本题的难度是 Medium.

其实我们只需要考虑两个壶相加能否得到 targetCapacity, 因为如果只需要一个壶能满足的话把另一个倒空就行. 其次, 我们会发现, 每次加水时, 我们都可以简化为加量为 jug1Capacity 或 jug2Capacity 的水, 为了方便我们记 a=jug1Capacity, b=jug2Capacity, z=targetCapacity,我们可以考虑从以下几种情况(不考虑壶编号的话其实可能的就4种)

  • 情况1, 壶1满, 壶2满: 此时不能加水
  • 情况2, 壶1满, 壶2有水不满: 此时加水等价于从壶2空加满, 等同于加 b
  • 情况3, 壶1满, 壶2空: 此时加水等同于加 b
  • 情况4, 壶1有水不满, 壶2满: 与情况2 相同
  • 情况5, 壶1有水不满, 壶2有水不满: 按照题目不可能出现这种情况,因为倒水只会在一个空或者一个满的时候停
  • 情况6, 壶1有水不满, 壶2空: 壶1的水是壶2的倍数,此时如果对壶1加水等价于初始状态把壶1加满,等同于加了 a, 如果把壶2加满等于加了 b
  • 情况7, 壶1空, 壶2满: 等同于情况3
  • 情况8, 壶1空, 壶2有水不满: 等同于情况6
  • 情况9, 壶1空, 壶2空: 等同于加量为 a 或 b 的水

而清空水壶是类似的, 因此我们每次的操作都是对水量的变化为 a * x+b * y, 当没有倒出或加入时系数为0, 有可能出现一次倒出几倍的 b之类的, 倒出时系数为负,加入时为正, 所以会有个系数, 那么其实就是希望从0开始,进行操作k次, 每次操作对水量的变化为 a * x_i+b* y_i, 那么其实会发现, 把 k 次操作的变化量加起来为 a*(x_1+...+x_k)+b*(y_1+...+y_k), 还是一个 ax+by 的格式, 我们希望判断 ax+by=z 是否存在整数解(因为要求倒入倒出是整数嘛), 这时候我们就发现这就是 Bézout's identity.

即: 若 x, y 为整数, 且有 d=gcd(a,b), 那么对于任意的整数 x, y, 都有: ax+by 的值都一定是 d 的倍数, 其中 gcd(a,b) 表示 a, b 的最大公因数. 因此有一个推论, 如果 a, b 互质, 那么一定存在整数 x, y 使得 ax+by=1.

知道了上面这个结论, 那我们只需要求 a, b 的最大公因数 d, 然后看 z 是不是 d 的倍数就行了. 至于求最大公因数使用辗转相除法就行.

代码如下:

class Solution {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (jug1Capacity + jug2Capacity < targetCapacity){return false;}
        if (jug1Capacity > jug2Capacity){
            return targetCapacity % gcd(jug1Capacity,jug2Capacity) == 0;
        }else {
            return targetCapacity % gcd(jug2Capacity,jug1Capacity) == 0;
        }
    }

    private int gcd(int a, int b){
        if (a%b == 0){return b;}
        return gcd(b, a%b);
    }
}

时间效率成功击败 100%, 这题的标签还有 DFS 和 BFS, 应该不用数学的话就是用这两种方法, 下次试试不用数学的方法. 应该可以把搜索过的存起来, 最多也就 (a+1)(b+1) 种情况.