[LeetCode] 365、水壶问题

题目描述

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

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

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

解题思路

纯数学解法比较难搞，这是一个比较经典的图的“广度优先搜索”问题。我的实现。

• BFS：（从一个或若干个起始点开始，沿着边像水波一样逐层向外遍历，直到所有的点已被访问或者到达目标状态。推荐看题解！）

  这一类游戏相关的问题，用人脑去想，是很难穷尽所有的可能情况的。因此很多时候需要用到**「搜索算法」**。

  「搜索算法」一般情况下是在「树」或者「图」结构上的「深度优先遍历」或者「广度优先遍历」。因此，在脑子里，更建议动手在纸上画出问题抽象出来的「树」或者「图」的样子。（遍历所有可能就解出来了）

  

  关于图片的说明：

  • 节点表示两个水壶的状态；
  • 边表示操作方法：分别为倒满A/B，倒空A/B，A倒入B，B倒入A 六种方法；
  • 这是一个有向图，因为有些状态并不能互相转移。比如 (1,1) 和 (1,0)。

  在「树」上的「深度优先遍历」就是「回溯算法」，在「图」上的「深度优先遍历」是「flood fill」 算法（附议）。深搜比较节约空间。这道题由于就是要找到一个符合题意的状态，我们用广搜就好了。这是因为广搜有个性质，一层一层像水波纹一样扩散，路径最短。

  所谓「状态」，就是指当前的任务进行到哪个阶段了，可以用变量来表示，怎么定义状态有的时候需要一定技巧，这道题不难。这里分别定义两个水壶为 A 和 B，定义有序整数对 (a, b) 表示当前 A 和 B 两个水壶的水量，它就是一个状态。

  其它细节请直接题解和代码，清晰易懂！

• 数学方法：（这部分直接看题解即可，较难理解，面试不会问数学解法）

  • 我们认为，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。（原因看题解）
  • 因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。所以我们的目标可以改写成：找到一对整数 a, b，使得ax + by = z。若这样的a, b存在，那么我们的目标就是可以达成的。
  • 而贝祖定理告诉我们，ax + by = z 有解当且仅当 z 是 x, y 的最大公约数的倍数。因此我们只需要找到 x, y 的最大公约数并判断 z 是否是它的倍数即可。

参考代码

BFS

class Solution {
    pair<int, int> op(int type, const pair<int, int> &state, int x, int y) {
        // 边表示操作方法：分别为倒满A/B，倒空A/B，A倒入B，B倒入A 六种方法。
        switch(type) {
            case 0 : return make_pair(x, state.second);
            case 1 : return make_pair(state.first, y);
            case 2 : return make_pair(0, state.second);
            case 3 : return make_pair(state.first, 0);
            case 4 :{
                int move = min(state.first, y-state.second);
                return make_pair(state.first - move, state.second + move);
            }
            case 5 : {
                int move = min(x-state.first, state.second);
                return make_pair(state.first + move, state.second - move);
            }
        }
        return make_pair(0, 0);
    }
    
    // 自定义的hash函数
    struct HashPair {
        size_t operator()(const pair<int, int> &key) const noexcept{
		    return size_t(key.first)*100000007 + key.second;
	    }
    };
    
public:
    bool canMeasureWater(int x, int y, int z) {
        // 特判
        if(z == 0) return true;
        if(x + y < z) return false;
        
        unordered_set<pair<int,int>, HashPair> mark;
        queue<pair<int,int> > q;
        q.push(make_pair(0, 0));
        while(q.empty() == false) {
            auto node = q.front();
            q.pop();
            // 找到了目标状态
            if(node.first + node.second == z || node.first == z || node.second == z) {
                return true;
            }
            
            // 因为一共有六种操作方法
            for(int i = 0; i < 6; i++) {
                auto next = op(i, node, x, y);
                // 因为状态有重复，因此是一个「有向」且「有环」的图，在遍历的时候，需要判断该结点设置是否访问过
                if(mark.find(next) != mark.end()) {
                    continue;
                }
                mark.insert(next);
                q.push(next);
            }
        }
        
        return false;
    }
    
};

数学方法

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        // 特判
        if(z < 0 || x + y < z) return false;
        if(z == 0) return true;
        
        int g;
        if(x == 0 || y == 0)  // 除数不为0
            g = x + y;
        else
            g = gcd(x, y);
            
        return (z % g) == 0;
    }
    
    int gcd(int a,int b) {  // 辗转相除法
        if(b == 0)
            return a;
        return gcd(b, a % b);
    }
};