GCD

GCD 即求最大公约数的算法，是一种辗转相除法，即用较大的数除以较小的数，再用除数除以余数，直到余数为 0 为止，此时除数就是最大公约数。

例如有两个数 12 和 8，12 ÷ 8 = 1，余数为 4，8 ÷ 4 = 2，余数为 0，所以最大公约数为 4。再复杂一点，有两个数 12 和 18，18 ÷ 12 = 1，余数为 6，12 ÷ 6 = 2，余数为 0，所以最大公约数为 6。有两个数 12 和 32 时，32 ÷ 12 = 2，余数为 8，12 ÷ 8 = 1，余数为 4，8 ÷ 4 = 2，余数为 0，所以最大公约数为 4。我们把它们 a，b 列出来：

a = 32, b = 12 mod: 8
a = 12, b = 8  mod: 4
a = 8,  b = 4  mod: 0

代码

function gcd(a: number, b: number): number {
  if (a < b) {
    [a, b] = [b, a];
  }
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

这里的 [a, b] = [b, a % b] 是一种解构赋值的写法，它的意思是将 [a, b] 解构为 a 和 b，然后将 b 赋值为 a % b，将 a 赋值为 b。拆开来写就是：

a = b;
b = a % b;

可以使用三元运算符和递归来简化代码：

function gcd(a: number, b: number): number {
  return b === 0 ? a : gcd(b, a % b);
}

这里的三元运算符的意思是：如果 b 等于 0，返回 a，否则返回 gcd(b, a % b)。

下面是一个使用 GCD 求 12 和 18 的最小公约数的例子：

let a = 12;
let b = 18;
 
gcd(a, b); // 6

对字符串 ABCABCABC 和 ABCABC，求最大公约数，结果为 ABC：

let a = "ABCABCABC";
let b = "ABCABC";
 
gcd(a, b); // "ABC"

当然还有其它语言的实现，如 C++：

int gcd(int a, int b) {
  if (a < b) {
    swap(a, b);
  }
  while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        a, b = b, a % b
    return a

public int gcd(int a, int b) {
  if (a < b) {
    int temp = a;
    a = b;
    b = temp;
  }
  while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

实例

对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。

给定两个字符串 str1 和 str2 。返回最长字符串 x，要求满足 x 能除尽 str1 且 X 能除尽 str2 。如果不存在，返回空字符串 ""。

示例 1：

输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

示例 2：

输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

示例 3：

输入：str1 = "LEET", str2 = "CODE"
输出：""

题解：

function gcdOfStrings(str1: string, str2: string): string {
    // x 是 str1 和 str2 的公因子，那么 x 也是 str1 + str2 的公因子，且 str1 + str2 === str2 + str1 充要
    // 如果不满足，就返回空字符串
    if (str1 + str2 !== str2 + str1){
        return ''
    }
    function gcd(str1: number,str2:number):number {
        if (str1 < str2){
            [str1,str2]=[str2,str1]
        }
        while (str2!==0){
           [str1,str2] = [str2,str1%str2]
        }
        return str1
    }
    return str1.substring(0, gcd(str1.length, str2.length))
}

这里的主要思路是：如果 str1 和 str2 的最大公约数 x 能够整除 str1 + str2，那么 x 也能整除 str1 和 str2。因为 str1 + str2 = str2 + str1，所以如果 x 能够整除 str1 + str2，那么 x 也能整除 str2 + str1。因此，如果 x 能够整除 str1 + str2，那么 x 也能整除 str1 和 str2。那么如何求出 x 呢？我们可以使用辗转相除法，求出 str1 和 str2 的最大公约数，然后取 str1 和 str2 的最大公约数的子串即可。

call、apply、bind