365. Water and Jug Problem

题意：
给定两个容量分别为x和y升的罐子。提供无限容量的水。你需要判断用这两个罐子是否可以恰好量出z升的体积。到最后量出的z升体积可以由一到两个罐子装着。
允许的操作包括：
1、将任意罐子灌满。
2、将任意罐子清空。
3、将任意罐子的水倒入另一个罐子，直到另一个罐子倒满或者自己为空为止。

方法一：我自己的解法（不能保证正确）

void increse(set<int>& s, int x, int y) {
    int size = s.size();
    auto items2 = s;
    for(auto var = items2.begin(); var != items2.end(); var++)
    {
        int newx = x - *var;
        int newy = y - *var;
        if (newx > 0)s.insert(newx);
        if (newy > 0) s.insert(newy);
    }

    if (size != s.size()) increse(s, x, y);
}
bool canMeasureWater(int x, int y, int z) {
    if (z > x + y) return false;
    if (z == x + y) return true;
    if (x < y) {
        int temp = x;
        x = y;
        y = temp;
    }

    set<int> items;
    
    for (int i = x - y; i > 0 && y != 0; i -= y) {
        items.insert(i);
    }

    increse(items, x, y);

    for(auto var = items.begin(); var != items.end(); var ++)
    {
        if (*var + x == z || *var + y == z) return true;
    }

    return false;
}

方法二：利用数学知识，判断z是否为x,y的最大公约数的倍数

int gcd(int p, int q) {
    return q == 0 ? p : gcd(q, p % q);
} 
   
bool canMeasureWater2(int x, int y, int z) {
    if (z > x + y) return false;
    if (z == 0) return true;
    return z % gcd(x, y) == 0 ? true : false;
}

总结：数学真的很重要啊，从这代码量就能看出来了啊