[LeetCode解题报告] 365. 水壶问题

一、 题目

1. 题目描述

2. 原题链接

链接: 365. 水壶问题

二、 解题报告

1. 思路分析

 水壶倒水问题非常经典，这里用BFS解决复杂度较高，实际上可以用裴蜀定理，直接一个GCD最大公倍数的复杂度就可以搞定，在此不展开。
1

• 为了方便我们即两个水壶的容量是j1,j2,目标值是t. 过程中两个水壶实际装水量记a,b。
• 我们这里用BFS做，状态记录两个水壶分别的装水量，即（a,b）
• 当a+b==t时，达成目标，返回True。
• 我们详细分析题目给出的每步中的三种操作，发现其实不是三种：
• 把a变成0或j1(2种操作）
• 把b变成0或j2(2种)
• 前两个操作比较简单，共四种；第三个操作看似是一个卷积四种，但我们仔细分析发现只有两种：
• 假设从a向b倒水，直到装满或倒空，这里只会b装满或a倒空，a不会变满；同时这两种操作不能分别达成，因为ab在某个状态是固定的。但可以同时达成。也就是说这个动作只会有一个转移结果。
• 具体转移到多少，即从a向b倒多少水，显然取决于a有多少水或b还能乘多少，diff=min(a,j2-b)，然后计算转移后的状态即可；
• 反过来从b向a倒水同理。
• 因此我们只需在代码里模拟这个状态转移过程并加入队列即可。
• 为了不重复搜索还需要一个visited集合来记录已访问过的状态。

2. 复杂度分析

最坏时间复杂度O(x×y)

3. 代码实现

BFS。

class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
        vis = {(0,0)}
        q = deque(vis)
        while q:
            a,b = q.popleft()
            if a+b == targetCapacity:
                return True 
            
            for c,d in (0,b),(a,0),(jug1Capacity,b),(a,jug2Capacity):            
                if (c,d) not in vis:
                    vis.add((c,d))
                    q.append((c,d))
            diff = min(jug2Capacity-b,a)
            c,d = a-diff,b+diff
            if (c,d) not in vis:
                vis.add((c,d))
                q.append((c,d))
            diff = min(jug1Capacity-a,b)
            c,d = a+diff,b-diff
            if (c,d) not in vis:
                vis.add((c,d))
                q.append((c,d))
                
        return False
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

三、 本题小结

1. 遇到这种问题不要慌直接搜索。
2. 当搜索状态无限多的时候可以随手想一个上下边界。当然这题显然不是无限多，因此用vis即可。