365. 水壶问题

题目描述

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

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

你可以：

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

示例 1:

输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true
解释：来自著名的 “Die Hard”

示例 2:

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

示例 3:

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

提示:

1 <= jug1Capacity, jug2Capacity, targetCapacity <= 10⁶

解法一：DFS

由于使用递归可能导致系统栈溢出，故下面代码使用栈来模拟递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


func min(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num < res {
            res = num
        }
    }
    return res
}
func canMeasureWater(jug1Capacity int, jug2Capacity int, targetCapacity int) bool {
    seen := make(map[[2]int]bool)
    var stack [][2]int
    stack = append(stack, [2]int{0, 0})
    for len(stack) > 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if seen[cur] {
            continue
        }
        seen[cur] = true
        remainX, remainY := cur[0], cur[1]
        if remainX == targetCapacity || remainY == targetCapacity ||
            remainX+remainY == targetCapacity {
            return true
        }
        // 将第一个水壶倒满
        stack = append(stack, [2]int{jug1Capacity, remainY})
        // 清空第一个水壶
        stack = append(stack, [2]int{0, remainY})
        // 将第一个水壶的水壶倒入第二个水壶，直至水倒完或者第二个水壶的水倒满
        stack = append(stack, [2]int{remainX - min(remainX, jug2Capacity-remainY),
            remainY + min(remainX, jug2Capacity-remainY)})
        // 将第二个水壶倒满
        stack = append(stack, [2]int{remainX, jug2Capacity})
        // 清空第二个水壶
        stack = append(stack, [2]int{remainX, 0})
        // 将第二个水壶的水倒入第一个水壶，直至水倒完或者第一个水壶的水倒满
        stack = append(stack, [2]int{remainX + min(remainY, jug1Capacity-remainX),
            remainY - min(remainY, jug1Capacity-remainX)})
    }

    return false
}

解法二：数学

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func canMeasureWater(jug1Capacity int, jug2Capacity int, targetCapacity int) bool {
    a, b :=jug1Capacity, jug2Capacity
    if a + b < targetCapacity {
        return false
    }
    if a == 0 || b == 0 {
        return targetCapacity == 0 || a + b == targetCapacity
    }
    for a % b > 0 {
        a, b = b, a % b
    }
    return targetCapacity % b == 0
}