Leetcode 365. 水壶问题

题目

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

装满任意一个水壶清空任意一个水壶从一个水壶向另外一个水壶倒水，直到装满或者倒空

测试样例

示例 1: (From the famous “Die Hard” example)

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

示例 2:

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

题解

正常来说是BFS，是可以建图实现的 但本题解可以说是利用了贪心的思路，具体是不是正解我也无法考证。我的思路是利用大壶与小壶的一个差进行构建，也就是说，优先小壶装水，如果装满了就往大壶中倒；大壶满了，则倒出。小壶水不满，大壶为空，则小壶往大壶倒。也就是z升的水一定会在大壶中。详细过程见代码

代码

bool canMeasureWater(int x, int y, int z) { if(x > y) swap(x,y); if(z == x || z==0) return true; if(x==0 && z!=y) return false; //只有一个壶时，看能不能直接得到z int i=0,j=0; //分别表示两个壶的水量 while(j+i != z){ if(i == 0) i = x; //小壶没有水就加满 else if(i == x){ //小壶满了，我们可以考虑把它装到大壶中 if(i <= y-j){ //大壶不会满 j += i; i = 0; }else{ //大壶会满 i -= y-j; j = y; } }else if(j == 0){ //大壶没有水，我们考虑把小壶中的水倒进来 j = i; i = 0; }else if(j == y){ //大壶满了，倒出 j = 0; } if(i+y!=z && i==x && j==y) return false; //两个壶都满了，却不能达到条件 } return true; }

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/water-and-jug-problem 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。