Skip to content

Latest commit

 

History

History
213 lines (145 loc) · 5.76 KB

365.water-and-jug-problem.md

File metadata and controls

213 lines (145 loc) · 5.76 KB
Raw

题目地址

https://leetcode.com/problems/water-and-jug-problem/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

BFS（超时）

前置知识

  • BFS
  • 最大公约数

思路

两个水壶的水我们考虑成状态，然后我们不断进行倒的操作，改变状态。那么初始状态就是（0 0） 目标状态就是 （any, z）或者 (z, any)，其中any 指的是任意升水。

已题目的例子，其过程示意图，其中括号表示其是由哪个状态转移过来的：

0 0 3 5(0 0) 3 0 (0 0 )0 5(0 0) 3 2(0 5) 0 3(0 0) 0 2(3 2) 2 0(0 2) 2 5(2 0) 3 4(2 5) bingo

代码

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x + y < z:
            return False
        queue = [(0, 0)]
        seen = set((0, 0))

        while(len(queue) > 0):
            a, b = queue.pop(0)
            if a ==z or b == z or a + b == z:
                return True
            states = set()

            states.add((x, b))
            states.add((a, y))
            states.add((0, b))
            states.add((a, 0)) 
            states.add((min(x, b + a), 0 if b < x - a else b - (x - a))) 
            states.add((0 if a + b < y else a - (y - b), min(b + a, y)))
            for state in states:
                if state in seen:
                    continue;
                queue.append(state)
                seen.add(state)
        return False

复杂度分析

  • 时间复杂度：由于状态最多有$O((x + 1) * (y + 1))$ 种，因此总的时间复杂度为$O(x * y)$。
  • 空间复杂度：我们使用了队列来存储状态，set 存储已经访问的元素，空间复杂度和状态数目一致，因此空间复杂度是$O(x * y)$。

上面的思路很直观，但是很遗憾这个算法在 LeetCode 的表现是 TLE(Time Limit Exceeded)。不过如果你能在真实面试中写出这样的算法，我相信大多数情况是可以过关的。

我们来看一下有没有别的解法。实际上，上面的算法就是一个标准的 BFS。如果从更深层次去看这道题，会发现这道题其实是一道纯数学问题，类似的纯数学问题在 LeetCode 中也会有一些，不过大多数这种题目，我们仍然可以采取其他方式 AC。那么让我们来看一下如何用数学的方式来解这个题。

数学法 - 最大公约数

思路

这是一道关于数论的题目，确切地说是关于裴蜀定理（英语：Bézout's identity）的题目。

摘自wiki的定义：

对任意两个整数 a、b，设 d是它们的最大公约数。那么关于未知数  x和  y的线性丢番图方程（称为裴蜀等式）：

ax+by=m

有整数解  (x,y) 当且仅当  m是  d的整数倍。裴蜀等式有解时必然有无穷多个解。

因此这道题可以完全转化为裴蜀定理。还是以题目给的例子x = 3, y = 5, z = 4，我们其实可以表示成3 * 3 - 1 * 5 = 4, 即3 * x - 1 * y = z。我们用a和b分别表示3 升的水壶和5升的水壶。那么我们可以：

  • 倒满a（1）
  • 将a倒到b
  • 再次倒满a（2）
  • 再次将a倒到b（a这个时候还剩下1升）
  • 倒空b（-1）
  • 将剩下的1升倒到b
  • 将a倒满（3）
  • 将a倒到b
  • b此时正好是4升

上面的过程就是3 * x - 1 * y = z的具体过程解释。

也就是说我们只需要求出x和y的最大公约数d，并判断z是否是d的整数倍即可。

代码

代码支持：Python3，JavaScript

Python Code：

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x + y < z:
            return False

        if (z == 0):
            return True

        if (x == 0):
            return y == z

        if (y == 0):
            return x == z

        def GCD(a, b):
            smaller = min(a, b)
            while smaller:
                if a % smaller == 0 and b % smaller == 0:
                    return smaller
                smaller -= 1

        return z % GCD(x, y) == 0

JavaScript：

/**
 * @param {number} x
 * @param {number} y
 * @param {number} z
 * @return {boolean}
 */
var canMeasureWater = function(x, y, z) {
  if (x + y < z) return false;

  if (z === 0) return true;

  if (x === 0) return y === z;

  if (y === 0) return x === z;

  function GCD(a, b) {
    let min = Math.min(a, b);
    while (min) {
      if (a % min === 0 && b % min === 0) return min;
      min--;
    }
    return 1;
  }

  return z % GCD(x, y) === 0;
};

实际上求最大公约数还有更好的方式，比如辗转相除法：

def GCD(a, b):
    if b == 0: return a
    return GCD(b, a % b)

复杂度分析

  • 时间复杂度：$O(log(max(a, b)))$
  • 空间复杂度：空间复杂度取决于递归的深度，因此空间复杂度为 $O(log(max(a, b)))$

关键点分析

  • 数论
  • 裴蜀定理

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经接近30K star啦。

大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解