数学问题 Math Problems

数学问题是算法中的重要组成部分，涉及数论、概率、几何等多个方面。本指南涵盖常见的数学问题类型及其解决方案。

基础数论 Basic Number Theory

1. 素数 Prime Numbers

def isPrime(n: int) -> bool:
    if n < 2: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def sieveOfEratosthenes(n: int) -> List[int]:
    """返回小于n的所有素数"""
    isPrime = [True] * n
    isPrime[0] = isPrime[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n, i):
                isPrime[j] = False
                
    return [i for i in range(n) if isPrime[i]]

2. 最大公约数与最小公倍数 GCD & LCM

def gcd(a: int, b: int) -> int:
    """欧几里得算法求最大公约数"""
    while b:
        a, b = b, a % b
    return a

def lcm(a: int, b: int) -> int:
    """最小公倍数"""
    return a * b // gcd(a, b)

3. 因数分解 Prime Factorization

def primeFactors(n: int) -> List[int]:
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
    return factors

进制转换 Base Conversion

1. 十进制转其他进制

def decimalToBinary(n: int) -> str:
    return bin(n)[2:]  # 去掉'0b'前缀

def decimalToHex(n: int) -> str:
    return hex(n)[2:]  # 去掉'0x'前缀

2. 其他进制转十进制

def binaryToDecimal(s: str) -> int:
    return int(s, 2)

def hexToDecimal(s: str) -> int:
    return int(s, 16)

3. 任意进制转换

def baseConversion(num: str, fromBase: int, toBase: int) -> str:
    # 先转成十进制
    decimal = int(num, fromBase)
    # 再转成目标进制
    if toBase == 2:
        return bin(decimal)[2:]
    elif toBase == 16:
        return hex(decimal)[2:]
    else:
        return str(decimal)

随机与概率 Random & Probability

1. 蓄水池抽样 Reservoir Sampling

def reservoirSampling(stream: Iterator, k: int) -> List:
    """从流中随机选择k个元素"""
    result = []
    for i, item in enumerate(stream):
        if i < k:
            result.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                result[j] = item
    return result

2. Fisher-Yates 洗牌算法

def shuffle(arr: List) -> None:
    """原地洗牌算法"""
    n = len(arr)
    for i in range(n-1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]

3. 随机数生成器

def rand10UsingRand7():
    """使用rand7()实现rand10()"""
    while True:
        # 生成1-49的随机数
        num = (rand7() - 1) * 7 + rand7()
        if num <= 40:  # 只使用1-40
            return num % 10 + 1

几何问题 Geometry Problems

1. 点和线 Points and Lines

class Point:
    def __init__(self, x: float, y: float):
        self.x = x
        self.y = y

def distance(p1: Point, p2: Point) -> float:
    """计算两点间距离"""
    return ((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2) ** 0.5

def orientation(p1: Point, p2: Point, p3: Point) -> int:
    """判断三点方向"""
    val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y)
    if val == 0: return 0  # 共线
    return 1 if val > 0 else 2  # 顺时针/逆时针

2. 矩形问题 Rectangle Problems

def isRectangleOverlap(rec1: List[int], rec2: List[int]) -> bool:
    """判断两个矩形是否重叠"""
    return not (rec1[2] <= rec2[0] or  # left
               rec1[3] <= rec2[1] or  # bottom
               rec1[0] >= rec2[2] or  # right
               rec1[1] >= rec2[3])    # top

3. 凸包 Convex Hull

def grahamScan(points: List[Point]) -> List[Point]:
    """Graham扫描法求凸包"""
    # 实现略（较复杂）
    pass

经典题目 Classic Problems

1. 快速幂 (50. Pow(x, n))

def myPow(x: float, n: int) -> float:
    if n < 0:
        x = 1/x
        n = -n
    result = 1
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

2. 矩阵快速幂

def matrixPow(matrix: List[List[int]], n: int) -> List[List[int]]:
    """矩阵快速幂"""
    # 实现略
    pass

3. 计算质数个数 (204. Count Primes)

def countPrimes(n: int) -> int:
    if n < 3: return 0
    isPrime = [True] * n
    isPrime[0] = isPrime[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            isPrime[i*i:n:i] = [False] * len(isPrime[i*i:n:i])
            
    return sum(isPrime)

4. 分数到小数 (166. Fraction to Decimal)

def fractionToDecimal(numerator: int, denominator: int) -> str:
    if numerator == 0: return "0"
    
    result = []
    if numerator * denominator < 0:
        result.append("-")
    numerator, denominator = abs(numerator), abs(denominator)
    
    # 整数部分
    result.append(str(numerator // denominator))
    numerator %= denominator
    
    if numerator == 0:
        return "".join(result)
    
    # 小数部分
    result.append(".")
    seen = {}
    while numerator:
        if numerator in seen:
            result.insert(seen[numerator], "(")
            result.append(")")
            break
            
        seen[numerator] = len(result)
        numerator *= 10
        result.append(str(numerator // denominator))
        numerator %= denominator
        
    return "".join(result)

实践建议 Practice Tips

1. 理解基本概念和定理

   • 数论基础
   • 概率统计
   • 几何性质

2. 掌握常用算法

   • 欧几里得算法
   • 素数筛法
   • 快速幂
   • 矩阵运算

3. 注意边界情况

   • 0和负数
   • 溢出处理
   • 精度问题

4. 优化思路

   • 数学公式简化
   • 找规律
   • 合理使用库函数

常见陷阱 Common Pitfalls

1. 整数溢出
2. 浮点数精度
3. 除数为零
4. 负数处理
5. 大数运算

参考资源 References

1. 数论基础
2. 几何算法
3. 概率统计