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;}

//使用哈希函数进行优化，自定义哈希函数。
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];}

方法二 数学

数学理论看：官方题解

时间复杂度：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;
}

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