365. 水壶问题

image.png
思路：刚看这题是懵圈的状态的，完全不知道如何入手。但是仔细想想会发现这是一个搜索问题。抽象出来的话，就是你有两个容器，你需要用这两个容器凑出“一定容量”的水。允许的操作有3个，如题中所述，实际上是有6个操作的。这就是回到了递归执行可执行操作，然后寻找结束条件这类的问题了，最容易想到的就是DFS算法或BFS算法。

  1. /**
  2. 6种操作
  3. 1. 装满水壶1
  4. 2. 装满水壶2
  5. 3. 清空水壶1
  6. 4. 清空水壶2
  7. 5. 水壶1倒向水壶2，直到水壶2满或水壶1倒尽了
  8. 6. 水壶2倒向水壶1，直到水壶1满或水壶2倒尽了
  10. 结束条件
  11. 水壶1凑出 || 水壶2凑出 || 水壶1+水壶2凑出
  12. */
  13. class Solution {
  14.     public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
  15.         int x = jug1Capacity;
  16.         int y = jug2Capacity;
  17.         int z = targetCapacity;
  18.         LinkedList<int[]> stack = new LinkedList<>(); //装水壶1和水壶2的当前水量
  19.         stack.addLast(new int[]{0, 0});
  20.         Set<Long> visited = new HashSet(); //已经查过了，使用hash函数
  21.         while (!stack.isEmpty()) {
  22.             if (visited.contains(hash(stack.getLast()))) {
  23.                 stack.pollLast();
  24.                 continue;
  25.             }
  26.             visited.add(hash(stack.getLast()));
  27.             int[] state = stack.pollLast();
  28.             int remainX = state[0];
  29.             int remainY = state[1];
  30.             if (remainX==z || remainY==z || (remainX+remainY)==z) {
  31.                 return true;
  32.             }
  33.             //上述6种操作
  34.             stack.push(new int[]{x, remainY});
  35.             stack.push(new int[]{remainX, y});
  36.             stack.push(new int[]{0, remainY});
  37.             stack.push(new int[]{remainX, 0});
  38.             int xToy = Math.min(remainX,y-remainY);
  39.             stack.push(new int[]{remainX - xToy, remainY + xToy});
  40.             int yTox = Math.min(x-remainX,remainY);
  41.             stack.push(new int[]{remainX + yTox, y - yTox});
  42.         }
  43.         return false;
  44.     }
  45.     public long hash(int[] state) {
  46.         return (long) state[0] * 10000001 + state[1];
  47.     }
  48. }