likes
comments
collection
share

面试算法：数学我的一生之敌📐

作者站长头像
站长
· 阅读数 69

数学问题

小到质数回文数，大到一些都没听过的东西，有很多算法和数学是相关的，常见的比如：

  1. 欧几里得算法（辗转相除法）：求两个数的最大公约数（Greatest Common Divisor，简称 GCD）的算法。它的基本思想是，用较大的数除以较小的数，再用余数去除除数，如此反复，直到余数为 0，则最后的除数就是这两个数的最大公约数。欧几里得算法的时间复杂度为 O(log n)。

  2. 埃拉托斯特尼筛法：求小于等于一个正整数 N 的所有质数的算法。它的基本思想是，从小到大枚举每个数，如果这个数是质数，则将其倍数标记为合数，直到枚举完所有小于等于 N 的数，剩下的未被标记的数就是质数。埃拉托斯特尼筛法的时间复杂度为 O(N log log N)。

  3. 快速幂算法：求一个数的正整数次幂的算法。它的基本思想是，将幂指数表示成二进制形式，然后用乘法和平方操作逐位计算出结果。快速幂算法的时间复杂度为 O(log n)。

  4. 卡特兰数：指满足以下递推关系式的一系列数：C0 = 1，Cn+1 = (4n + 2)/(n + 2) * Cn。卡特兰数可以用来表示很多组合问题，如括号匹配、出栈序列等。计算第 n 个卡特兰数的时间复杂度为 O(n)。

  5. 贝祖定理：也称为贝祖等式，它的表述为：对于任意的正整数 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]

这段代码使用了字符串反转的方法，先将整数转换成字符串，然后将其反转，最后再与原字符串比较，如果相等则说明是回文数，否则不是回文数。

具体来说，这个函数的实现步骤如下：

  1. 将输入的整数转换为字符串，保存在变量 x 中。

  2. 将字符串 x 反转，得到字符串 y。

  3. 比较字符串 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相同。

算法步骤如下：

  1. 如果x是负数，则它不是回文数，直接返回False。

  2. 初始化一个变量rev为0，它将用于存储反转后的整数。

  3. 初始化另一个变量n为x，用于迭代整数x的每个数字。

  4. 在循环中，反转整数n的最低位并将其添加到rev的末尾。

  5. 将n除以10，向下取整，以消除刚刚添加到rev的数字。

  6. 重复步骤4和步骤5，直到n变为0。

  7. 检查反转后的整数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

  进阶： 你可以设计并实现对数时间复杂度的算法来解决此问题吗？

直接求解：

  1. 求出阶乘

  2. 对数字操作，或者转成字符串，求尾随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=(eln⁡x)12=e12⋅ln⁡x\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-1
  • n 是一个整数
  • -104 <= xn <= 104

我们当然可以使用简单的连乘，但是这题既然出来还是medium，肯定就不会让你这么简单。所以这题要用快速幂。

快速幂算法是一种高效计算幂运算的算法。其核心思想是利用指数的二进制表示来加速幂运算的计算过程。

假设我们要计算 x 的 n 次幂，其中 n 的二进制表示为 b0b1b2...bk。我们可以将 x 的 n 次幂表示为：

xn=xb0∗20+b1∗21+b2∗22+...+bk∗2kx^n = x^{b0 * 2^0 + b1 * 2^1 + b2 * 2^2 + ... + bk * 2^k}xn=xb0∗20+b1∗21+b2∗22+...+bk∗2k

根据指数运算的乘法法则，我们可以将上式展开成：

xn=xb0∗20∗xb1∗21∗xb2∗22∗...∗xbk∗2kx^n = x^{b0 * 2^0} * x^{b1 * 2^1} * x^{b2 * 2^2} * ... * x^{bk * 2^k}xn=xb0∗20∗xb1∗21∗xb2∗22∗...∗xbk∗2k

观察上式可以发现，每一项的指数都是 2 的幂次。因此，我们可以使用迭代的方式，每次将指数除以 2，将底数平方，然后判断当前指数是否为奇数，如果是，则将结果乘上当前的底数。

具体的做法如下：

  1. 初始化结果为 1，底数为 x，指数为 n；

  2. 当指数为 0 时，返回结果；

  3. 如果当前指数是奇数，则将结果乘上当前底数；

  4. 将底数平方，将指数除以 2；

  5. 重复步骤 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) 次。

转载自:https://juejin.cn/post/7226361209804931132
评论
请登录