04.01 枚举算法

204. 计数质数

枚举（超时）

考虑到如果i是x的因数，则$\frac{x}{i}$也必然是x的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在$[2, \sqrt{x}]$上。因此我们在检验x是否为质数时，只需要枚举$[2, \sqrt{x}]$中的所有数即可。

class Solution {
public:
    bool isPrime(int x){
        if(x < 2){
            return false;
        }
        int sqrtx = sqrt(x);
        for(int i = 2; i <= sqrtx; i++){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
    int countPrimes(int n) {
        int res = 0;
        for(int i = 2; i < n; i++){
            if(isPrime(i)){
                res++;
            }
        }
        return res;
    }
};

• 时间复杂度：$O(n \sqrt{n})$
• 空间复杂度：O(1)

埃氏筛

如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数，设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数。

class Solution {
public:
    int countPrimes(int n) {
        // 定义数组
        vector<bool> isPrime(n, true);
        int res = 0;
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                res++;
                if((long long)i * i < n){
                    for(int j = i*i; j < n; j += i){
                    isPrime[j] = false;
                    }
                }
            }
        }
        return res;
    }
};

• 时间复杂度：O(nloglogn)
• 空间复杂度：O(n)

线性筛

使用已知的质数来标记非质数。如果 i 是当前质数 primes[j] 的倍数，则退出内部循环。这个检查用于优化：当 i 已经是 primes[j] 的倍数时，后续的 i * primes[j] 将不会是质数，因为 i 本身已经被标记了。

class Solution {
public:
    int countPrimes(int n) {
        vector<int> primes;  // 用于存储找到的质数
        vector<bool> isPrime(n, true);  // 标记数组，初始时所有数都标记为质数
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                primes.push_back(i);     // 如果i是质数，将其加入质数列表
            }
            // 遍历当前质数列表
            for(int j = 0; j < primes.size() && i * primes[j] < n;j++){
                isPrime[i * primes[j]] = false; // 标记i * primes[j]为非质数
                 // 如果i是当前质数列表中的质数的倍数，退出循环
                 if(i % primes[j] == 0){
                    break;
                 }
            }
        }
        return primes.size();
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

1925. 统计平方和三元组的数目

分析

注意：在计算中，为了防止浮点数造成的误差，并且两个相邻的完全平方正数之间的距离一定大于1，所以我们可以用$\sqrt{a^2 + b^2 + 1}$来代替$\sqrt{a^2 + b^2}$。

class Solution {
public:
    int countTriples(int n) {
        int res = 0;
        for(int a = 1; a <= n; a++){
            for(int b = 1; b <= n; b++){
                int c = (int)sqrt(a*a+b*b+1);
                if(c <= n && a*a + b*b == c*c){
                    res++;
                }
            }
        }
        return res;
    }
};

• 时间复杂度：$O(n^2)$
• 空间复杂度：O(1)

2427. 公因子的数目

枚举到较小值

最大的公因子也只能小于等于a和b中较小的数。

class Solution {
public:
    int commonFactors(int a, int b) {
        int small = min(a, b);
        int res = 0;
        for(int i = 1; i <= small; i++){
            if(a % i == 0 && b % i == 0){
                res++;
            }
        }
        return res;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

枚举到最大公约数

因子一定是成对出现的。

class Solution {
public:
    int commonFactors(int a, int b) {
        int c = gcd(a, b), ans = 0;
        for (int x = 1; x * x <= c; ++x) {
            if (c % x == 0) {
                ++ans;
                if (x * x != c) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

• 时间复杂度：$O(\sqrt{n})$
• 空间复杂度：O(1)

LCR 180. 文件组合

枚举

序列的起点一定小于给定数字编号的$\frac{1}{2}$，枚举每个正整数为起点，判断以它为起点的序列和 sum 是否等于 target 即可。

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        vector<vector<int>> res;
        int sum = 0;
        int limit = (target - 1) / 2;   // (target - 1) / 2 等效于 target / 2 下取整
        for(int i = 1; i <= limit; i++){
            vector<int> cur;
            for(int j = i; ; j++){
                sum += j;
                cur.push_back(j);
                if(sum > target){
                    sum = 0;
                    cur.clear();
                    break;
                }
                else if(sum == target){
                    res.push_back(cur);
                    sum = 0;
                    break;
                }
            }
        }
        return res;
    }
};

• 时间复杂度：$O(target \sqrt{target})$
• 空间复杂度：O(1)，除了答案数组只需要常数的空间存放若干变量。

枚举+数学优化

求根公式：$\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        vector<vector<int>> res;
        int sum = 0;
        int limit = (target - 1) / 2;
        for(int x = 1; x <= limit; x++){
            // 计算delta
            long long delta = 1 - 4 * (x - 1ll*x*x - 2*target);
            // 判断是否有解
            if(delta < 0){
                continue;
            }
            int delta_sqrt = (int)sqrt(delta + 0.5);
            if(1ll * delta_sqrt * delta_sqrt == delta && (delta_sqrt-1) % 2 == 0){
                int y = (-1 + delta_sqrt) / 2;
                // 符合要求
                if(x < y){
                    vector<int> cur;
                    for(int i = x; i <= y; i++){
                        cur.push_back(i);
                    }
                    res.push_back(cur);
                }
            }
        }
        return res;
    }
};

• 时间复杂度：O(target)
• 空间复杂度：O(1)

2249. 统计圆内格点数目

分析

根据半径和坐标的范围确定枚举的范围。

class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        int res = 0;
        for(int i = 0; i <= 200; i++){
            for(int j = 0; j <= 200; j++){
                for(auto& circle : circles){
                    int x = circle[0];
                    int y = circle[1];
                    int r = circle[2];
                    if((i-x)*(i-x) + (j-y)*(j-y) <= r*r){
                        res++;
                        break;
                    }
                }
            }
        }
        return res;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

总结

枚举算法是一种基础而直接的解题方法，适用于解答各种组合问题、计数问题、搜索问题等。它的核心思想是列举所有可能的情况，逐一进行验证，找到符合条件的解。确定需要解决的问题，并明确需要枚举的目标是什么。例如，枚举可能的数值、组合、子集等。确定需要枚举的范围，包括起始值和终止值。确定这个范围有助于限定算法的搜索空间。通过循环或递归的方式，遍历所有可能的选项或组合。例如，通过循环遍历所有整数或所有可能的子集。通过循环或递归的方式，遍历所有可能的选项或组合。例如，通过循环遍历所有整数或所有可能的子集。