題目

https://leetcode.com/problems/water-and-jug-problem/

又是踩比贊多的一道題…我認為有兩個可能的原因：

雖然通過了，但原理不明了。

本質(zhì)是個數(shù)學問題，數(shù)學問題本應用數(shù)學方法解決。如果用普通的模擬解法，會很耗（人的）時間。

題解

看了下面的 Related Topics，知道了這是個 DFS，就往 DFS 的方向思考了。

思路就是輾轉相減，直到結果等于 target 為止。為了避免重復運算，將已經(jīng)得到的結果放進 seen 集合中。

順便貼一下草稿：

另外，本題實際上可以簡化成為一個數(shù)學問題，參考：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）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。