365. 水壶问题

[yankewei]

有两个容量分别为 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/water-and-jug-problem

解答

深度优先搜索（超时）

func canMeasureWater(x int, y int, z int) bool {
    stack := [][]int{{0,0}}
    seen := make(map[string]bool)
    for len(stack) != 0 {
        t := stack[0]
        stack = stack[1:]
        if t[0] == z || t[1] == z || t[0] + t[1] == z {
            return true
        }
        var b strings.Builder
        b.WriteString(strconv.Itoa(t[0]))
        b.WriteString(strconv.Itoa(t[1]))
        if _, e := seen[b.String()]; e {
            continue
        }
        seen[b.String()] = true

        // 把x清空
        stack = append(stack, []int{0, t[1]})
        // 把y清空
        stack = append(stack, []int{t[0], 0})
        // 把x装满
        stack = append(stack, []int{x, t[1]})
        // 把y装满
        stack = append(stack, []int{t[0], y})
        // 把y的水倒入x中，倒满或者y没有了
	if x-t[0] >= t[1] {
	    stack = append(stack, []int{t[0] + t[1], 0})
	} else {
	    stack = append(stack, []int{x, t[1] - (x - t[0])})
	}
	// 把x的水倒入y中，倒满或者x没有了
	if y-t[1] >= t[0] {
	    stack = append(stack, []int{0, t[1] + t[0]})
	} else {
	    stack = append(stack, []int{t[0] - (y - t[1]), y})
	}
    }
    return false
}

数学

具体可参考:https://leetcode-cn.com/problems/water-and-jug-problem/solution/shui-hu-wen-ti-by-leetcode-solution/

func canMeasureWater(x int, y int, z int) bool {
    if x + y < z {
        return false
    }
    if x == 0 || y == 0 {
        return z == 0 || x + y == z
    }
    return z % gcd(x, y) == 0
}

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