leetcode365 水壺問題

有兩個容量分別為 x升 和 y升 的水壺以及無限多的水。請判斷能否通過使用這兩個水壺，從而可以得到恰好 z升 的水？

如果可以，最後請用以上水壺中的一或兩個來盛放取得的 z升 水。

你允許：

• 裝滿任意一個水壺
• 清空任意一個水壺
• 從一個水壺向另外一個水壺倒水，直到裝滿或者倒空

示例 1: (From the famous "Die Hard" example)

<code>輸入: x = 3, y = 5, z = 4
輸出: True
/<code>

示例 2:

<code>輸入: x = 2, y = 6, z = 5
輸出: False/<code>

方法1，最大公約數

<code>public boolean canMeasureWater(int x, int y, int z) {
    if (z == 0) return true;
    if (x + y < z) return false;

    int big = Math.max(x, y);
    int small = x + y - big;

    if (small == 0) return big == z;


    while (big % small != 0) {
        int temp = small;
        small = big % small;
        big = temp;
    }
    return z % small == 0;
}/<code>

方法2，BFS搜索

<code>public boolean canMeasureWater_BFS(int x, int y, int z) {
    if (z < 0 || z > x + y) {
        return false;
    }
    Set<integer> set = new HashSet<>();
    Queue<integer> q = new LinkedList<>();
    q.offer(0);
    while (!q.isEmpty()) {
        int n = q.poll();
        if (n + x <= x + y && set.add(n + x)) {
            q.offer(n + x);
        }
        if (n + y <= x + y && set.add(n + y)) {
            q.offer(n + y);
        }
        if (n - x >= 0 && set.add(n - x)) {
            q.offer(n - x);
        }
        if (n - y >= 0 && set.add(n - y)) {
            q.offer(n - y);
        }
        if (set.contains(z)) {
            return true;
        }
    }
    return false;
}/<integer>/<integer>/<code>

閱讀更多 新視像 的文章

關鍵字: 水壺 big 裝滿