LeetCode算法学习日记（2020年3月）

2020.3.23

---

题目：求两数的最大公约数
知识点：辗转相除法（欧几里得算法）
代码：

class Solution {
    func getGreatestCommonDivisor(x : Int, y : Int) -> Int{
        var preDivisor = max(x, y)
        var Divisor = min(x, y)
        repeat{
            let Remainder = preDivisor%Divisor
            if Remainder == 0 {
                break
            }
            preDivisor = Divisor
            Divisor = Remainder
        }while true
        return Divisor;
    }
}

算法理解：
假设x > y，则有x = k·y + r（x，y，k，r都为正整数，且r≥0）
当r = 0，y为(x, y)
当r > 0，r = x%y = x - k·y
假设d为(x, y)的公约数，记做 d|x（x能够被d整除）和 d|y（y能够被d整除）
则以上等式可以写成r/d = x/d - k·y/d，而等式的右边一定是正整数，所以r也能被d整除，即记做 d|r
所以x, y, x%y具有相同的公约数集
同理可得x_0 = y, y_0 = x%y, r_0 = x_0 % y_0 = y%(x%y)具有相同的公约数集，并以此类推
当首次出现x_n%y_n = 0时，即为(x, y)的最大公约数

2020.3.24

---

题目：【水壶问题】有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
允许操作：
· 装满任意一个水壶
· 清空任意一个水壶
· 从一个水壶向另外一个水壶倒水，直到装满或者倒空
知识点：裴蜀定理（贝祖定理）
代码：

class Solution {
    func gcd(_ x : Int,_ y : Int) -> Int{
        let preDivisor = max(x, y)
        let Divisor = min(x, y)
        if preDivisor % Divisor == 0 {
            return Divisor
        }else{
            return gcd(x: Divisor, y: preDivisor % Divisor)
        }
    }

    func canMeasureWater(_ x: Int, _ y: Int, _ z: Int) -> Bool {
        if z > x+y{
            return false
        }
        if x==0 || y==0{
            return (z==0) || (x+y==z)
        }
        return z % gcd(x, y) == 0
    }
}

算法理解：
由题可知，在z ≤ x+y，且x, y都不为0的情况下，两个水壶总水量的增加或减少，一定有至少一个壶是满的或是空的，不存在同时有水且都不满的情况。
当有一个水壶不满时，往不满的水壶里加满水，或是将水壶倒空，都是没有意义的，
所以，每次变动的 总水量 一定是 x 和 y 的变化量。
此时题目可以理解为 总水量 经过a次 x升，b次 y升 的变化，能否最终得到 z升？
也就获得了等式：

ax + by = z

而只要满足 z ≤ x+y，且这样的 a, b 存在，那么目标就可以达成。
根据 裴蜀定理(贝祖定理)，ax+by = z 有解的充要条件是：当且仅当 z 是 (x, y) 最大的公约数的倍数。
因此我们只需要找到 (x, y) 的最大公约数并判断 z 是否是它的倍数即可。

打赏