面试算法：数学我的一生之敌📐
数学问题
小到质数回文数，大到一些都没听过的东西，有很多算法和数学是相关的，常见的比如：
-
欧几里得算法（辗转相除法）：求两个数的最大公约数（Greatest Common Divisor，简称 GCD）的算法。它的基本思想是，用较大的数除以较小的数，再用余数去除除数，如此反复，直到余数为 0，则最后的除数就是这两个数的最大公约数。欧几里得算法的时间复杂度为 O(log n)。
-
埃拉托斯特尼筛法：求小于等于一个正整数 N 的所有质数的算法。它的基本思想是，从小到大枚举每个数，如果这个数是质数，则将其倍数标记为合数，直到枚举完所有小于等于 N 的数，剩下的未被标记的数就是质数。埃拉托斯特尼筛法的时间复杂度为 O(N log log N)。
-
快速幂算法：求一个数的正整数次幂的算法。它的基本思想是，将幂指数表示成二进制形式，然后用乘法和平方操作逐位计算出结果。快速幂算法的时间复杂度为 O(log n)。
-
卡特兰数：指满足以下递推关系式的一系列数：C0 = 1，Cn+1 = (4n + 2)/(n + 2) * Cn。卡特兰数可以用来表示很多组合问题，如括号匹配、出栈序列等。计算第 n 个卡特兰数的时间复杂度为 O(n)。
-
贝祖定理：也称为贝祖等式，它的表述为：对于任意的正整数 a、b 和它们的最大公约数 d，关于未知数 x 和 y 的线性不定方程 ax + by = d 有整数解当且仅当 d 是 a 和 b 的最大公约数的倍数。
本文是面试经典 150 题中汇总的 面试常见的数学问题。
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入： x = 121
输出： true
示例 2：
输入： x = -121
输出： false
解释： 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入： x = 10
输出： false
解释： 从右向左读, 为 01 。因此它不是一个回文数。
提示：
-231 <= x <= 231 - 1
进阶： 你能不将整数转为字符串来解决这个问题吗？
class Solution:
def isPalindrome(self, x: int) -> bool:
x = str(x)
return x == x[::-1]
这段代码使用了字符串反转的方法，先将整数转换成字符串，然后将其反转，最后再与原字符串比较，如果相等则说明是回文数，否则不是回文数。
具体来说，这个函数的实现步骤如下：
-
将输入的整数转换为字符串，保存在变量 x 中。
-
将字符串 x 反转，得到字符串 y。
-
比较字符串 x 和字符串 y，如果相等则说明是回文数，返回 True，否则不是回文数，返回 False。
这个算法的时间复杂度为 O(n)，其中 n 是整数 x 的位数，因为要对整数进行字符串转换和字符串反转，需要遍历整个字符串一次。空间复杂度也为 O(n)，因为要保存一个字符串 y。
进阶解法： 不使用字符串
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
rev,n = 0,x
while n:
rev = rev*10 + n%10
n //= 10
return x == rev
这是另一种解决回文数问题的方法，其思想是将给定的整数x反转，然后检查反转后的整数是否与原始整数x相同。
算法步骤如下：
-
如果x是负数，则它不是回文数，直接返回False。
-
初始化一个变量rev为0，它将用于存储反转后的整数。
-
初始化另一个变量n为x，用于迭代整数x的每个数字。
-
在循环中，反转整数n的最低位并将其添加到rev的末尾。
-
将n除以10，向下取整，以消除刚刚添加到rev的数字。
-
重复步骤4和步骤5，直到n变为0。
-
检查反转后的整数rev是否与原始整数x相同。如果相同，则x是回文数，返回True；否则返回False。
这种方法的时间复杂度为O(log n)，其中n是给定整数x的位数。
66. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入： digits = [1,2,3]
输出： [1,2,4]
解释： 输入数组表示数字 123。
示例 2：
输入： digits = [4,3,2,1]
输出： [4,3,2,2]
解释： 输入数组表示数字 4321。
示例 3：
输入： digits = [0]
输出： [1]
代码实现如下：
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
digits = digits[::-1]
flag = False
for i in range(len(digits)):
digits[i] += 1
if digits[i] < 10:
flag = False
break
else:
digits[i] = 0
flag = True
if flag:
digits.append(1)
return digits[::-1]
首先将整数列表反转。
然后，遍历整数列表中的每一位，并将其加1。
如果加1后的值小于10，则退出循环；否则将该位的值设为0，并继续遍历下一位。
如果遍历完整个列表后最高位的值仍然是0，则需要在列表的末尾添加一个值为1的元素，表示进位。
最后，将整数列表再次反转，并返回该列表。
该算法的时间复杂度是O(n)，其中n是整数列表的长度，因为需要遍历整个列表。该算法的空间复杂度是O(1)，因为只需要常数级别的额外空间来存储一些变量。
172. 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入： n = 3
输出： 0
解释： 3! = 6 ，不含尾随 0
示例 2：
输入： n = 5
输出： 1
解释： 5! = 120 ，有一个尾随 0
示例 3：
输入： n = 0
输出： 0
提示：
0 <= n <= 104
进阶： 你可以设计并实现对数时间复杂度的算法来解决此问题吗？
直接求解：
-
求出阶乘
-
对数字操作，或者转成字符串，求尾随0 的个数。
但是计算阶乘可能溢出。
换个思路：
-
乘之前找到谁能得到尾随0 --> 找到10的倍数
- 2*5 = 10 --> 10的倍数
- 4*5 = 20 --> 10的倍数
-
找到10的倍数 --> 找到 5 的倍数 --> 看5的倍数能转化出几个5
- 因为2的倍数肯定比5多，所以能找到2的倍数一定能找到与之对应的5的倍数
- 25 ---> 5*5 这样能拆出两个5！
class Solution:
def trailingZeroes(self, n: int) -> int:
count = 0
for i in range(1,n+1):
while i %5 == 0:
count += 1
i //= 5
return count
末尾的零来自于因子 2 和因子 5 相乘得到的结果，因为每个偶数都包含因子 2，而每个因子 5 都会与因子 2 相乘得到一个末尾的零。
具体的做法是，遍历 1 到 n 的所有整数，每个数都除以所有的因子 5，并计算除以因子 5 的次数，即为末尾的零的个数。因为 5 的倍数有一个因子 5，25 的倍数有两个因子 5，125 的倍数有三个因子 5，以此类推，因此需要用循环逐次除以 5 的幂次，直到商为 0。
这个算法的时间复杂度为 O(log n)，因为每次都将 n 除以 5，直到商为 0，总共最多需要除以 log5(n)log_5(n)log5(n) 次。
69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意： 不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
解法：
x=x12=(elnx)12=e12⋅lnx\sqrt x = x^{\frac 1 2} = (e^{\ln x})^{\frac 1 2} = e^{\frac 1 2 · \ln x}x=x21=(elnx)21=e21⋅lnx
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
ans = int(math.exp(0.5 * math.log(x)))
return ans + 1 if (ans + 1) ** 2 <= x else ans
因为浮点数计算精度的问题，在计算结果之后，我们还需要判断该结果的平方是否等于 x。如果不等于 x，说明结果的整数部分是 x 的下取整，而如果平方大于 x，则说明结果的整数部分是 x 的上取整。
50. Pow(x, n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入： x = 2.00000, n = 10
输出： 1024.00000
示例 2：
输入： x = 2.00000, n = -2
输出： 0.25000
解释： 2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1n是一个整数-104 <= xn <= 104
我们当然可以使用简单的连乘，但是这题既然出来还是medium，肯定就不会让你这么简单。所以这题要用快速幂。
快速幂算法是一种高效计算幂运算的算法。其核心思想是利用指数的二进制表示来加速幂运算的计算过程。
假设我们要计算 x 的 n 次幂，其中 n 的二进制表示为 b0b1b2...bk。我们可以将 x 的 n 次幂表示为：
根据指数运算的乘法法则，我们可以将上式展开成：
观察上式可以发现，每一项的指数都是 2 的幂次。因此，我们可以使用迭代的方式，每次将指数除以 2，将底数平方，然后判断当前指数是否为奇数，如果是，则将结果乘上当前的底数。
具体的做法如下：
-
初始化结果为 1，底数为 x，指数为 n；
-
当指数为 0 时，返回结果；
-
如果当前指数是奇数，则将结果乘上当前底数；
-
将底数平方，将指数除以 2；
-
重复步骤 2 到步骤 4。
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1.0
if n < 0:
x = 1 / x
n = -n
res = 1.0
while n > 0:
if n & 1 == 1:
res *= x
x *= x
n //= 2
return res
这个算法的时间复杂度为 O(log n)，因为每次循环将指数除以 2，总共最多需要循环log2(n)log_2(n)log2(n) 次。