🌕🌕 365. 水壶问题

难度: 🌕🌕

问题描述

---

解法 1 - DFS

class Solution {
    HashSet<Long> set = new HashSet<>();
    int capX;
    int capY;
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        // 思路：
        // 模拟，假设 2 个水壶分别为 x, y 初始状态下已有水量为 curX, curY，最大容量分别为 capX, capY
        // 每次均有 3 种操作
        // 1. 装满任意一个水壶 --> [capX, curY] or [curX, capY]
        // 2. 清空任意一个水壶 --> [0, curY] or [curX, 0]
        // 3. x 倒入 y or y 倒入 x 
        // 1) x 倒入 y --> [0, curY + curX] or [curX - capY + curY, capY]
        // 2) y 倒入 x --> [curX + curY, 0] or [capX, curY - capX + curX]
        // 因此可以采用 DFS | BFS 搜索
        // 通过 set 去重
        capX = jug1Capacity;
        capY = jug2Capacity;

        if(targetCapacity > capX + capY) {
            return false;
        }
        return mySol(0, 0, targetCapacity);
    }

    private boolean mySol(int curX, int curY, int targetCapacity) {
        // System.out.println(curX + ", " + curY + " ; " + targetCapacity);
        // 递归终止条件
        if(targetCapacity == curX || targetCapacity == curY || targetCapacity == curX + curY) {
            return true;
        }
        if(set.contains(getHash(curX, curY))) {
            return false; // 说明出现了循环
        } else {
            set.add(getHash(curX, curY));
        }
        
        // situation 1 - 只有往空壶中倒满水才有意义
        if(curX == 0) {
            if(mySol(capX, curY, targetCapacity)) {
                return true;
            }
        }
        if(curY == 0) {
            if(mySol(curX, capY, targetCapacity)) {
                return true;
            }
        }
        // situation 2
        if(curX > 0) {
            if(mySol(0, curY, targetCapacity)) {
                return true;
            }
        }
        if(curY > 0) {
            if(mySol(curX, 0, targetCapacity)) {
                return true;
            }
        }
        // situation 3
        if(curX + curY <= capY) {
            if(mySol(0, curX + curY, targetCapacity)) {
                return true;
            }
        } else {
            if(mySol(curY + curX - capY, capY, targetCapacity)) {
                return true;
            }
        }
        if(curX + curY <= capX) {
            set.add(getHash(curX + curY, 0));
            if(mySol(curY + curX, 0, targetCapacity)) {
                return true;
            }
        } else {
            if(mySol(capX, curY + curX - capX, targetCapacity)) {
                return true;
            }
        }
        return false;
    }

    private long getHash(int a, int b) {
        // 将 2 个32位 int 数转为一个 long 值
        long res = (long)((long)a << 32) + b;
        return res;
    }
}

---

输出 1

---

解法 2 - BFS

class Solution {
    HashSet<Long> set = new HashSet<>();
    int capX;
    int capY;
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        // 思路：
        // 模拟，假设 2 个水壶分别为 x, y 初始状态下已有水量为 curX, curY，最大容量分别为 capX, capY
        // 每次均有 3 种操作
        // 1. 装满任意一个水壶 --> [capX, curY] or [curX, capY]
        // 2. 清空任意一个水壶 --> [0, curY] or [curX, 0]
        // 3. x 倒入 y or y 倒入 x 
        // 1) x 倒入 y --> [0, curY + curX] or [curX - capY + curY, capY]
        // 2) y 倒入 x --> [curX + curY, 0] or [capX, curY - capX + curX]
        // 因此可以采用 DFS | BFS 搜索
        // 通过 set 去重
        capX = jug1Capacity;
        capY = jug2Capacity;
        // 特殊情况特判
        if(targetCapacity > capX + capY) {
            return false;
        }
        if(targetCapacity == capX + capY) {
            return true;
        }

        // BFS
        LinkedList<Long> queue = new LinkedList<>();
        HashSet<Long> set = new HashSet<>();
        // 压入初始状态
        queue.offer(getHash(0, 0));
        while(!queue.isEmpty()) {
            int len = queue.size();
            for(int i = 0; i < len; i ++) {
                long cur = queue.poll(); // 获取当前状态
                if(set.contains(cur)) {
                    continue;
                } else {
                    set.add(cur);
                }
                // 根据队列中的值转换为 x & y
                int[] tmp = hashBefore(cur);
                int curX = tmp[0];
                int curY = tmp[1];
                // System.out.println(Arrays.toString(tmp));
                // 判断当前 cur 是否满足条件
                if(targetCapacity == curX || targetCapacity == curY || targetCapacity == curX + curY) {
                    return true;
                }
                // situation 1 尝试
                if(curX == 0) {
                    // 只有杯子空时倒满才有用，半满的杯子倒满无意义，相当于从空杯倒满
                    long tmp1 = getHash(capX, curY);
                    queue.offer(tmp1);
                }
                if(curY == 0) {
                    long tmp1 = getHash(curX, capY);
                    queue.offer(tmp1);
                }
                // sit2 
                if(curX > 0) {
                    // 只有杯子有水时，清空杯子才有意义
                    long tmp1 = getHash(0, curY);
                    queue.offer(tmp1);
                }
                if(curY > 0) {
                    long tmp1 = getHash(curX, 0);
                    queue.offer(tmp1);
                }
                // sit3
                if(curX + curY <= capY) {
                    long tmp1 = getHash(0, curX + curY);
                    queue.offer(tmp1);
                } else {
                    long tmp1 = getHash(curX - capY + curY, capY);
                    queue.offer(tmp1);
                }
                if(curX + curY <= capX) {
                    long tmp1 = getHash(curX + curY, 0);
                    queue.offer(tmp1);
                } else {
                    long tmp1 = getHash(capX, curY - capX + curX);
                    queue.offer(tmp1);
                }
            }
        }
        return false;
    }

    private int[] hashBefore(long input) {
        int[] res = new int[] {0, 0};
        res[0] = (int)(input >>> 32);
        res[1] = (int)input;
        return res;
    }

    private long getHash(int a, int b) {
        // 将 2 个32位 int 数转为一个 long 值
        long res = (long)((long)a << 32) + b;
        return res;
    }
}

---

输出 2

---

解法 3 - 数学

class Solution {
    HashSet<Long> set = new HashSet<>();
    int capX;
    int capY;
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        // 思路：
        // 模拟，假设 2 个水壶分别为 x, y 初始状态下已有水量为 curX, curY，最大容量分别为 capX, capY
        // 每次均有 3 种操作
        // 1. 装满任意一个水壶 --> [capX, curY] or [curX, capY]
        // 2. 清空任意一个水壶 --> [0, curY] or [curX, 0]
        // 3. x 倒入 y or y 倒入 x 
        // 1) x 倒入 y --> [0, curY + curX] or [curX - capY + curY, capY]
        // 2) y 倒入 x --> [curX + curY, 0] or [capX, curY - capX + curX]
        // 
        // 以上 3 种操作中，
        // 1. 导致 整体 + capX | + capY
        // 2. 导致 整体 - capX | - capY
        // 3. 导致 整体水量不变
        // 
        // 也就是说，
        // 无论怎么变换，可以通过公式 a*capX + b*capY 表示
        // 即找到满足条件的 a & b 使得 a*capX + b*capY = targetCapacity
        // 即找到 capX & capY 的最大公约数 c，判断 targetCapacity 是否为 c 的倍数
        // 如何找到 2 个数的最大公约数？
        // 循环取余，每次找到较大的数，让其减去较小数，直到 2 个数相等，即为最大公约数
        capX = jug1Capacity;
        capY = jug2Capacity;
        // 特殊情况特判
        if(targetCapacity > capX + capY) {
            return false;
        }
        if(targetCapacity == capX + capY) {
            return true;
        }
        int c = mySol(capX, capY);
        return targetCapacity % c == 0;
    }

    private int mySol(int a, int b) {
        if(a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        // a >= b
        if(a == b) {
            return a;
        }
        // a > b
        return mySol(a - b, b);
    }
}

---

输出 3