0 智力题
如何使用5L和6L水桶,得到3L水?
解答:
先用5升的容器灌满水,倒入6升容器里,
再用5升容器灌满水,用这个水把6升容器灌满,
5升容器里只有4升水,把6升容器里的水倒掉,
把5升容器里的水倒入6升容器,这样6升容器里有4升水。
把5升容器灌满水,用这个水再把6升容器灌满,5升容器里就只有3升水了。
以前看技术岗的面试智力题看到了这道倒水的题目,当时想半天没想出来,
后面发现Leetcode里竟然有专门针对这类题的程序:
1 LeetCode 365:水壶问题 [中等] [DFS]
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?
如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。你允许:
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水,直到装满或者倒空
示例 1:
输入: x = 3, y = 5, z = 4
输出: True示例 2:
输入: x = 2, y = 6, z = 5
输出: False
解法1:深度优先搜索
明确倒水的操作有以下几种情况:
1 | 把 X 壶的水灌进 Y 壶,直至灌满或倒空; |
使用remain_x,remain_y
记录当前X,Y壶中水量状态,每次都进行深度优先搜索操作。使用栈的数据结构,每次从栈中弹出状态进行深度优先遍历,把状态压入栈,直到栈空或者达到要求。
C++ 新的关联容器unordered_set
内部实现是基于哈希表(hashtable)
深搜可能会导致陷入无止境的递归,因此我们还需要使用一个哈希结合(HashSet)存储所有已经搜索过的 remain_x, remain_y 状态,保证每个状态至多只被搜索一次
1 | using XY = pair<int,int>; |
解法2:数学思想,贝祖定理
每次操作只会让桶里的水总量
增加 x,
增加 y,
减少 x,
减少 y。
贝祖定理
对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性不定方程(称为裴蜀等式):
若a,b是整数,且gcd(a,b)=d,
那么对于任意的整数x,y,ax+by都一定是d的倍数,
特别地,一定存在整数x,y,使ax+by=d成立。
总结起来我们可以认为每次操作只会给水量带来x或者y的变化。
我们的目标变为:找到一对整数a,b,使得
ax + by = z
而只要满足z<=x+y
,且这样的a,b存在,则可以达到目标。
贝祖定理中,x+by=z
有解当且仅当 z
是 x,y
的最大公约数的倍数。
因此我们只需要找到 x,y 的最大公约数并判断 z 是否是它的倍数即可。
1 | class Solution { |
数学方法真的简单很多,但是如果不看题解都不知道有这个定理(手动狗头