leetcode365.Water And Jug Problem

发表于 更新于 分类于 ，

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False

假设现在有两个杯子，每个杯子分别最多可以装x和y升水，假设现在水的供应量是无限的，问是否有可能用这两个杯子共同承装z升水，可以用两个杯子执行的操作如下：

  1. 将任何一个杯子装满水
  2. 倒掉任何一个杯子中的所有水
  3. 将一个杯子中的水倒进另一个杯子，直到另一个杯子满了或者是当前的杯子已经空了

比如，如果现在两个杯子A和B分别能装3升水和5升水，需要在两个杯子中共装4升水。我们可以找到这样一个序列满足题目要求：

  1. 将B杯倒满水并导入A中，此时A:3 B:2
  2. 将A杯倒空，并将B中的水倒入A中，此时A:2 B:0
  3. 将B杯装满并倒A中，此时A:3 B:4
  4. 将A杯倒掉，此时A:0 B:4

##思路一：搜索##
这里可以说我们变相的利用了深度/广度优先搜索来实现。通过深度/广度优先搜索我们可以实现遍历所有可能的场景，直到找到我们最终想要的结果，或者得到该结果无法达到的结论。假设我们知道当前水杯的情况为A最多可以放置x升水，B最多可以放置Y升水，而且A当前水杯中有a升水，B中有b升水，则由当前情况在一次操作之后可能产生以下几种情况：

  • 倒光A中的水：A:0 | B:b
  • 倒光B中的水：A:a | B:0
  • 装满A中的水：A:x | B:b
  • 装满B中的水：A:a | B:y
  • 将A中的水倒进B中：A:a - min(a, y-b) | B:b + min(a, y-b)
  • 将B中的水倒进A中：A:a + min(x-a, y) | B:b - min(x-a, y)
    最后两种情况需要判断两个杯子的剩余水情况和可倒入水的情况

如果以上几种情况都不满足z，则我们再以以上几种情况为基础继续寻找可能的情况。这里可以使用HashSet来避免对情况的重复遍历。代码如下：

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
61
62
63
64
65
   public class Status{
	private int x;
	private int y;
	
	public int getX() {
		return x;
	}
	
	public int getY() {
		return y;
	}
	
	public int getWater() {
		return this.getX() + this.getY();
	}
	
	public Status(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	@Override
	public boolean equals(Object o) {
		if(o==null || !(o instanceof Status)) return false;
		if(this == o) return true;
		Status s = (Status) o;
		return this.getX() == s.getX() && this.getY() == s.getY();
	}
	
	@Override
	public int hashCode() {
		return this.getX() + 17 * this.getY();
	}
}

Set<Status> statusSet = new HashSet<Status>();
public boolean canMeasureWaterDFS(int x, int y, int z) {
	if(x + y < z) return false;
	if(x == z || y == z || x + y == z) return true;
	return canMeasureWaterDFS(x, y , new Status(0, 0), z);
}

public boolean canMeasureWaterDFS(int x, int y, Status curStatus, int z) {
	if(statusSet.contains(curStatus)) return false;
	else if(curStatus.getWater() == z) return true;
	else{
		statusSet.add(curStatus);
		
		return canMeasureWaterDFS(x, y, new Status(x, curStatus.getY()), z)
			|| canMeasureWaterDFS(x, y, new Status(curStatus.getX(), y), z)
			|| canMeasureWaterDFS(x, y, new Status(curStatus.getX(), 0), z)
			|| canMeasureWaterDFS(x, y, new Status(0, curStatus.getY()), z)
			|| canMeasureWaterDFS(x, y, new Status(
							curStatus.getX() - Math.min(curStatus.getX(), y-curStatus.getY()),
							curStatus.getY() + Math.min(curStatus.getX(), y-curStatus.getY())
					),
					z)
			|| canMeasureWaterDFS(x, y, new Status(
							curStatus.getX() + Math.min(x - curStatus.getX(), curStatus.getY()),
							curStatus.getY() - Math.min(x - curStatus.getX(), curStatus.getY())
					), 
					z);
	
	}
}

思路二：数学

这里使用了一个数学结论叫做Bézout’s identity，在该理论中，假设数字a和b有一个最大公约数d，则一定存在x和y满足ax+by=d。x,y的其它组合所得到的值一定是d的倍数。
这里x为负值时代表将杯子倒空，x为正值时代表将杯子装满。

1
2
3
4
5
6
7
public boolean canMeasureWater(int x, int y, int z) {
    if(x == z || y == z || x + y == z) return true;
    if(x + y < z) return false;
    
    while( (x %= y) != 0 && (y %= x) != 0);
    return z % (x+y) == 0;
}