leetcode 365. Water and Jug Problem | 365. 水壶问题（Java）

矫情吗；* 2022-08-30 01:57 95阅读 0赞

## 题目 ##

[https://leetcode.com/problems/water-and-jug-problem/][https_leetcode.com_problems_water-and-jug-problem]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]  
又是踩比赞多的一道题…我认为有两个可能的原因：

1.  虽然通过了，但原理不明了。
2.  本质是个数学问题，数学问题本应用数学方法解决。如果用普通的模拟解法，会很耗（人的）时间。

## 题解 ##

看了下面的 Related Topics，知道了这是个 DFS，就往 DFS 的方向思考了。  
![在这里插入图片描述][20210718155534679.png]  
思路就是辗转相减，直到结果等于 target 为止。为了避免重复运算，将已经得到的结果放进 seen 集合中。

顺便贴一下草稿：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

另外，本题实际上可以简化成为一个数学问题，参考：[Math solution - Java solution][]

import java.util.HashSet;
    
    class Solution { 
        public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) { 
            int c1, c2; // c1<c2
            if (jug1Capacity < jug2Capacity) { 
                c1 = jug1Capacity;
                c2 = jug2Capacity;
            } else { 
                c1 = jug2Capacity;
                c2 = jug1Capacity;
            }
            if (c1 == targetCapacity || c2 == targetCapacity || c1 + c2 == targetCapacity) return true;
            HashSet<Integer> seen = new HashSet<>();
            seen.add(c1);
            seen.add(c2);
            int dif = c2 - c1;
            while (dif > 0) { 
                if (dfs(c1, c2, dif, targetCapacity, seen)) return true;
                dif -= c1;
            }
            return false;
        }
    
        public boolean dfs(int c1, int c2, int diff, int t, HashSet<Integer> seen) { 
            if (seen.contains(diff)) return false;
            seen.add(diff);
            if (diff == t || c1 + diff == t || c2 + diff == t) return true;
    
            int d1 = c1 - diff;
            while (d1 > 0) { 
                if (dfs(c1, c2, d1, t, seen)) return true;
                d1 -= diff;
            }
    
            int d2 = c2 - diff;
            while (d2 > 0) { 
                if (dfs(c1, c2, d2, t, seen)) return true;
                d2 -= diff;
            }
    
            int d3 = c1 + diff;
            while (d3 < c2) { 
                if (dfs(c1, c2, d3, t, seen)) return true;
                d3 += diff;
            }
    
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_water-and-jug-problem]: https://leetcode.com/problems/water-and-jug-problem/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/3b3db42362e8466f9cd30eee1dffc935.png
[20210718155534679.png]: /images/20220829/0da9a3f7bdfc4f0e861b00b457007c8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/dfee9fad7bdd4c89859dab8d881b95c4.png
[Math solution - Java solution]: https://leetcode.com/problems/water-and-jug-problem/discuss/83715/Math-solution-Java-solution
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/60d77c3d75434ffd80fdf339086f4242.png