有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
Related Topics
深度优先搜索广度优先搜索数学\n
👍 301👎 0
题解
首先想到的是深搜，代码写完了开心提交，emmm，问题来了。有个用例过不去，提示超时，这个用例是
104579, 104593, 12444
1水壶容量104579，2水壶容量104593，目标水量12444
自己在本地写了个test试了下，，提示栈溢出，修改-Xss参数多次尝试之后终于能跑过去了，这个时候的设置是-Xss102400k，加了个标记看了栈深度大概看了下，好家伙，直接跑到了362138。这只是个大概值，并不肯定十分准确。
先贴下这个代码，思路应该还是比较明晰的。
import org.junit.Test;
import java.util.HashSet;
/**
* LeetCode365<br>
* [在此填写类描述]
*
* @date 2021/7/14 19:54
* @see [相关类/方法]（可选）
* @since [产品/模块版本] （可选）
*/
public class LeetCode365 {
@Test
public void test(){
System.out.println(canMeasureWater(104579, 104593, 12444));;
}
private HashSet<String> visited = new HashSet<>();
private boolean ifCan = false;
private int target;
private int jug1Max;
private int jug2Max;
private int depth = 0;
public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
this.target = targetCapacity;
this.jug1Max = jug1Capacity;
this.jug2Max = jug2Capacity;
if (jug1Max+jug2Max < target){
return false;
}
tryNext( 0 ,0 ,1);
System.out.println(depth);
return ifCan;
}
private void tryNext( int jug1Current, int jug2Current, int count){
count++;
if (count > this.depth){
this.depth = count;
}
if (ifCan)return;
if (jug1Current == target || jug2Current == target || jug1Current + jug2Current == target){
ifCan = true;
return;
}
if (visited.contains(jug1Current+"_"+jug2Current)){
return;
}
visited.add(jug1Current+"_"+jug2Current);
//下一步几种情况
//往1瓶子倒满水, 但是只有在1瓶子水没满的情况下可以
if (jug1Current < jug1Max){
tryNext(jug1Max,jug2Current,count);
}
//往2瓶子倒满水，但是只有在2瓶子水没有满的情况下可以
if (jug2Current < jug2Max){
tryNext(jug1Current,jug2Max,count);
}
if ( jug1Current > 0 && jug2Current>0){
//把1瓶子的水倒掉，但是只在1瓶子里有水的情况可以，且2瓶子里也有水，如果2瓶子没水会回到0_0的状态
tryNext(0,jug2Current,count);
//把2瓶子的水倒掉，但是只在2瓶子里有水的情况可以，且1瓶子里也有水，如果1瓶子没水会回到0_0的状态
tryNext(jug1Current,0,count);
}
//把一个瓶子里的水倒到另外一个瓶子里分情况
//1.倒到满，倒出的瓶子还有剩余
//2.倒完了，被倒入的瓶子还没满
//中间正好满的情况都可以并在这两个里面，但是因为前面其实有两个瓶子各倒满一个的情况了，其实可以忽略
//把1瓶子的水倒入2瓶子,余下的水留在1瓶子中，但是只有在2瓶子水没满，且1瓶子有水的情况下
if (jug2Current < jug2Max && jug1Current > 0){
if ( jug1Current + jug2Current >= jug2Max){
//如果倒满了还有剩余
tryNext(jug1Current-(jug2Max-jug2Current),jug2Max,count);
}else {
//如果能全倒进去
tryNext(0,jug1Current+jug2Current,count);
}
}
//把2瓶子的水倒入1瓶子，余下的水留在2瓶子中，但是只有在1瓶子水没满，且2瓶子有水的情况下
if (jug1Current < jug1Max && jug2Current > 0){
if ( jug1Current + jug2Current >= jug1Max){
//如果倒满了还有剩余
tryNext(jug1Max,jug2Current - (jug1Max-jug1Current),count);
}else {
//如果能全倒进去
tryNext(jug1Current + jug2Current,0,count);
}
}
}
}
既然好吧，换个思路看看了。把深度递归调用改成队列试试呢。
private HashSet<String> visited = new HashSet<>();
private int target;
private int jug1Max;
private int jug2Max;
private Queue<int[]> queue = new LinkedList<>();
public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
this.target = targetCapacity;
this.jug1Max = jug1Capacity;
this.jug2Max = jug2Capacity;
if (jug1Max+jug2Max < target){
return false;
}
queue.add(new int[]{0, 0});
while (!queue.isEmpty()){
int[] arr = queue.poll();
int jug1Current = arr[0];
int jug2Current = arr[1];
//1和2的当前状态已经拿到了，那么和之前以前判断当前的状态并得到下一个可能的状态
//将下一个可能的状态放到队列尾部
if (jug1Current == target || jug2Current == target || jug1Current + jug2Current == target){
return true;
}
visited.add(jug1Current+"_"+jug2Current);
if (jug1Current < jug1Max){
addNext(jug1Max,jug2Current);
}
//往2瓶子倒满水，但是只有在2瓶子水没有满的情况下可以
if (jug2Current < jug2Max){
addNext(jug1Current,jug2Max);
}
if ( jug1Current > 0 && jug2Current>0){
//把1瓶子的水倒掉，但是只在1瓶子里有水的情况可以，且2瓶子里也有水，如果2瓶子没水会回到0_0的状态
addNext(0,jug2Current);
//把2瓶子的水倒掉，但是只在2瓶子里有水的情况可以，且1瓶子里也有水，如果1瓶子没水会回到0_0的状态
addNext(jug1Current,0);
}
//把一个瓶子里的水倒到另外一个瓶子里分情况
//1.倒到满，倒出的瓶子还有剩余
//2.倒完了，被倒入的瓶子还没满
//中间正好满的情况都可以并在这两个里面，但是因为前面其实有两个瓶子各倒满一个的情况了，其实可以忽略
//把1瓶子的水倒入2瓶子,余下的水留在1瓶子中，但是只有在2瓶子水没满，且1瓶子有水的情况下
if (jug2Current < jug2Max && jug1Current > 0){
if ( jug1Current + jug2Current >= jug2Max){
//如果倒满了还有剩余
addNext(jug1Current-(jug2Max-jug2Current),jug2Max);
}else {
//如果能全倒进去
addNext(0,jug1Current+jug2Current);
}
}
//把2瓶子的水倒入1瓶子，余下的水留在2瓶子中，但是只有在1瓶子水没满，且2瓶子有水的情况下
if (jug1Current < jug1Max && jug2Current > 0){
if ( jug1Current + jug2Current >= jug1Max){
//如果倒满了还有剩余
addNext(jug1Max,jug2Current - (jug1Max-jug1Current));
}else {
//如果能全倒进去
addNext(jug1Current + jug2Current,0);
}
}
}
return false;
}
private void addNext(int jug1Current,int jug2Current){
if (visited.contains(jug1Current+"_"+jug2Current)){
//已经有过，不添加
return;
}
queue.add(new int[]{jug1Current,jug2Current});
}
写queue版本的时候原本把已访问的判断写在poll之后的，但是想了下，还是放在了添加进queue之前，这样也许可以减少点判断。
if (visited.contains(jug1Current+"_"+jug2Current))
如果是写在poll之后的话，就用CONTINUE中断，继续处理queue中的下一个。
另外，写queue这个版本的时候，可以看到，大部分逻辑代码和之前的递归深搜的是基本一致的，区别仅仅在于，递归是调用自身，而queue这个是把下一个可能的状态加进队列，等待处理。是不是看到的BFS的影子，确实，本质上来说这两种方法就是DFS和BFS的区别。