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

今天和大家聊的问题叫做 水壶问题，我们先来看题面：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);
    }
};

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