长大后想做什么？做回小孩！

0%

LeetCode——水壶问题

发表于 分类于 Valine：
本文字数： 348

NO.365 水壶问题 中等

8fu65F.png

思路一：广度优先遍历

两个水壶不可能同时都是半满的。如果某个水壶是半满的，另外一个肯定是满的或者空的。而且如果某个水壶是半满的（此时另外一个就是空的或者满的），就不能直接把这个水壶填满，也不能把这个半满的水倒掉，因为这会回到初始状态，这么做没有意义。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;

class Solution {
  public boolean canMeasureWater(int x, int y, int z) {
    if (z == 0) {
      return true;
    }
    if (x + y < z) {
      return false;
    }
    Queue<Map.Entry<Integer, Integer>> queue = new ArrayDeque<>();
    AbstractMap.SimpleEntry<Integer, Integer> start = new AbstractMap.SimpleEntry<>(0, 0);
    queue.add(start);
    Set<Map.Entry<Integer, Integer>> visited = new HashSet<>();
    visited.add(start);
    while (!queue.isEmpty()) {
      Map.Entry<Integer, Integer> entry = queue.poll();
      int curX = entry.getKey();
      int curY = entry.getValue();
      if (curX == z || curY == z || curX + curY == z) {
        return true;
      }
      if (curX == 0) {
        // 把第一个桶填满
        addIntoQueue(queue, visited, new AbstractMap.SimpleEntry<>(x, curY));
      }
      if (curY == 0) {
        // 把第二个桶填满
        addIntoQueue(queue, visited, new AbstractMap.SimpleEntry<>(curX, y));
      }
      if (curY < y) {
        // 把第一个桶倒空
        addIntoQueue(queue, visited, new AbstractMap.SimpleEntry<>(0, curY));
      }
      if (curX < x) {
        // 把第二个桶倒空
        addIntoQueue(queue, visited, new AbstractMap.SimpleEntry<>(curX, 0));
      }

      // y - curY是第二个桶还可以再加的水的升数，但是最多只能加curX升水。
      int moveSize = Math.min(curX, y - curY);
      // 把第一个桶里的curX升水倒到第二个桶里去。
      addIntoQueue(queue, visited, new AbstractMap.SimpleEntry<>(curX - moveSize, curY + moveSize));
      // 反过来同理，x - curX是第一个桶还可以再加的升数，但是最多只能加curY升水。
      moveSize = Math.min(curY, x - curX);
      // 把第一个桶里的curX升水倒到第二个桶里去。
      addIntoQueue(queue, visited, new AbstractMap.SimpleEntry<>(curX + moveSize, curY - moveSize));
    }
    return false;
  }

  private void addIntoQueue(Queue<Map.Entry<Integer, Integer>> queue,
                            Set<Map.Entry<Integer, Integer>> visited,
                            Map.Entry<Integer, Integer> newEntry) {
    if (!visited.contains(newEntry)) {
      visited.add(newEntry);
      queue.add(newEntry);
    }
  }
}

时间复杂度：O(xy)

思路二：裴蜀(贝祖)定理

裴蜀定理：对任意两个整数 a、b，设 d是它们的最大公约数。那么关于未知数 x和 y的线性丢番图方程（称为裴蜀等式）：ax+by=m

有整数解 (x,y) 当且仅当 m是d的整数倍。裴蜀等式有解时必然有无穷多个解。

意思就是两个壶的容量x、y的最大公约数d可以整除目标壶的容量z，则为true。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean canMeasureWater(int x, int y, int z) {
    if (z==0)return true;
    if (x+y<z)return false;
    //求x，y的最大公约数
    int d=gcd(x,y);
    return z%d==0;
}

private int gcd(int x, int y) {
    if (y==0)return x;
    return gcd(y,x%y);
}

时间复杂度：O(logMax(x,y))

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github