0%

leetcode Water and Jug Problem

leetcode Water and Jug Problem

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.

Operations allowed:

  • Fill any of the jugs completely.
  • 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:

1
2
3
Input: x = 2, y = 6, z = 4
Output: True

Example 2:

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

题目地址:leetcode Water and Jug Problem

题意: 给定两个杯子,它们分别能装x和y升水,求它们是否能恰好测量出z升的水。

思路:

题目可以表示为如下等式:

  • mx + ny = z
  • 若m,n>0说明往里面加水,若m,n <0则说明清空

如x=3,y=5 可以有  3 x  + (-1)y = 4 即 m=3 , n=-1 ,也就是说我们需要往3这个杯子装满3次,5这个杯子倒掉1次

  • 首先往3的杯子注满水,然后倒入倒入5    杯子情况为: 0,3
  • 接着把3的杯子注满水,在倒入5 ,杯子情况为  1,5
  • 接着把5的杯子倒掉, 把3的杯子装入5, 这样为 0,1
  • 接着把3的杯子注满水,倒入5, 这样0,4

可以参考  : http://www.math.tamu.edu/~dallen/hollywood/diehard/diehard.htm

本题中,若mx + ny = z 有解,则一定有z为GCD(x,y) 的整数倍,否则无解。

且需要满足条件 x + y >=z

C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
return x + y == z (x + y > z ) && z % gcd(x,y) == 0;
}

int gcd(int a,int b){
return b==0? a: gcd(b,a%b);
}
};

Java

1
2
3
4
5
6
7
8
9
public class Solution {
public boolean canMeasureWater(int x, int y, int z) {
return x + y == z (x + y > z ) && z % gcd(x,y) == 0;
}

private int gcd(int a,int b){
return b==0? a: gcd(b,a%b);
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def canMeasureWater(self, x, y, z):
"""
:type x: int
:type y: int
:type z: int
:rtype: bool
"""

def gcd(a, b):
return a if b == 0 else gcd(b, a % b)

return x + y == z or ((x + y > z) and z % gcd(x, y) == 0)

 

本题是leetcode 365 Water and Jug Problem 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~