題目
水壺問題
鏈接可能點不進去，所以我把完整的題目寫在了下面。
有兩個容量分別為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。
這題的標簽是數學，一般數學標簽的題都是有規(guī)律可循或者它本質就是一個數學定理。比如這道題燈泡開關答案是sqrt(n)，這道題我是通過找規(guī)律做出來的，手撕了n=1-8所有的情況后發(fā)現的。
回到這道題，開始看到這道題我一點思路都沒有，做了半年的算法了發(fā)現數學和動態(tài)規(guī)劃標簽的題是最難找到思路的。于是乎我去谷歌了一下，在我寫這篇文章的時候我搜到的思路千篇一律：判斷z是否能被x和y的最大公約數整除；反正我是想不到的。
看來這確實是一個定理沒跑了。那有沒有什么其他的方法來做這道題呢？
Accept
其實這道題你可以類比為有向連通圖，路徑由題目中給出的三種操作創(chuàng)建，節(jié)點就是兩杯水的多少，然后利用廣度/深度搜索算法來做這個題。
解釋一下路徑怎么來
對于示例 1，最開始兩杯水都是0 0。
0 0和0 5之間存在一條路徑，因為他們可以通過第一個操作進行連接。
為什么是有向圖
依然對于示例 1，假設目前兩杯水為2 2。
2 2能到達3 1，只需要y的水倒入x即可，但是反過來3 1是沒辦法直接到達2 2的。
廣度/深度搜索需要一個起始節(jié)點，我們可假設一個初始狀態(tài)比如裝滿x來模擬。
因為此有向圖中存在環(huán)。
解釋一下為何存在環(huán)
依然對于示例 1
0 0能到0 5，0 5同樣能到0 0。
所以我們需要記憶之前走過的點，后續(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轉成一維來表示，這個值同時也類比于廣度搜索中的節(jié)點。
//num = x * 10000 + y numberMap用來記錄已經走過的路，后續(xù)不會再走，你也可以用其他方式表示節(jié)點，后續(xù)解析的時候對應著來就好了。
//這里使用了哈希表，因為我們后面經常會查詢此表，把查詢時間降低為O(1)提升算法速度。
unordered_map<int, bool> numberMap;
numberMap[x * 10000 + 0] = true;
//雙端隊列，存放需要遍歷的點。
deque<int> needFindDeque;
needFindDeque.push_back(x * 10000 + 0);
//如果可以繼續(xù)走，那就一直走
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;
}
通過代碼
