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;	//只有一个壶时，看能不能直接得到zint 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。