2024.1.28力扣每日一题——水壶问题

题目来源

力扣每日一题；题序：365

我的题解

方法一 深度搜索（DFS）/广度搜索（BFS）

首先对题目进行建模。观察题目可知，在任意一个时刻，此问题的状态可以由两个数字决定：X 壶中的水量，以及 Y 壶中的水量。
在任意一个时刻，我们可以且仅可以采取以下几种操作：
　　把 X 壶的水灌进 Y 壶，直至灌满或倒空；
　　把 Y 壶的水灌进 X 壶，直至灌满或倒空；
　　把 X 壶灌满；
　　把 Y 壶灌满；
　　把 X 壶倒空；
　　把 Y 壶倒空。
因此，本题可以使用深度优先搜索来解决。搜索中的每一步以 cap1, cap2 作为状态，即表示 X 壶和 Y 壶中的水量。在每一步搜索时，我们会依次尝试所有的操作，递归地搜索下去。这可能会导致我们陷入无止境的递归，因此我们还需要使用一个哈希结合（HashSet）存储所有已经搜索过的 cap1, cap2 状态，保证每个状态至多只被搜索一次。但是由于数据量问题，导致递归空间不足，因此最终使用广度优先实现。

时间复杂度：O(xy)，状态数最多有 (x+1)(y+1)种，对每一种状态进行深度优先搜索的时间复杂度为 O(1)，因此总时间复杂度为 O(xy)。
空间复杂度：O(xy),由于状态数最多有 (x+1)(y+1) 种，哈希集合中最多会有 (x+1)(y+1) 项，因此空间复杂度为 O(xy)。

//未使用哈希函数进行优化，直接将两个杯子的值构建字符串，利用字符串类重写了哈希函数的特点保证集合中出现的内容唯一。

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;
       }
       Queue<int[]> queue = new LinkedList<>();
       queue.offer(new int[]{0, 0});
       Set<Long> seen = new HashSet<>();
       while (!queue.isEmpty()) {
           int[] state = queue.poll();
           int remain_x = state[0], remain_y = state[1];
           if (seen.contains(hash(state))) {
               continue;
           }
           seen.add(hash(state));
           if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
               return true;
           }
           // 把 X 壶灌满。
           queue.offer(new int[]{x, remain_y});
           // 把 Y 壶灌满。
           queue.offer(new int[]{remain_x, y});
           // 把 X 壶倒空。
           queue.offer(new int[]{0, remain_y});
           // 把 Y 壶倒空。
           queue.offer(new int[]{remain_x, 0});
           // 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
           queue.offer(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});
           // 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
           queue.offer(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});
       }
       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
26
27
28
29
30
31
32
33
34
35
36
37
38

//使用哈希函数进行优化，自定义哈希函数。
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;
     }
     Queue<int[]> queue = new LinkedList<>();
     queue.offer(new int[]{0, 0});
     Set<Long> seen = new HashSet<>();
     while (!queue.isEmpty()) {
         int[] state = queue.poll();
         int remain_x = state[0], remain_y = state[1];
         if (seen.contains(hash(state))) {
             continue;
         }
         seen.add(hash(state));
         if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
             return true;
         }
         // 把 X 壶灌满。
         queue.offer(new int[]{x, remain_y});
         // 把 Y 壶灌满。
         queue.offer(new int[]{remain_x, y});
         // 把 X 壶倒空。
         queue.offer(new int[]{0, remain_y});
         // 把 Y 壶倒空。
         queue.offer(new int[]{remain_x, 0});
         // 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
         queue.offer(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});
         // 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
         queue.offer(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});
     }
     return false;
 }

 private long hash(int[] state) {
     return (long) state[0] * 1000001 + state[1];
 }
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

方法二 数学

数学理论看：官方题解

时间复杂度：O(log(min(x,y)))，取决于计算最大公约数所使用的算法的时间复杂度
空间复杂度：O(1)

public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
    if(jug1Capacity+jug2Capacity<targetCapacity)
        return false;
    if(jug1Capacity==0||jug2Capacity==0)
        return targetCapacity==0||jug1Capacity+jug2Capacity==targetCapacity;
    return targetCapacity%gcd(jug1Capacity,jug2Capacity)==0;
}
public int gcd(int x,int y){
    int z=x%y;
    while(z!=0){
        x=y;
        y=z;
        z=x%y;
    }
    return y;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈