刷爆leetcode：数学

简介

1 数学(Math)

1.1 基本原理

说白了就是利用已知的数学知识对题目进行分析和解答.
强迫症必须多打两级标题

实战演练

1 素数分解

每一个数都可以分解成素数的乘积，例如 84 = 22 * 31 * 50 * 71 * 110 * 130 * 170 * …

204. 计数质数

leetcode

难度: 中等

数学题，质数？总数？那就用素数筛啦。
一些素数筛的总结
另一些素数筛的总结

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

数学解法

网上找了个似乎最好的素数筛，但是结果也只是80%+
找了题解中比较靠谱的一个，98%+

说实话，没怎么看懂，还是背板吧！

• isPrimeOdd = [1] * (n // 2)
• range(1, int(n**0.5) // 2 + 1)
• isPrimeOdd[i2(i+1):m:2i+1] = [0] * ((m+i)//(2i+1)-i)

class Solution:
    def countPrimes(self, n):
        if n < 3:
            return 0
        else:
            isPrimeOdd = [1] * (n // 2)
            for i in range(1, int(n**0.5) // 2 + 1):
                if isPrimeOdd[i]:
                    isPrimeOdd[i*2*(i+1):m:2*i+1] = [0]*((m+i)//(2*i+1)-i)
            return sum(isPrimeOdd)

另一种使用numpy加速的方法（埃氏筛·优化），注意用np.sum()

import numpy as np
class Solution:
    def countPrimes(self, n):
        if n < 3:
            return 0
        primes = np.ones(n)
        primes[0] = primes[1] = 0
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i::i] = 0
        return int(np.sum(primes))

2 整除

暂无题目。

令 x = 2m0 * 3m1 * 5m2 * 7m3 * 11m4 * …

令 y = 2n0 * 3n1 * 5n2 * 7n3 * 11n4 * …

如果 x 整除 y（y mod x == 0），则对于所有 i，mi <= ni。

3 最大公约数最小公倍数

x 和 y 的最大公约数为：gcd(x,y) = 2min(m0,n0) * 3min(m1,n1) * 5min(m2,n2) * …

x 和 y 的最小公倍数为：lcm(x,y) = 2max(m0,n0) * 3max(m1,n1) * 5max(m2,n2) * …

def gcd(a: int, b:int) -> int:
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

最小公倍数为两数的乘积除以最大公约数。

def lcm(a: int, b:int) -> int:
    return a * b // gcd(a, b)

000. 使用位操作和减法求解最大公约数

难度: xx

对于 a 和 b 的最大公约数 f(a, b)，有：

如果 a 和 b 均为偶数，f(a, b) = 2*f(a/2, b/2);
如果 a 是偶数 b 是奇数，f(a, b) = f(a/2, b);
如果 b 是偶数 a 是奇数，f(a, b) = f(a, b/2);
如果 a 和 b 均为奇数，f(a, b) = f(b, a-b);
乘 2 和除 2 都可以转换为移位操作。

数学解法

public int gcd(int a, int b) {
    if (a < b) &#123;
        return gcd(b, a);
    &#125;
    if (b == 0) &#123;
        return a;
    &#125;
    boolean isAEven = isEven(a), isBEven = isEven(b);
    if (isAEven && isBEven) &#123;
        return 2 * gcd(a >> 1, b >> 1);
    &#125; else if (isAEven && !isBEven) &#123;
        return gcd(a >> 1, b);
    &#125; else if (!isAEven && isBEven) &#123;
        return gcd(a, b >> 1);
    &#125; else &#123;
        return gcd(b, a - b);
    &#125;
&#125;

？？？