LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• Sieve of Eratosthenes（埃拉托斯色尼筛法）

先假设所有数为质数，之后标记不为质数的数

2 => 4、6、8、... 不为质数
3 => 6、9、12、... 不为质数
4 已标记不为质数
5 => 10、15、20、... 不为质数
6 已标记不为质数
7 => 14、21、28、... 不为质数
8 已标记不为质数
9 已标记不为质数
10 已标记不为质数
11 => 22、33、44、... 不为质数
12 已标记不为质数
13 => 26、39、42、... 不为质数
14 已标记不为质数
15 已标记不为质数
16 已标记不为质数
17 => 34、51、68、... 不为质数
18 已标记不为质数
19 => 38、57、78不为质数
20 已标记不为质数
... 

• 解法如下

class Solution {
 public:
  int countPrimes(int n) {
    if (n <= 2) {
      return 0;
    }
    vector<bool> dp(n, true);
    int cnt = 0;
    for (int i = 2; i < n; ++i) {
      if (dp[i]) {
        ++cnt;
        for (int j = i + i; j < n; j += i) {  // 后续为该质数倍数的数均不为质数
          dp[j] = false;
        }
      }
    }
    return cnt;
  }
};

• 实际上只要遍历到不超过 sqrt(n) 即可，时间复杂度 O(n loglog n)

class Solution {
 public:
  int countPrimes(int n) {
    if (n <= 2) return 0;
    vector<bool> dp(n, true);
    dp[0] = false;
    dp[1] = false;
    for (int i = 2; i < sqrt(n); ++i) {
      if (dp[i]) {
        for (int j = i + i; j < n; j += i) {
          dp[j] = false;
        }
      }
    }
    return count(begin(dp), end(dp), true);
  }
};

• Euler’s sieve （欧拉筛、线性筛）可以避免普通筛中重复筛选的过程，每个数只标记一次，时间复杂度 O(n)

标记当前数与所有已记录质数的乘积
若当前数能被相乘的质数整除时，标记该乘积后结束当前数的标记
这样，所有的数都只被标记一次

2 => 2 * 2 => 2 整除 2，结束
3 => 3 * 2、3 * 3 => 3 整除 3，结束
4 => 4 * 2 => 2 整除 4，结束
5 => 5 * 2、5 * 3、5 * 5 => 5 整除 5，结束
6 => 6 * 2 => 2 整除 6，结束
7 => 7 * 2、7 * 3、7 * 5、7 * 7 => 7 整除 7，结束
8 => 6 * 2 => 2 整除 8，结束
9 => 9 * 2、9 * 3 => 3 整除 9，结束
10 => 10 * 2 => 2 整除 10，结束
11 => * 2、3、5、7、11（如果设置了上限是 100，121 超出了上限，就没必要标记）
12 => * 2
13 => * 2、3、5、7、11、13
14 => * 2
15 => * 2、3
16 => * 2
17 => * 2、3、5、7、11、13、17
18 => * 2
19 => * 2、3、5、7、11、13、17、19
20 => * 2
... 

• 解法如下

class Solution {
 public:
  int countPrimes(int n) {
    if (n <= 2) {
      return 0;
    }
    vector<bool> dp(n, true);
    vector<int> primes;
    for (int i = 2; i < n; ++i) {
      if (dp[i]) {
        primes.emplace_back(i);
      }
      for (int j = 0; j < size(primes) && i * primes[j] < n; ++j) {
        dp[i * primes[j]] = false;
        if (i % primes[j] == 0) {
          break;
        }
      }
    }
    return size(primes);
  }
};