Tong's Blog

Welcome to my Blog

0%

刷题笔记：数模运算

发表于 更新于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

寻找素数

素数：只能被1或其本身整除。

实现一个函数，输入一个整数n，返回[2, n]中的素数个数

暴力解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime(i)) count++;
    }
    return count;
}
//判断整数n是否是素数
bool isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

暴力解法时间复杂度为O(n^2)，不够高效。

改进：

  • i 只需遍历到sqrt(n)；
  • 筛数法，2，3…的所有倍数都不是素数，但存在计算冗余；
  • 内层for循环的j从i的平方开始遍历，不是从2 * i 开始.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int countPrimes(int n) {
    vector<bool> isPrime(n, 1);
    for (int i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j++) {
                isPrime[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

模幂运算

位运算n & (n-1)的妙用

n&(n-1)作用：将n的二进制表示中的最低位为1的改为0

n = 10100(二进制），则(n-1) = 10011 –> n&(n-1) = 10000

  • 判断一个数是否是2的n次幂
    n > 0 && ((n & (n - 1)) == 0 )

    解释((n & (n-1)) == 0)：

    如果A & B == 0，表示A与B的二进制形式没有在同一个位置都为1的时候。

  • 求某一个数的二进制表示中1的个数

    while (n > 0 ) { count ++; n &= (n-1); }

幂运算

整数a，数组b，返回幂运算a ^ b的结果，与1337取模（mod，余数）运算后的结果。

例如输入a = 2, b = [1, 2]，返回2 ^ 12 和1337取模的结果，4096 % 1337 = 85

  • 处理指数数组

    注：b为指数数组，可以采用递归求幂，superPow(a, [1, 2, 5, 6]) ==> superPow(a, [1, 2, 5])

  • 处理模运算

    (a * b) % base = (a % k) * (b % k) % k

    对乘法的结果求模，等价于先对每个因子求模，然后对因子相乘的结果再求模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int base = 1337;
int mypow(int a, int k) {
    int res = 1;
    a %= base;
    //先对a求模，然后每次多对乘法结果res求模
    for (int i = 0; i < k; i++) {
        res *= a;
        res %= base;
    }
    return res;
}

int superPow(int a, vecter<int>& b) {
    if (b.empty()) return 1;
    int last = b.back();
    b.pop_back();
    
    int part1 = mypow(a, last);
    int part2 = mypow(superPow(a, b), 10);
    
    return (part1 * part2) % base;
}

  • 高效求幂

    幂运算的递归关系式：

    a ^ b = a * a ^ (b - 1) , b为奇数

    a ^ b = (a ^ (b / 2)) ^ 2 , b为偶数

    加上对base求模运算：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int base = 1337;

    int mypow(int a, int k) {
        if (k == 0) return 1;
        a %= base;
        if (k % 2 == 1) {
            return (a * mypow(a, k - 1)) % base;
        } else {
            int sub = mypow(a, b / 2);
            return (sub * sub) % base;
        }
    }

连续N个数的和

求 1 2 … n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例：

  • 输入：n = 3 输出：6
  • 输入：n = 9 输出：45

限制：1 <= n <= 1000

解析：

因为不能使用公式直接计算（公式中包含乘除法），所以考虑使用递归进行求解，又不能使用if等判断返回条件，采用A && B 的特性进行判断。

  • 如果A为true，返回B的布尔值（继续往下执行）

  • 如果A为false，直接返回false（相当于短路）

将递归的返回条件取非然后作为 && 的第一个条件，递归主体转换为第二个条件语句。

1
2
3
4
int sumNums(int n) {
    bool b = n && (n += sumNums(n-1));
    return n; 
}

二分搜索剪枝

  1. Koko食香蕉

有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉，Koko要在H小时内吃完，吃香蕉的速度为每小时K根，每小时最多吃一堆香蕉，若吃不下到下一小时再吃，如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。 计算Koko每小时至少吃几根香蕉，才能在H小时内全部吃完？

1
2
3
4
5
输入: piles = [3,6,7,11], H = 8
输出: 4

输入: piles = [30,11,23,4,20], H = 5
输出: 30

解析：求H小时内吃完的最小速率，假设为speed，speed至少为1，最大为max(piles)，一小时最多吃一堆。

暴力解法：从1开始穷举到max(piles)，一旦发现某个值符合，就为最小速度。

改进：可以利用二分搜索剪枝，搜索左侧边界。

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
27
28
int minSpeed(vector<int>& piles, int h) {
    int left = 1, right = getMax(piles) + 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, mid, h)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

bool canFinish(vector<int>& piles, int speed, int h) {
    int time = 0;
    for (int n : piles) {
        time += (n + speed - 1) / speed;
    }
    return time <= h;
}

int getMax(vector<int>& piles) {
    int res = 0;
    for (int n : piles) {
        res = max(res, n);
    }
    return res;
}
  1. 在 D 天内送达包裹的能力

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

货物不可分割且必须按顺序运输

1
2
3
4
5
6
7
8
9
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

解法：本质上和koko食香蕉的问题是一样的，首先确定最小载重cap，最小值为max(weights)和sum(weights)，求最小载重。

暴力法顺序遍历，改进二分搜索左侧边界剪枝。

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
27
28
29
30
31
32
33
34
35
int shipWithinDays(vector<int>& weights, int days) {
	int left = getMax(weights);
    int right = accumulate(weights.begin(), weights.end(), 0) + 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(weights, days, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

bool canFinish(vector<int>& weights, int days, int cap) {
    int i = 0;
    for (int day = 0; day < days; day++) {
        int maxCap = cap;
        while ((maxCap -= weights[i]) >= 0) {
            i++;
            if (i == weights.size()) {
                return true;
            }
        }
    }
    return false;
}

int getMax(vector<int>& weights) {
    int res = 0;
    for (int n : weights) {
        res = max(res, n);
    }
    return res;
}