class Solution {
public:
bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
}
};
365. 水壶问题
有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。
如果可以得到 targetCapacity 升水，最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。
你可以：
示例 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
提示:
1 <= jug1Capacity, jug2Capacity, targetCapacity <= 106原站题解
golang 解法, 执行用时: 633 ms, 内存消耗: 129.8 MB, 提交时间: 2024-01-28 23:30:09
func canMeasureWater(x int, y int, z int) bool {
type pair struct{ x, y int }
vis := map[pair]bool{}
var dfs func(int, int) bool
dfs = func(i, j int) bool {
st := pair{i, j}
if vis[st] {
return false
}
vis[st] = true
if i == z || j == z || i+j == z {
return true
}
if dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0) {
return true
}
a := min(i, y-j)
b := min(j, x-i)
return dfs(i-a, j+a) || dfs(i+b, j-b)
}
return dfs(0, 0)
}
java 解法, 执行用时: 0 ms, 内存消耗: 39.2 MB, 提交时间: 2024-01-28 23:28:21
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (x + y < z) {
return false;
}
if (x == 0 || y == 0) {
return z == 0 || x + y == z;
}
return z % gcd(x, y) == 0;
}
public int gcd(int x, int y) {
int remainder = x % y;
while (remainder != 0) {
x = y;
y = remainder;
remainder = x % y;
}
return y;
}
// dfs
public boolean canMeasureWater2(int x, int y, int z) {
Deque<int[]> stack = new LinkedList<int[]>();
stack.push(new int[]{0, 0});
Set<Long> seen = new HashSet<Long>();
while (!stack.isEmpty()) {
if (seen.contains(hash(stack.peek()))) {
stack.pop();
continue;
}
seen.add(hash(stack.peek()));
int[] state = stack.pop();
int remain_x = state[0], remain_y = state[1];
if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
return true;
}
// 把 X 壶灌满。
stack.push(new int[]{x, remain_y});
// 把 Y 壶灌满。
stack.push(new int[]{remain_x, y});
// 把 X 壶倒空。
stack.push(new int[]{0, remain_y});
// 把 Y 壶倒空。
stack.push(new int[]{remain_x, 0});
// 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
stack.push(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});
// 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
stack.push(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});
}
return false;
}
public long hash(int[] state) {
return (long) state[0] * 1000001 + state[1];
}
}
cpp 解法, 执行用时: 988 ms, 内存消耗: 305 MB, 提交时间: 2024-01-28 23:27:30
using PII = pair<int, int>;
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
stack<PII> stk;
stk.emplace(0, 0);
auto hash_function = [](const PII& o) {return hash<int>()(o.first) ^ hash<int>()(o.second);};
unordered_set<PII, decltype(hash_function)> seen(0, hash_function);
while (!stk.empty()) {
if (seen.count(stk.top())) {
stk.pop();
continue;
}
seen.emplace(stk.top());
auto [remain_x, remain_y] = stk.top();
stk.pop();
if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
return true;
}
// 把 X 壶灌满。
stk.emplace(x, remain_y);
// 把 Y 壶灌满。
stk.emplace(remain_x, y);
// 把 X 壶倒空。
stk.emplace(0, remain_y);
// 把 Y 壶倒空。
stk.emplace(remain_x, 0);
// 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y));
// 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
stk.emplace(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));
}
return false;
}
// 数学
bool canMeasureWater2(int x, int y, int z) {
if (x + y < z) {
return false;
}
if (x == 0 || y == 0) {
return z == 0 || x + y == z;
}
return z % gcd(x, y) == 0;
}
};
python3 解法, 执行用时: 36 ms, 内存消耗: 14.8 MB, 提交时间: 2022-08-01 11:05:51
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if x + y < z:
return False
if x == 0 or y == 0:
return z == 0 or x + y == z
return z % math.gcd(x, y) == 0
python3 解法, 执行用时: 4556 ms, 内存消耗: 154 MB, 提交时间: 2022-08-01 11:04:36
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
stack = [(0, 0)]
self.seen = set()
while stack:
remain_x, remain_y = stack.pop()
if remain_x == z or remain_y == z or remain_x + remain_y == z:
return True
if (remain_x, remain_y) in self.seen:
continue
self.seen.add((remain_x, remain_y))
# 把 X 壶灌满。
stack.append((x, remain_y))
# 把 Y 壶灌满。
stack.append((remain_x, y))
# 把 X 壶倒空。
stack.append((0, remain_y))
# 把 Y 壶倒空。
stack.append((remain_x, 0))
# 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))
# 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))
return False