LeetCode 365.水壺問題

題目

水壺問題
鏈接可能點(diǎn)不進(jìn)去锉矢，所以我把完整的題目寫在了下面藕溅。

有兩個容量分別為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。

這題的標(biāo)簽是數(shù)學(xué)蚣驼，一般數(shù)學(xué)標(biāo)簽的題都是有規(guī)律可循或者它本質(zhì)就是一個數(shù)學(xué)定理魄幕。比如這道題燈泡開關(guān)答案是sqrt(n)，這道題我是通過找規(guī)律做出來的颖杏，手撕了n=1-8所有的情況后發(fā)現(xiàn)的纯陨。
回到這道題，開始看到這道題我一點(diǎn)思路都沒有，做了半年的算法了發(fā)現(xiàn)數(shù)學(xué)和動態(tài)規(guī)劃標(biāo)簽的題是最難找到思路的翼抠。于是乎我去谷歌了一下咙轩，在我寫這篇文章的時候我搜到的思路千篇一律：判斷z是否能被x和y的最大公約數(shù)整除；反正我是想不到的阴颖。
看來這確實(shí)是一個定理沒跑了活喊。那有沒有什么其他的方法來做這道題呢？

Accept

其實(shí)這道題你可以類比為有向連通圖量愧，路徑由題目中給出的三種操作創(chuàng)建钾菊，節(jié)點(diǎn)就是兩杯水的多少，然后利用廣度/深度搜索算法來做這個題偎肃。

解釋一下路徑怎么來
對于示例 1煞烫，最開始兩杯水都是0 0。
0 0和0 5之間存在一條路徑累颂，因?yàn)樗麄兛梢酝ㄟ^第一個操作進(jìn)行連接滞详。
為什么是有向圖
依然對于示例 1，假設(shè)目前兩杯水為2 2紊馏。
2 2能到達(dá)3 1料饥，只需要y的水倒入x即可，但是反過來3 1是沒辦法直接到達(dá)2 2的朱监。

廣度/深度搜索需要一個起始節(jié)點(diǎn)岸啡，我們可假設(shè)一個初始狀態(tài)比如裝滿x來模擬。
因?yàn)榇擞邢驁D中存在環(huán)赌朋。

解釋一下為何存在環(huán)
依然對于示例 1
0 0能到0 5凰狞，0 5同樣能到0 0。

所以我們需要記憶之前走過的點(diǎn)沛慢，后續(xù)不要再走赡若，否則會死循環(huán)。
此題我們用廣度來做即可团甲，深度也一樣的思路就不再給出了逾冬。

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轉(zhuǎn)成一維來表示，這個值同時也類比于廣度搜索中的節(jié)點(diǎn)躺苦。
        //num = x * 10000 + y numberMap用來記錄已經(jīng)走過的路身腻，后續(xù)不會再走，你也可以用其他方式表示節(jié)點(diǎn)匹厘，后續(xù)解析的時候?qū)?yīng)著來就好了嘀趟。
        //這里使用了哈希表，因?yàn)槲覀兒竺娼?jīng)常會查詢此表愈诚，把查詢時間降低為O(1)提升算法速度她按。
        unordered_map<int, bool> numberMap;
        numberMap[x * 10000 + 0] = true;
        //雙端隊(duì)列牛隅，存放需要遍歷的點(diǎn)。
        deque<int> needFindDeque;
        needFindDeque.push_back(x * 10000 + 0);
        //如果可以繼續(xù)走酌泰，那就一直走
        while (!needFindDeque.empty()) {
            //得到此時兩個瓶子的值
            int frontValue = needFindDeque.front();
            needFindDeque.pop_front();
            //這里應(yīng)該不難理解吧媒佣，一維還原為二維
            int frontX = frontValue / 10000;
            int frontY = frontValue % 10000;
            //看看是否能得到z
            if(z == frontX || z == frontY || z == frontX + frontY) {
                return true;
            }
            //不能得到z，那么我們現(xiàn)在有題目中的幾條路可以走
            //1.裝滿x
            {
                int tempX = x;
                //如果已經(jīng)走過了陵刹，不需要添加
                if(numberMap[tempX * 10000 + frontY] == false) {
                    numberMap[tempX * 10000 + frontY] = true;
                    needFindDeque.push_back(tempX * 10000 + frontY);
                }
            }
            //2.裝滿y
            {
                int tempY = y;
                //如果已經(jīng)走過了默伍，不需要添加
                if(numberMap[frontX * 10000 + tempY] == false) {
                    numberMap[frontX * 10000 + tempY] = true;
                    needFindDeque.push_back(frontX * 10000 + tempY);
                }
            }
            //3.清空x
            {
                //如果已經(jīng)走過了，不需要添加
                if(numberMap[0 * 10000 + frontY] == false) {
                    numberMap[0 * 10000 + frontY] = true;
                    needFindDeque.push_back(0 * 10000 + frontY);
                }
            }
            //4.清空y
            {
                //如果已經(jīng)走過了衰琐，不需要添加
                if(numberMap[frontX * 10000 + 0] == false) {
                    numberMap[frontX * 10000 + 0] = true;
                    needFindDeque.push_back(frontX * 10000 + 0);
                }
            }
            //5.x倒入y
            {
                //如果x全部倒入y也糊，y都沒能滿，重點(diǎn)５舛Ｏ陨琛框弛！
                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都沒能滿瑟枫，重點(diǎn)６犯恪！慷妙！
                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;
}

通過代碼