leetcode 365. Water and Jug Problem | 365. 水壶问题（Java）-蒲公英云

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

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

题目

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

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

题解

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

顺便贴一下草稿：
在这里插入图片描述

另外，本题实际上可以简化成为一个数学问题，参考：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;
    }
}