LeetCode题解365.water-and-jug-problem

题目地址

https://leetcode.com/problems/water-and-jug-problem/description/

题目描述

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False

思路

这是一道关于数论的题目，确切地说是关于裴蜀定理（英语：Bézout's identity）的题目。

摘自wiki的定义：

对任意两个整数 a、b，设 d是它们的最大公约数。那么关于未知数  x和  y的线性丢番图方程（称为裴蜀等式）：

ax+by=m

有整数解  (x,y) 当且仅当  m是  d的整数倍。裴蜀等式有解时必然有无穷多个解。

因此这道题可以完全转化为裴蜀定理。

关键点解析

• 数论
• 裴蜀定理

代码

/*
 * @lc app=leetcode id=365 lang=javascript
 *
 * [365] Water and Jug Problem
 *
 * https://leetcode.com/problems/water-and-jug-problem/description/
 *
 * algorithms
 * Medium (28.76%)
 * Total Accepted:    27K
 * Total Submissions: 93.7K
 * Testcase Example:  '3\n5\n4'
 *
 * You are given two jugs with capacities x and y litres. There is an infinite
 * amount of water supply available. You need to determine whether it is
 * possible to measure exactly z litres using these two jugs.
 *
 * If z liters of water is measurable, you must have z liters of water
 * contained within one or both buckets by the end.
 *
 * Operations allowed:
 *
 *
 * Fill any of the jugs completely with water.
 * Empty any of the jugs.
 * Pour water from one jug into another till the other jug is completely full
 * or the first jug itself is empty.
 *
 *
 * Example 1: (From the famous "Die Hard" example)
 *
 *
 * Input: x = 3, y = 5, z = 4
 * Output: True
 *
 *
 * Example 2:
 *
 *
 * Input: x = 2, y = 6, z = 5
 * Output: False
 *
 */
/**
 * @param {number} x
 * @param {number} y
 * @param {number} z
 * @return {boolean}
 */
var canMeasureWater = function(x, y, z) {
  if (x + y < z) return false;

  if (z === 0) return true;

  if (x === 0) return y === z;

  if (y === 0) return x === z;

  function GCD(a, b) {
    let min = Math.min(a, b);
    while (min) {
      if (a % min === 0 && b % min === 0) return min;
      min--;
    }
    return 1;
  }

  return z % GCD(x, y) === 0;
};

LeetCode题解11.container-with-most-water

题目地址 https://leetcode.com/problems/container-with-most-water/description/ 题目描述 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). …

LeetCode题解201.bitwise-and-of-numbers-range

题目地址 https://leetcode.com/problems/bitwise-and-of-numbers-range/description/ 题目描述 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbe…

LeetCode题解211.add-and-search-word-data-structure-design

题目地址（211. 添加与搜索单词 - 数据结构设计） https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/description/ 题目描述 设计一个支持以下两种操作的数据结构： void addWord(word) bool search(word) sea…

LeetCode题解121.best-time-to-buy-and-sell-stock

题目地址 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ 题目描述 Say you have an array for which the ith element is the price of a given stock on day i. If you …

LeetCode题解122.best-time-to-buy-and-sell-stock-ii

题目地址 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/ 题目描述 Say you have an array for which the ith element is the price of a given stock on day i. Desi…