LeetCode 数学问题详解：概念、技巧与实战应用

VocabVictor2024-09-022024-09-04

引言

数学问题是 LeetCode 中一个重要的问题类型,涉及到各种数学概念和技巧。这类问题不仅考察我们的数学基础,还要求我们能够将数学知识灵活运用到编程中。本文将深入探讨 LeetCode 中常见的数学问题类型、解题技巧以及实战应用。

1. 基础数学概念

在开始之前,我们先回顾一些基础的数学概念:

质数(素数)
最大公约数(GCD)和最小公倍数(LCM)
阶乘
排列组合
等差数列和等比数列
斐波那契数列
欧拉函数
模运算

2. 常见数学问题类型及解题技巧

2.1 质数问题

埃拉托斯特尼筛法(Sieve of Eratosthenes)

用于高效地找出一定范围内的所有质数。

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    return [i for i in range(n+1) if primes[i]]

2.2 最大公约数(GCD)

欧几里得算法(辗转相除法)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

2.3 组合数学

杨辉三角

def generate_pascal_triangle(n):
    triangle = [[1]]
    for _ in range(n-1):
        prev_row = triangle[-1]
        new_row = [1]
        for i in range(len(prev_row)-1):
            new_row.append(prev_row[i] + prev_row[i+1])
        new_row.append(1)
        triangle.append(new_row)
    return triangle

2.4 数论

快速幂算法

def pow_mod(base, exponent, mod):
    result = 1
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % mod
        exponent >>= 1
        base = (base * base) % mod
    return result

3. LeetCode 实战应用

3.1 LeetCode 204. Count Primes

计算小于非负整数 n 的质数的数量。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        
        primes = [True] * n
        primes[0] = primes[1] = False
        
        for i in range(2, int(n**0.5) + 1):
            if primes[i]:
                for j in range(i*i, n, i):
                    primes[j] = False
        
        return sum(primes)

3.2 LeetCode 69. Sqrt(x)

实现 int sqrt(int x) 函数。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        left, right = 2, x // 2
        
        while left <= right:
            mid = left + (right - left) // 2
            squared = mid * mid
            
            if squared == x:
                return mid
            elif squared < x:
                left = mid + 1
            else:
                right = mid - 1
        
        return right

3.3 LeetCode 50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        
        result = 1
        current_product = x
        
        while n > 0:
            if n % 2 == 1:
                result *= current_product
            current_product *= current_product
            n //= 2
        
        return result

3.4 LeetCode 279. Perfect Squares

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] + [float('inf')] * n
        
        for i in range(1, n+1):
            for j in range(1, int(i**0.5) + 1):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        return dp[n]

4. 高级数学技巧

4.1 中国剩余定理 (Chinese Remainder Theorem)

用于求解一元线性同余方程组。

def chinese_remainder_theorem(nums, remainders):
    total = 0
    product = reduce(lambda a, b: a*b, nums)
    for num, remainder in zip(nums, remainders):
        p = product // num
        total += remainder * mod_inverse(p, num) * p
    return total % product

def mod_inverse(a, m):
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        else:
            gcd, x, y = extended_gcd(b % a, a)
            return gcd, y - (b // a) * x, x
    
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise Exception('模逆不存在')
    else:
        return x % m

4.2 FFT (快速傅里叶变换)

用于大数乘法等问题。

import cmath

def fft(a):
    n = len(a)
    if n <= 1:
        return a
    omega = cmath.exp(2j * cmath.pi / n)
    a0 = fft(a[0::2])
    a1 = fft(a[1::2])
    return [a0[k] + omega**k * a1[k] for k in range(n//2)] + \
           [a0[k] - omega**k * a1[k] for k in range(n//2)]

def ifft(a):
    n = len(a)
    a = fft([x.conjugate() for x in a])
    return [x.conjugate() / n for x in a]

def multiply(a, b):
    n = 1
    while n < len(a) + len(b):
        n <<= 1
    a.extend([0] * (n - len(a)))
    b.extend([0] * (n - len(b)))
    fa = fft(a)
    fb = fft(b)
    fc = [fa[i] * fb[i] for i in range(n)]
    c = [round(x.real) for x in ifft(fc)]
    while c[-1] == 0:
        c.pop()
    return c