题目描述

You are given two jugs with capacities xand 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.

 

题目大意

两个大小分别为x和y升的水壶，可以无限次的给水壶充满水，并且两个水壶之间可以互相倒水，是否可以实现两个水壶中的水相加等于z。

 

示例

E1

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

E2

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

 

解题思路

根据LeetCode@lblbxuxu2的思路，用v来表示当前的获得的水的总量，

　　当v < x时，能做的有意义的操作只能是将y灌满，因此：v += y

　　当v > x时，能做的有意义的操作只能是将x清空，因此：v -= x

循环判定是否存在满足v = z的情况。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

 

代码

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(x + y == z)
            return true;
        if(x + y < z)
            return false;
        // 若x比y小，则将两个数字互换
        if(x < y) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        
        int v = 0;
        while(1) {
            if(v < x)
                v += y;
            else
                v -= x;
            if(v == z)
                return true;
            if(v == 0)
                return false;
        }
    }
};