湖北网站推广服务,网站建设一年600,南昌高端网站开发费用表,做网站得基础2024.1.28 题目来源我的题解方法一 深度搜索#xff08;DFS#xff09;/广度搜索#xff08;BFS#xff09;方法二 数学 题目来源
力扣每日一题#xff1b;题序#xff1a;365
我的题解
方法一 深度搜索#xff08;DFS#xff09;/广度搜索#xff08;BFS#xff… 2024.1.28 题目来源我的题解方法一 深度搜索DFS/广度搜索BFS方法二 数学 题目来源
力扣每日一题题序365
我的题解
方法一 深度搜索DFS/广度搜索BFS 首先对题目进行建模。观察题目可知在任意一个时刻此问题的状态可以由两个数字决定X 壶中的水量以及 Y 壶中的水量。 在任意一个时刻我们可以且仅可以采取以下几种操作 把 X 壶的水灌进 Y 壶直至灌满或倒空 把 Y 壶的水灌进 X 壶直至灌满或倒空 把 X 壶灌满 把 Y 壶灌满 把 X 壶倒空 把 Y 壶倒空。 因此本题可以使用深度优先搜索来解决。搜索中的每一步以 cap1, cap2 作为状态即表示 X 壶和 Y 壶中的水量。在每一步搜索时我们会依次尝试所有的操作递归地搜索下去。这可能会导致我们陷入无止境的递归因此我们还需要使用一个哈希结合HashSet存储所有已经搜索过的 cap1, cap2 状态保证每个状态至多只被搜索一次。但是由于数据量问题导致递归空间不足因此最终使用广度优先实现。 时间复杂度O(xy)状态数最多有 (x1)(y1)种对每一种状态进行深度优先搜索的时间复杂度为 O(1)因此总时间复杂度为 O(xy)。 空间复杂度O(xy),由于状态数最多有 (x1)(y1) 种哈希集合中最多会有 (x1)(y1) 项因此空间复杂度为 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;}Queueint[] queue new LinkedList();queue.offer(new int[]{0, 0});SetLong 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;}Queueint[] queue new LinkedList();queue.offer(new int[]{0, 0});SetLong 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(jug1Capacityjug2CapacitytargetCapacity)return false;if(jug1Capacity0||jug2Capacity0)return targetCapacity0||jug1Capacityjug2CapacitytargetCapacity;return targetCapacity%gcd(jug1Capacity,jug2Capacity)0;
}
public int gcd(int x,int y){int zx%y;while(z!0){xy;yz;zx%y;}return y;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
