数学问题 Math Problems
数学问题 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
-
理解基本概念和定理
- 数论基础
- 概率统计
- 几何性质
-
掌握常用算法
- 欧几里得算法
- 素数筛法
- 快速幂
- 矩阵运算
-
注意边界情况
- 0和负数
- 溢出处理
- 精度问题
-
优化思路
- 数学公式简化
- 找规律
- 合理使用库函数
常见陷阱 Common Pitfalls
- 整数溢出
- 浮点数精度
- 除数为零
- 负数处理
- 大数运算