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

题目

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<c2if (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;} }

总结

以上是生活随笔为你收集整理的leetcode 365. Water and Jug Problem | 365. 水壶问题（Java）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。