精华内容
下载资源
问答
  • LeetCode 水壶问题

    2020-03-21 20:43:52
    根据裴蜀定理,求最大公约数,判断是否有解来解决《水壶问题

    水壶问题


    题目来源:https://leetcode-cn.com/problems/water-and-jug-problem/

    题目


    有两个容量分别为 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
    

    解题思路


    思路:裴蜀定理

    裴蜀定理是关于最大公约数的定理。

    对于任何整数 a、b 和 m,d 为 a 及 b 的最大公约数,关于未知数 x 和 y 的线性不定方程:

    ax+by=max + by = m

    有整数解时,当且仅当 m 是 a 及 b 的最大公约数 d 的倍数。

    审题可得:其实每次操作可以认为是让壶里的水总量增加 x,增加 y,减少 x,减少 y。

    这里涉及到一个壶的水不空的情况下,那么对于上面的结论来说明显是不成立。不着急,这里解释下:

    对于示例 1,题目给出 x = 3, y = 5, z = 4。

    尝试如何让壶盛放 4 升的水。(这里将可盛放 x 升水的壶设为 A,可盛放 y 升水的壶设为 B,形如 (0, 0),表示两个壶盛放的水)

    1. 首先将 B 装满,此时两个壶盛放水的情况:(0, 5);
    2. 将 B 壶的水倒入 A 中,两个壶的情况:(3, 2);
    3. 将 A 壶中的水倒掉,两个壶的情况:(0, 2);
    4. 再次将 B 壶中的水倒入 A 中,此时:(2, 0);
    5. 将 B 壶装满,此时两个壶的情况:(2, 5);
    6. 将 B 壶的水倒入 A 中直至倒满,此时:(3, 4)。

    这个时候 ,B 壶中的水为 4 升,即是所求得结果。

    • 在这里,我们可以观察到,在操作的过程中,是不会让两个壶同时有水且不满的情况发生。
    • 而且,给未满的壶盛放水并没有意义。假设给一个未满的壶盛放水时,如果另外一个壶是满的,那这种情况就相当于初始状态下直接给两个壶装满;如果另一个壶是空的,那这个就相当于是直接在初始状态下,给当前壶盛满水。
    • 同样的,将未满的壶中的水倒掉也是没有意义的。假设倒掉一个未满的壶中的水,如果另外一个壶是满的,这种情况就相当于初始状态下直接给另外一个壶装满水;如果另外一个壶是空的,那么这将又回到初始的状态。

    所以这里就可以明确前面所得的结论:每次操作,水的总量只会带来 x 或 y 的变化量。

    现在我们将问题转化为求一对整数 a,b,使得

    ax+by=zax + by = z

    只要满足 zx+yz \leq x+y,表示目标可得。

    注意,这里跟上面的裴蜀定理的式子有所不同,这里 a,b 表示所需求得的目标,而 x,y 已知。(与裴蜀定理式子刚好反过来)。

    由题可知:

    a0,b0a \geq 0, b \geq 0 时,可求得目标;

    a<0a<0 时,则需要进行以下操作:(延用上面的 A 壶,B 壶)

    • 先往 B 壶装满水;
    • 将 B 壶的水往 A 壶倒;
    • 这个时候,如果 B 壶还有水,表示 A 壶满了。将 A 壶的水倒掉,将 B 壶剩余的水倒入 A 壶中。

    重复上面的操作,直到对 A 壶进行 a 次清空,而对 B 壶进行 b 次倒水操作。

    b<0b<0 时,跟上面的情况类似,将对 A 壶和 B 壶的操作调换过来即可。

    根据裴蜀定理, ax+by=zax+by=z 有解,当且仅当 z 是 x,y 的最大公约数的倍数。所以我们只要找到 x,y 的最大公约数,然后判断 z 是否是这个最大公约数的倍数即可求得答案。

    代码实现


    class Solution:
        def canMeasureWater(self, x: int, y: int, z: int) -> bool:  
            import math
            if x + y < z:
                return False
            if x == 0 or y == 0:
                return z == 0 or x + y == z
            return z % math.gcd(x, y) == 0
    

    实现结果


    实现结果


    以上就是根据裴蜀定理,求最大公约数,判断是否有解来解决《水壶问题》的主要内容。


    欢迎关注微信公众号《书所集录》

    展开全文
  • Leetcode365 水壶问题

    2020-03-21 17:01:04
    leetcode 水壶问题 水壶问题 每日一题,有点偏数学,但是可以用图论的BFD 和DFS 求解。 关于二叉树的BFS和DFS已经进行过介绍,本文主要是图论的BFS和DFS。 首先对题目进行建模。观察题目可知,在任意一个时刻,此...

    leetcode 水壶问题

    水壶问题

    在这里插入图片描述每日一题,有点偏数学,但是可以用图论的BFD 和DFS 求解。
    关于二叉树的BFS和DFS已经进行过介绍,本文主要是图论的BFS和DFS。
    首先对题目进行建模。观察题目可知,在任意一个时刻,此问题的状态可以由两个数字决定:X 壶中的水量,以及 Y 壶中的水量。

    在任意一个时刻,我们可以且仅可以采取以下几种操作或者是只存在如下的状态转移可能:

    把 X 壶的水灌进 Y 壶,直至灌满或倒空;
    把 Y 壶的水灌进 X 壶,直至灌满或倒空;
    把 X 壶灌满;
    把 Y 壶灌满;
    把 X 壶倒空;
    把 Y 壶倒空。
    

    因此可以用搜索的方法解决问题。

    首先是广度优先

    class Solution(object):
        def canMeasureWater(self, x, y, z):
            """
            :type x: int
            :type y: int
            :type z: int
            :rtype: bool
            """
            # bfs
            from collections import deque
            queue = deque([[0, 0]]) # 双向队列
            visited = set([(0, 0)]) # 标记哪些状态已经处理过了
    		# 开始递推状态
            while queue:
                cur_x, cur_y = queue.pop()  # 广度优先 
                # 结束循环的条件
                if z in [cur_x, cur_y, cur_x + cur_y]:
                    return True 
                # 可能转移到下列可能的状态
                for item in [
                    # 加满水
                    (x, cur_y), (cur_x, y),
                    # 清空水
                    (0, cur_y), (cur_x, 0),
                    # x -> y
                    (cur_x + cur_y - y, y) if cur_x + cur_y >= y else (0, cur_x + cur_y),
                    # y -> x
                    (x, cur_x + cur_y - x) if cur_x + cur_y >= x else (cur_x + cur_y, 0)]:
                    # 为防止成环,对邻居进行标记
                    if item not in visited:
                        queue.appendleft(item)
                        visited.add(item)
            return False
    

    这种方法的在得到结果的时候就会结束,不用遍历整个图,相对复杂度比较低。

    深度优先

    class Solution:
        def canMeasureWater(self, x: int, y: int, z: int) -> bool:  
            visited = set()
    
            def helper(cur_x, cur_y):
                # print(cur_x, cur_y)
                if z in [cur_x, cur_y, cur_x + cur_y]:
                    return True
                for item in [
                    # 加满水
                    (x, cur_y), (cur_x, y),
                    # 清空水
                    (0, cur_y), (cur_x, 0),
                    # x -> y
                    (cur_x + cur_y - y, y) if cur_x + cur_y >= y else (0, cur_x + cur_y),
                    # y -> x
                    (x, cur_x + cur_y - x) if cur_x + cur_y >= x else (cur_x + cur_y, 0)]:
                    if item not in visited:
                        visited.add(item)
                        if helper(*item): return True
                        visited.remove(item)
    
                return False
    
            return helper(x, y)
    

    数学方法

    裴蜀定理

    若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立

    class Solution:
        def canMeasureWater(self, x: int, y: int, z: int) -> bool:  
            import math
            if x + y < z: return False
            if x == z or y == z or x + y == z: return True
            return z % math.gcd(x, y) == 0
    
    
    展开全文
  • leetcode-水壶问题

    2020-03-21 20:18:33
     题目来自LeetCode,链接:水壶问题。具体描述为:有两个容量分别为x升和y升的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好z升的水?如果可以,最后请用以上水壶中的一或两个来盛放取得的z...

     题目来自LeetCode,链接:水壶问题。具体描述为:有两个容量分别为x升和y升的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好z升的水?如果可以,最后请用以上水壶中的一或两个来盛放取得的z升水。你允许:

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

     示例1:

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

     示例2:

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

     首先,可以用一个二元组(X中水量,Y中水量)表示在任意一个时刻的状态。每个时刻都有以下几个可选操作:

    • 把X的水倒进Y,直至Y满或X空;
    • 把Y的水倒进X,直至X满或Y空;
    • 把X装满;
    • 把Y装满;
    • 把X倒空;
    • 把Y倒空。

     因此,本题可以使用深度优先搜索BFS来解决。在每一步搜索时,依次尝试上述所有的操作,递归地搜索下去。同时还需要用一个哈希表存储所有已经搜索过的状态,从而保证每个状态至多只被搜索一次。

     JAVA版代码如下:

    class Solution {
        public boolean canMeasureWater(int x, int y, int z) {
            Set<String> set = new HashSet<>();
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[] {0, 0});
            while (!queue.isEmpty()) {
                int[] item = queue.poll();
                if (item[0] == z || item[1] == z || item[0] + item[1] == z) {
                    return true;
                }
                if (!set.add(item[0] + "," + item[1])) {
                   continue;
                }
                queue.offer(new int[] {x, item[1]});
                queue.offer(new int[] {item[0],y});
                queue.offer(new int[] {0, item[1]});
                queue.offer(new int[] {item[0], 0});
                queue.offer(new int[] {Math.max(0, item[0] - (y - item[1])), Math.min(item[1] + item[0], y)});
                queue.offer(new int[] {Math.min(item[0] + item[1], x), Math.max(0, item[1] - (x - item[0]))});
            }
            return false;
        }
    }
    

     这个直接就超时了,因为状态还是有点太多了啊。

     然后参考评论区的一种简单BFS。这里不去关注(X中水量,Y中水量)这个二元状态,改为关注总水量n。那么每次操作只会让桶里的水总量增加 x,增加 y,减少 x,或者减少 y。原因在于在题目所给的操作下,两个桶不可能同时有水且不满。

    • 首先,每次操作后都至少有一个桶是空的或者满的。
    • 其次,对一个不满的桶加水是没有意义的。因为如果另一个桶是空的,那么这个操作的结果等价于直接从初始状态给这个桶加满水;而如果另一个桶是满的,那么这个操作的结果等价于从初始状态分别给两个桶加满。所以这种增加量不是x或y的操作是无意义的。
    • 再次,把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的,那么这个操作的结果等价于回到初始状态;而如果另一个桶是满的,那么这个操作的结果等价于从初始状态直接给另一个桶倒满。所以这种减少量不是x或y的操作也是无意义的。

     有了上面的分析,现在我们就只有四个状态了,同样可以用BFS:

    • 增加x:相当于给X加满水,所以须满足n\ley以将全部水先转移到Y;
    • 增加y:相当于给Y加满水,所以须满足n\lex以将全部水先转移到X;
    • 减少x:相当于倒掉X的水,所以须满足n\gex以能先装满X再倒掉;
    • 减少y:相当于倒掉Y的水,所以须满足n\gey以能先装满Y再倒掉。

     JAVA版代码如下:

    class Solution {
        public boolean canMeasureWater(int x, int y, int z) {
            Set<Integer> set = new HashSet<>();
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(0);
            while (!queue.isEmpty()) {
                int n = queue.poll();
                if (n == z) {
                    return true;
                }
                if (n <= y && set.add(n + x)) {
                    queue.offer(n + x);
                }
                if (n <= x && set.add(n + y)) {
                    queue.offer(n + y);
                }
                if (n >= x && set.add(n - x)) {
                    queue.offer(n - x);
                }
                if (n >= y && set.add(n - y)) {
                    queue.offer(n - y);
                }
            }
            return false;
        }
    }
    

     提交结果如下:


     最后是数学解法。因为可以认为每次操作只会给水的总量带来x或者y的变化量,所以可以把目标改写成:找到一对整数 a,和b使得ax+by=zax+by=z。而只要满足 zx+yz\leq x+y,且这样的a和b存在,那么就可以达成目标。这是因为:

    • a0a\geq 0b0b\geq 0,那么显然可以通过倒满a次X和b次Y达成目标。

    • a<0a\lt 0,那么可以进行以下操作:

      • 往Y倒水;
      • 把Y的水倒入X;
      • 如果Y不为空,那么X肯定是满的,把X倒空,然后再把Y的水倒入X以保证Y是空的。

      重复以上操作直至某一步时将X倒空了a次,给Y倒了b次水。

    • b<0b\lt 0,方法同上,x 与 y 互换。

     然后就需要用到数学定理了,根据贝祖定理,ax+by=zax+by=z有解当且仅当z是x和y的最大公约数的倍数。因此我们只需要找到 x和y的最大公约数并判断z是否是它的倍数即可。

     JAVA版代码如下:

    class Solution {
        private int gcd(int x, int y) {
            while (true) {
                if (x % y == 0) {
                    return y;
                }
                else {
                    int temp = y;
                    y = x % y;
                    x = temp;
                }
            }
        }
        public boolean canMeasureWater(int x, int y, int z) {
            if (x + y < z) {
                return false;
            }
            if (x == 0 || y == 0) {
                return z == 0 || z == x + y;
            }
            int n = x > y ? gcd(x, y) : gcd(y, x);
            return z % n == 0;
        }
    }
    

     提交结果如下:


    展开全文
  • LeetCode 365 水壶问题

    2020-03-21 08:52:02
    有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水 你允许: 装满任意一个水壶 清空任意...
    题目

    题目链接
    有两个容量分别为 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

    题解
    • z = ax+by的时候返回true,进一步展开为z为x和y最大公约数的倍数的时候返回true
    • 需要处理特殊情况 当 x+y > z 的时候返回false,因为这个时候无论怎么用这两个杯子也无法恰好得到z升的水(理解题目)比如 x = 1 y = 1,z = 12 返回false
    • z == 0 的时候返回true
    class Solution {
    private:
        int getGcd(int x,int y){
            if(y == 0){
                return x;
            }else{
                return getGcd(y,x%y);
            }
        }    
    public:
        bool canMeasureWater(int x, int y, int z) {
            if(z == 0){
                return true;
            }
            if(x + y < z){
                return false;
            }
            int maxGcd = getGcd(x,y);
            return z % maxGcd == 0;
        }
    };
    
    展开全文
  • Java实现 LeetCode 365 水壶问题

    万次阅读 多人点赞 2020-03-10 19:09:46
    365. 水壶问题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。 你允许: 装满任意...
  • 题目描述: 有两个容量分别为 x升 和 y升 的水壶以及无限多...水壶问题就是两个壶的最小公约数与想得到的水的升数是否成倍数问题(除去几个特殊情况,特殊情况在代码中有写到) 当z是最小公约数的整数倍时,可以利用两
  • [leetcode]水壶问题

    2020-04-30 01:27:35
    题目 水壶问题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。 你允许: 装满任意...
  • leetcode 365题 水壶问题

    2020-03-21 18:06:04
    个人博客中有本文原文...leetcode 365题 水壶问题 题目 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中...
  • leetcode 365. 水壶问题

    2020-03-21 21:33:56
    水壶问题 题目详情 题目链接 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。 你...
  • class Solution { public boolean canMeasureWater(int x, int y, int z) { // 判断特例 if(x + y < z) return false; if(x == z || y == z || x + y == z) return true; return z % help(x, y) == 0;...
  • LeetCode 365. 水壶问题

    2020-03-21 11:26:33
    问题 有两个容量分别为x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的z升水。 你允许: 装满任意一个水壶 ...
  • 水壶问题 题目 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。 你允许: 装满...
  • Leetcode 365.水壶问题

    2019-01-07 19:54:00
    水壶问题 有两个容量分别为x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好z升的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的z升水。 你允许: 装满任意一个...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 219
精华内容 87
关键字:

leetcode水壶问题