智力题
来源：7-5 代码实现一道智力题
梦想强大的人i
2021-01-27
bobo老师，水桶的这道智力题其实在leetcode上有的题目，对应365 水壶问题。只是两桶水的容量和target不是固定的。
说来很巧，这道题是我之前刷题的时候随机一题碰到的，那时候看这道题没有任何思路，直接把网页都关了。之后买了这门课程正好讲到这道题我也是很惊讶的，再回头看我曾经没有思路的题目，已经感到不再困难了。感谢bobo老师！：）
其实我算法和数据结构的基础都是由bobo老师打牢的，再配合上leetcode上的题目无意中的进步已经非常之大。我认为数据结构相当于内力，算法相当于招式，而刷题就相当于实战经验。只有地基打好了，实战才会有意义。（我也是一个实打实的武学迷hhhh，我愿意称bobo老师的课为《九阴真经》）
第一次的时候看bobo老师的《玩儿转数据结构》还是很吃力的，现在看bobo老师的图论已经没有这种感觉了，甚至还会产生我自己的一些想法。因此我希望bobo老师能够再出一些有意义的课程。再次感谢bobo老师！：）
写回答
2回答
-
大赞！我才知道力扣上有这个问题呢。如果早知道，我的课程代码就直接基于这个问题写了。谢谢你的推荐：）
也谢谢你的肯定，我会继续努力的，你也加油！：）
212021-01-28 -
梦想强大的人i
提问者
2021-01-28
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; } };012021-01-28
相似问题