LeetCode 365.水壶问题

题目

水壶问题
链接可能点不进去，所以我把完整的题目写在了下面。

有两个容量分别为x升和y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好z升的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的z升水。
你允许：
*装满任意一个水壶
*清空任意一个水壶
*从一个水壶向另外一个水壶倒水，直到装满或者倒空

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

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

分析

题意非常清晰，没有异议。对于示例 1我们可以通过如下步骤得到4：

装满y：0 5
把y倒入x：3 2
把x清空：0 2
装满y：2 5
把y倒入x：3 4
最后我们从y这个杯子中得到了4。

这题的标签是数学，一般数学标签的题都是有规律可循或者它本质就是一个数学定理。比如这道题灯泡开关答案是sqrt(n)，这道题我是通过找规律做出来的，手撕了n=1-8所有的情况后发现的。
回到这道题，开始看到这道题我一点思路都没有，做了半年的算法了发现数学和动态规划标签的题是最难找到思路的。于是乎我去谷歌了一下，在我写这篇文章的时候我搜到的思路千篇一律：判断z是否能被x和y的最大公约数整除；反正我是想不到的。
看来这确实是一个定理没跑了。那有没有什么其他的方法来做这道题呢？

Accept

其实这道题你可以类比为有向连通图，路径由题目中给出的三种操作创建，节点就是两杯水的多少，然后利用广度/深度搜索算法来做这个题。

解释一下路径怎么来
对于示例 1，最开始两杯水都是0 0。
0 0和0 5之间存在一条路径，因为他们可以通过第一个操作进行连接。
为什么是有向图
依然对于示例 1，假设目前两杯水为2 2。
2 2能到达3 1，只需要y的水倒入x即可，但是反过来3 1是没办法直接到达2 2的。

广度/深度搜索需要一个起始节点，我们可假设一个初始状态比如装满x来模拟。
因为此有向图中存在环。

解释一下为何存在环
依然对于示例 1
0 0能到0 5，0 5同样能到0 0。

所以我们需要记忆之前走过的点，后续不要再走，否则会死循环。
此题我们用广度来做即可，深度也一样的思路就不再给出了。

bool canMeasureWater(int x, int y, int z) {
        //去掉不可能的情况
        if(z > x + y) {
            return false;
        }
        //去掉一目了然的情况
        if(z == 0 || z == x || z == y || z == x + y) {
            return true;
        }
        //利用广度搜索来判断,最开始我们装满x,并把x和y转成一维来表示，这个值同时也类比于广度搜索中的节点。
        //num = x * 10000 + y numberMap用来记录已经走过的路，后续不会再走，你也可以用其他方式表示节点，后续解析的时候对应着来就好了。
        //这里使用了哈希表，因为我们后面经常会查询此表，把查询时间降低为O(1)提升算法速度。
        unordered_map<int, bool> numberMap;
        numberMap[x * 10000 + 0] = true;
        //双端队列，存放需要遍历的点。
        deque<int> needFindDeque;
        needFindDeque.push_back(x * 10000 + 0);
        //如果可以继续走，那就一直走
        while (!needFindDeque.empty()) {
            //得到此时两个瓶子的值
            int frontValue = needFindDeque.front();
            needFindDeque.pop_front();
            //这里应该不难理解吧，一维还原为二维
            int frontX = frontValue / 10000;
            int frontY = frontValue % 10000;
            //看看是否能得到z
            if(z == frontX || z == frontY || z == frontX + frontY) {
                return true;
            }
            //不能得到z，那么我们现在有题目中的几条路可以走
            //1.装满x
            {
                int tempX = x;
                //如果已经走过了，不需要添加
                if(numberMap[tempX * 10000 + frontY] == false) {
                    numberMap[tempX * 10000 + frontY] = true;
                    needFindDeque.push_back(tempX * 10000 + frontY);
                }
            }
            //2.装满y
            {
                int tempY = y;
                //如果已经走过了，不需要添加
                if(numberMap[frontX * 10000 + tempY] == false) {
                    numberMap[frontX * 10000 + tempY] = true;
                    needFindDeque.push_back(frontX * 10000 + tempY);
                }
            }
            //3.清空x
            {
                //如果已经走过了，不需要添加
                if(numberMap[0 * 10000 + frontY] == false) {
                    numberMap[0 * 10000 + frontY] = true;
                    needFindDeque.push_back(0 * 10000 + frontY);
                }
            }
            //4.清空y
            {
                //如果已经走过了，不需要添加
                if(numberMap[frontX * 10000 + 0] == false) {
                    numberMap[frontX * 10000 + 0] = true;
                    needFindDeque.push_back(frontX * 10000 + 0);
                }
            }
            //5.x倒入y
            {
                //如果x全部倒入y，y都没能满，重点！！！
                if(frontY + frontX < y) {
                    int tempX = 0;
                    int tempY = frontY + frontX;
                    if(numberMap[tempX * 10000 + tempY] == false) {
                        numberMap[tempX * 10000 + tempY] = true;
                        needFindDeque.push_back(tempX * 10000 + tempY);
                    }
                }
                //x倒入y，还有剩余
                else {
                    int tempX = frontX - (y - frontY);
                    int tempY = y;
                    if(numberMap[tempX * 10000 + tempY] == false) {
                        numberMap[tempX * 10000 + tempY] = true;
                        needFindDeque.push_back(tempX * 10000 + tempY);
                    }
                }
            }
            //6.y倒入x
            {
                //如果y全部倒入x，x都没能满，重点！！！
                if(frontX + frontY < x) {
                    int tempX = frontY + frontX;
                    int tempY = 0;
                    if(numberMap[tempX * 10000 + tempY] == false) {
                        numberMap[tempX * 10000 + tempY] = true;
                        needFindDeque.push_back(tempX * 10000 + tempY);
                    }
                }
                //y倒入x，还有剩余
                else {
                    int tempX = x;
                    int tempY = frontY - (x - frontX);
                    if(numberMap[tempX * 10000 + tempY] == false) {
                        numberMap[tempX * 10000 + tempY] = true;
                        needFindDeque.push_back(tempX * 10000 + tempY);
                    }
                }
            }
        }
        //如果所有可能的路径都做完了还不能得到z，那直接返回false
        return false;
}

通过代码