水壶问题

题目

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

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

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空.(From the famous "Die Hard" example)
示例 1:

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

示例 2:

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

思路

做这种游戏,本质上就是一个初始状态根据不同的变化产生的一个图.现在需要判断的就是图上的某个节点是否满足要求.所以实际上是一个广度优先搜索的遍历.

代码

广度优先搜索的方法

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        //做这种游戏,本质上就是一个初始状态根据不同的变化产生的一个图.现在需要判断的就是图上的某个节点是否满足要求.所以实际上是一个广度优先搜索的遍历.
        //特殊条件的判断
        if(z == 0){
            return true;
        }
        if(x + y < z){
            return false;
        }
        //初始状态的点
        Point init = new Point(0,0);
        //遍历所需的列表
        Queue<Point> list = new LinkedList<>();
        //记录已经判断的状态点.不然会无限循环
        Set<Point> set = new HashSet<>();
        //加入初始状态点
        list.offer(init);
        while(!list.isEmpty()){
            Point poll = list.poll();
            int tempX = poll.x;
            int tempY = poll.y;
            if(tempX == z || tempY == z || tempX + tempY == z){
                return true;
            }
            List<Point> nextList = getNextList(tempX,tempY,x,y);
            for(int i = 0;i < nextList.size();i++){
                if(!set.contains(nextList.get(i))){
                    list.add(nextList.get(i));
                    set.add(nextList.get(i));
                }
            }
        }
        return false;
    }

    private List<Point> getNextList(int tempX,int tempY,int x,int y) {
        //有八种情况,装满a,装满b,清空a,清空b,a向b倒b不满,a向b倒a有剩余,b向a倒a不满,b向a倒b有剩余.
        List<Point> result = new ArrayList<>();
        //装满a
        Point point1 = new Point(x,tempY);
        //装满b
        Point point2 = new Point(tempX,y);
        //清空a
        Point point3 = new Point(0,tempY);
        //清空b
        Point point4 = new Point(tempX,0);
        //a向b倒b不满
        Point point5 = new Point(0,tempX+tempY);
        //a向b倒a有余
        Point point6 = new Point(tempX-y+tempY,y);
        //b向a倒a不满
        Point point7 = new Point(tempY+tempX,0);
        //b向a倒a有余
        Point point8 = new Point(x,tempY-x+tempX);
        //由于不是所有的点都有八种状态,因此需要根据每个点的状态来对应添加相应状态
        //当水不满时加水
        if (tempX < x){
            result.add(point1);
        }
        if(tempY < y){
            result.add(point2);
        }
        //当水满时倒水
        if(tempX > 0){
            result.add(point3);
        }
        if(tempY > 0){
            result.add(point4);
        }
        //有剩余才会倒
        if(tempX - y + tempY > 0){
            result.add(point6);
        }
        if(tempY-x+tempY > 0){
            result.add(point8);
        }
        //限制条件
        if(tempX+tempY<y){
            result.add(point5);
        }
        if (tempX + tempY < x){
            result.add(point7);
        }
        return result;
    }

    public class Point{
        int x;
        int y;
        public Point(int x,int y){
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}

数学解法

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if(z == 0){
            return true;
        }
        if(x + y < z){
            return false;
        }
        if(x == 0 || y == 0){
            return x + y == z;
        }
        return z % gcd(x,y) == 0;
    }

    public int gcd(int m,int n) {
       int t;
        if(m<n) {
            t=m;
        }else {
            t=n;
        }
        while(m%t!=0||n%t!=0){
            t--;
        }
        return t;
    } 
}