智力题

Question

bobo老师，水桶的这道智力题其实在leetcode上有的题目，对应365 水壶问题。只是两桶水的容量和target不是固定的。

说来很巧，这道题是我之前刷题的时候随机一题碰到的，那时候看这道题没有任何思路，直接把网页都关了。之后买了这门课程正好讲到这道题我也是很惊讶的，再回头看我曾经没有思路的题目，已经感到不再困难了。感谢bobo老师！：）

其实我算法和数据结构的基础都是由bobo老师打牢的，再配合上leetcode上的题目无意中的进步已经非常之大。我认为数据结构相当于内力，算法相当于招式，而刷题就相当于实战经验。只有地基打好了，实战才会有意义。（我也是一个实打实的武学迷hhhh，我愿意称bobo老师的课为《九阴真经》）
第一次的时候看bobo老师的《玩儿转数据结构》还是很吃力的，现在看bobo老师的图论已经没有这种感觉了，甚至还会产生我自己的一些想法。因此我希望bobo老师能够再出一些有意义的课程。再次感谢bobo老师！：）

Answer 1

liuyubobobo 2021-01-28 01:29:51

大赞！我才知道力扣上有这个问题呢。如果早知道，我的课程代码就直接基于这个问题写了。谢谢你的推荐：）

也谢谢你的肯定，我会继续努力的，你也加油！：）

• 提问者 梦想强大的人i #1

  bobo老师，由于回复不能添加代码块，我在下面有一个新疑问哦，不知道你能不能看得到，就在这边先回复一下：）

Answer 2

提问者 梦想强大的人i 2021-01-28 14:57:37

bobo老师，我的代码超时了，凝重.jpg。有没有什么优化的方法，为什么力扣官方题解使用的dfs都比俺的bfs要快。。

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(x<0||y<0||z<0)
            return false;
        if(x==0||y==0)
            return x==z||y==z;
        vector<vector<bool>> visited(x+1,vector<bool>(y+1,false));
        queue<pair<int,int>> qu;
        qu.push(make_pair(0,0));
        visited[0][0]=true;
        while(!qu.empty()){
            pair<int,int> cur=qu.front();
            qu.pop();
            vector<pair<int,int>> choice;
            choice.push_back(make_pair(0,cur.second));
            choice.push_back(make_pair(cur.first,0));
            choice.push_back(make_pair(x,cur.second));
            choice.push_back(make_pair(cur.first,y));
            int left=min(cur.first,y-cur.second);
            int right=min(x-cur.first,cur.second);
            choice.push_back(make_pair(cur.first-left,cur.second+left));
            choice.push_back(make_pair(cur.first+right,cur.second-right));
            for(auto[a,b]:choice){
                if(!visited[a][b]){
                    visited[a][b]=true;
                    qu.push(make_pair(a,b));
                    if(a==z||b==z||a+b==z)
                        return true;
                }
            }
        }
        return false;
    }
};

• liuyubobobo #1

  这个问题数据规模确实有些大，x 和 y 可以达到 10^6，x * y 的哦空间就可以到 10^12。实际上不是 10^12 的所有位置都是有效状态的，所以使用一个哈希表更合适。我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0365-Water-and-Jug-Problem/cpp-0365/main.cpp 另外，力扣中文站官方题解提到的数学方法，有兴趣可以看一看：）继续加油！：）