算法leetcode

力扣365-水壶问题

字数统计: 729字   |   阅读时长: 3分
, , ,

摘要: 本文详细拆解 力扣365-水壶问题，核心是隐式图搜索和裴蜀定理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来看一个数学问题，本题可以列出不定方程，可以通过数论中的裴蜀定理解决，也可以抽象成隐式图搜索，用 BFS 解决，不过状态转移很复杂。

$1 题目

有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

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

你可以：

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

提示:

1
1 <= jug1Capacity, jug2Capacity, targetCapacity <= 1e6

示例 1:
输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true
解释：来自著名的 “Die Hard”

示例 2:
输入: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
输出: false

示例 3:
输入: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
输出: true

$2 题解

算法1 : 隐式图搜索-BFS

BFS 出队后，枚举 6 中转移方式:

  • 倒满x
  • 倒空x
  • 倒满y
  • 倒空y
  • x倒入y
  • y倒入x

推出各自的新状态。用 unordered_set 记录状态是否访问过，自定义哈希函数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
pair<int, int> op(int type, const pair<int, int> &state, int x, int y)
{
    switch(type) {
        case 0 : return make_pair(x, state.second);
        case 1 : return make_pair(state.first, y);
        case 2 : return make_pair(0, state.second);
        case 3 : return make_pair(state.first, 0);
        case 4 :{
            int move = min(state.first, y - state.second);
            return make_pair(state.first - move, state.second + move);
        }
        case 5 :{
            int move = min(x - state.first, state.second);
            return make_pair(state.first + move, state.second - move);
        }
    }
    return make_pair(0, 0);
}

struct HashPair
{
    size_t operator()(const pair<int, int> &key) const noexcept
    {
        return size_t(key.first)*100000007 + key.second;
    }
};

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        unordered_set<pair<int,int>, HashPair> mark;
        queue<pair<int,int> > q;
        q.push(make_pair(0, 0));
        while(!q.empty())
        {
            auto f = q.front();
            q.pop();
            if(f.first + f.second == z)
                return true;
            for(int i = 0; i < 6; i++) 
            {
                auto next = op(i, f, x, y);
                if(mark.find(next) != mark.end())
                    continue;
                mark.insert(next);
                q.push(next);
            }
        }
        return false;
    }
};

算法2 : 数论-裴蜀定理

裴蜀定理的原理参考文章 同余。

由裴蜀定理： $ax + by = z$ 有解 $\Leftrightarrow$ z 是 gcd(x, y) 的倍数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(z ==0) return true;
        if(x == y && y == 0) return false;
        if(x == 0 && y != z) return false;
        if(y == 0 && x != z) return false;
        if(x + y < z) return false;
        return z % gcd(x, y) == 0;
    }
}
Share