引言
对于 LeetCode 上数量不少的数学题，我们尽量将其按照类型划分讲解。然而很多数学题的解法并不通用，我们也很难在几道题里把所有的套路讲清楚，因此我们只选择了几道经典或是典型的题目，供大家参考。
公倍数与公因数
利用辗转相除法，我们可以很方便地求得两个数的最大公因数 (GCD)；将两个数相乘再除以最大公因数即可得到最小公倍数 (LCM)。进一步地，我们也可以通过扩展欧几里得算法，在求得 a 和 b 最大公因数的同时，也得到它们的系数 x 和 y，从而使 ax + by = gcd(a, b)：
1 | def gcd_extended(a, b): |
质数
质数又称素数，指的是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。值得注意的是，每一个数都可以分解成质数的乘积。
204. Count Primes
埃拉托斯特尼筛法 (Sieve of Eratosthenes) 是非常常用的，判断一个整数是否是质数的方法。并且它可以在判断一个整数 n 时，同时判断所有小于 n 的整数，因此非常适合这道题。
数字处理
504. Base 7
进制转换类型的题，通常是利用除法和取模 (Mod) 来进行计算，同时也要注意一些细节，如负数和零。如果输出是数字类型而非字符串，则也需要考虑是否会超出整数上下界。
172. Factorial Trailing Zeroes
明显的，质因子 2 的数量远多于质因子 5 的数量，因此我们可以只统计阶乘结果里有多少个质因子 5。
415. Add Strings
因为相加运算是从后往前进行的，所以可以先翻转字符串，再逐位计算。这种类型的题考察的是细节，如进位、位数差等等。
326. Power of Three
有两种方法：一种是利用对数，设 log(3, n) = m，如果 n 是 3 的整数次方，那么 m 一定是整数。另一种方法是，因为在 int 范围内 3 的最大次方是 3^19 = 1162261467，如果 n 是 3 的整数次方，那么 1162261467 除以 n 的余数一定是零；反之亦然。
50. Pow(x, n)
利用递归，我们可以较为轻松地解决本题。注意边界条件的处理。
随机与取样
384. Shuffle an Array
我们采用经典的洗牌算法 (Fisher-Yates)，原理是通过随机交换位置来实现随机打乱，有正向和反向两种写法，且实现非常方便。
528. Random Pick with Weight
我们可以先使用 accumulate 求前缀和（即到每个位置为止所有数字的和），这个结果对于正整数数组是单调递增的。每当需要采样时，我们可以先随机产生一个数字，然后使用二分法查找其在前缀和中的位置，以模拟加权采样的过程。这里的二分法可以用 bisect_left 实现。
382. Linked List Random Node
不同于数组，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采样：遍历一次链表，在遍历到第 m 个节点时，有 1/m 的概率选择这个节点覆盖掉之前的节点选择。
练习
168. Excel Sheet Column Title
7 进制转换的变种题，需要注意的一点是从 1 开始而不是 0。
67. Add Binary
字符串加法的变种题。
238. Product of Array Except Self
你可以不使用除法做这道题吗？我们很早之前讲过的 135. Candy 或许能给你一些思路。
462. Minimum Moves to Equal Array Elements II
这道题是笔者最喜欢的 LeetCode 题目之一，需要先推理出怎么样移动是最优的，再考虑如何进行移动。你或许需要一些前些章节讲过的算法。
169. Majority Element
如果想不出简单的解决方法，搜索一下 Boyer-Moore Majority Vote 算法吧。
470. Implement Rand10() Using Rand7()
如何用一个随机数生成器生成另一个随机数生成器？你可能需要利用原来的生成器多次。
202. Happy Number
你可以简单的用一个 while 循环解决这道题，但是有没有更好的解决办法？如果我们把每个数字想象成一个节点，是否可以转化为环路检测？