​LeetCode刷题实战365：水壶问题

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 水壶问题，我们先来看题面：

https://leetcode-cn.com/problems/water-and-jug-problem/

You are given two jugs with capacities jug1Capacity and jug2Capacity liters. There is an infinite amount of water supply available. Determine whether it is possible to measure exactly targetCapacity liters using these two jugs.

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

Operations allowed:

• Fill any of the jugs 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升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

• 装满任意一个水壶

• 清空任意一个水壶

• 从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例

示例 1:

输入: x = 3, y = 5, z = 4
输出: True

示例 2:

输入: x = 2, y = 6, z = 5
输出: False

解题

主要思路：

这是一道数学题了。水量 z 是两个水壶容量的最大公约数的倍数，且 z <= x+y

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(z > x+y)
          return false;
        int r;
        while(y != 0)//循环结束后，最大公约数是x
        {
          r = x%y;
          x = y;
          y = r;
        }
        return (z==0 || z%x == 0);
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-360题汇总，希望对你有点帮助！

LeetCode刷题实战361：轰炸敌人

LeetCode刷题实战362：敲击计数器

LeetCode刷题实战363：矩形区域不超过 K 的最大数值和