LeetCode-数学专题总结_数据组,每次操作可以使一个元素加1,一个减1

数学

素数

素数分解

每一个数都可以分解成素数的乘积，例如 84 = 2² * 3¹ * 5⁰ * 7¹ * 11⁰ * 13⁰ * 17⁰ * …

整除

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

令 y = 2ⁿ⁰ * 3ⁿ¹ * 5ⁿ² * 7ⁿ³ * 11ⁿ⁴ * …

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

生成素数序列

204. Count Primes (Easy)

埃拉托斯特尼筛法在每次找到一个素数时，将能被素数整除的数排除掉。

class Solution {
   
    public int countPrimes(int n) {
   
        boolean[] notPrimes = new boolean[n + 1];
        int count = 0;
        for (int i = 2; i < n; i++) {
   
            if (notPrimes[i]) {
   
                continue;
            }
            count++;
            for (long j = (long) i * i; j < n; j += i) {
   
                notPrimes[(int) j] = true;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最大公约数

最大公约数最小公倍数

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

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

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

对于 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 都可以转换为移位操作。

int gcd(int a, int b) {
   
    return b == 0 ? a : gcd(b, a % b);
}
1
2
3
4

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

int lcm(int a, int b) {
   
    return a * b / gcd(a, b);
}
1
2
3
4

进制转换

7 进制

504. Base 7 (Easy)

class Solution {
   
    public String convertToBase7(int num) {
   
        if (0 == num) {
   
            return "0";
        }
        boolean negative = num < 0 ? true : false;
        if (negative) {
   
            num = - num;
        }
        StringBuilder result = new StringBuilder();
        int a = 0, b = 0;
        while (num > 0) {
   
            a = num / 7;
            b = num % 7;
            num = a;
            result.append(b);
        }
        String ret = result.reverse().toString();
        return negative == true ? "-" + ret : ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Java 中 static String toString(int num, int radix) 可以将一个整数转换为 radix 进制表示的字符串。

public String convertToBase7(int num) {
   
    return Integer.toString(num, 7);
}
1
2
3
4

16 进制

405. Convert a Number to Hexadecimal (Easy)

Input:
26

Output:
"1a"

Input:
-1

Output:
"ffffffff"
1
2
3
4
5
6
7
8
9
10
11

负数要用它的补码形式。

class Solution {
   
    public String toHex(int num) {
   
        if (0 == num) {
   
            return "0";
        }
        char[] map = {
   '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a'
1
2
3
4
5
6
7
8
9