365.水壶问题

链接：365.水壶问题
难度：Medium
标签：深度优先搜索、广度优先搜索、数学
简介：有两个容量分别为 x 升 和 y 升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z 升 的水？。

题解 1 - rust

• 编辑时间：2024-01-28
• 执行用时：441ms
• 内存消耗：21.37MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn can_measure_water(jug1_capacity: i32, jug2_capacity: i32, target_capacity: i32) -> bool {
        use std::cmp::min;
        use std::collections::{HashMap, VecDeque};
        let mut used: HashMap<i32, HashMap<i32, bool>> = Default::default();
        let mut q: VecDeque<(i32, i32)> = Default::default();
        q.push_back((0, 0));
        used.entry(0).or_default().entry(0).or_insert(true);
        while let Some((jug1, jug2)) = q.pop_front() {
            if jug1 == target_capacity || jug2 == target_capacity || jug1 + jug2 == target_capacity
            {
                return true;
            }
            let next = [
                [jug1_capacity, jug2],
                [0, jug2],
                [
                    min(jug1_capacity, jug1 + jug2),
                    jug2 - (min(jug1_capacity, jug1 + jug2) - jug1),
                ],
                [jug1, jug2_capacity],
                [jug1, 0],
                [
                    jug1 - (min(jug2_capacity, jug1 + jug2) - jug2),
                    min(jug2_capacity, jug1 + jug2),
                ],
            ];
            for [jug1, jug2] in next {
                let item = used.entry(jug1).or_default().entry(jug2).or_default();
                if !*item {
                    q.push_back((jug1, jug2));
                    *item = true;
                }
            }
        }
        false
    }
}

题解 2 - typescript

• 编辑时间：2021-07-21
• 执行用时：2516ms
• 内存消耗：81.7MB
• 编程语言：typescript
• 解法介绍：广度优先，遍历所有可能。

function canMeasureWater(
  jug1Capacity: number,
  jug2Capacity: number,
  targetCapacity: number
): boolean {
  type State = [number, number];
  const format = (x: number, y: number) => `${x}::${y}`;
  const set = new Set<string>([format(0, 0)]);
  const queue: State[] = [[0, 0]];
  return find();
  function find(): boolean {
    while (queue.length !== 0) {
      const cur = queue.shift()!;
      const next = findNext(cur);
      if (next.some(([x, y]) => x + y === targetCapacity)) return true;
      next.forEach(v => {
        const str = format(...v);
        if (!set.has(str)) {
          set.add(str);
          queue.push(v);
        }
      });
    }
    return false;
  }
  function findNext([x, y]: State): State[] {
    return [
      [0, y],
      [x, 0],
      [jug1Capacity, y],
      [x, jug2Capacity],
      [Math.max(x - (jug2Capacity - y), 0), Math.min(y + x, jug2Capacity)],
      [Math.min(x + y, jug1Capacity), Math.max(y - (jug1Capacity - x), 0)],
    ];
  }
}

题解 3 - python

• 编辑时间：2024-01-28
• 执行用时：2181ms
• 内存消耗：67.66MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
        used = defaultdict(defaultdict)
        q = deque()
        q.append((0, 0))
        used[0][0] = True
        while q:
            jug1, jug2 = q.popleft()
            if jug1 == targetCapacity or jug2 == targetCapacity or jug1 + jug2 == targetCapacity:
                return True
            arr =[
                [jug1Capacity, jug2],
                [0, jug2],
                [min(jug1Capacity, jug1 + jug2), jug2 - (min(jug1Capacity, jug1 + jug2) - jug1)],
                [jug1, jug2Capacity],
                [jug1, 0],
                [jug1 - (min(jug2Capacity, jug1 + jug2) - jug2), min(jug2Capacity, jug1 + jug2)]
            ]
            for jug1, jug2 in arr:
                if jug2 not in used[jug1]:
                    q.append((jug1, jug2))
                    used[jug1][jug2] = True
        return False