leetcode::the_number_of_good_subsets::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static int	numberOfGoodSubsets (vector< int > &nums)

静态 Private 属性
static constexpr int	mask_max = 1 << primes.size()
static constexpr int	mod = 1000000007
static constexpr int	num_max = 30
static constexpr array< int, 10 >	primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

详细描述

在文件 leetcode.h 第 1321 行定义.

成员函数说明

numberOfGoodSubsets()

int leetcode::the_number_of_good_subsets::Solution::numberOfGoodSubsets ( vector< int > &  nums )

static

在文件 leetcode.cpp 第 3391 行定义.

                                                           {
            vector<int> freq(num_max + 1);
            for(const int num: nums) {
                freq[num]++;
            }
 
            vector<int> f(mask_max);
            f[0] = 1;
            for(int i = 0; i < freq[1]; ++i) {
                f[0] = f[0] * 2 % mod;
            }
 
            for(int i = 2; i <= num_max; ++i) {
                if(freq[i] == 0) {
                    continue;
                }
 
                // 检查 i 的每个质因数是否均不超过 1 个
                int subset  = 0;
                const int x = i;
                bool check  = true;
                for(int j = 0; j < primes.size(); j++) {
                    const int prime = primes[j];
                    if(x % (prime * prime) == 0) {
                        check = false;
                        break;
                    }
                    if(x % prime == 0) {
                        subset |= 1 << j;
                    }
                }
                if(!check) {
                    continue;
                }
 
                // 动态规划
                for(int mask = mask_max - 1; mask > 0; mask--) {
                    if((mask & subset) == subset) {
                        f[mask] = (f[mask] + static_cast<long long>(f[mask ^ subset]) * freq[i]) % mod;
                    }
                }
            }
            int ans = 0;
            for(int mask = 1; mask < mask_max; mask++) {
                ans = (ans + f[mask]) % mod;
            }
            return ans;
        }

引用了 mask_max, mod, num_max , 以及 primes.

被这些函数引用 leetcode::the_number_of_good_subsets::TEST().

类成员变量说明

mask_max

constexpr int leetcode::the_number_of_good_subsets::Solution::mask_max = 1 << primes.size()

staticconstexprprivate

在文件 leetcode.h 第 1326 行定义.

被这些函数引用 numberOfGoodSubsets().

mod

constexpr int leetcode::the_number_of_good_subsets::Solution::mod = 1000000007

staticconstexprprivate

在文件 leetcode.h 第 1325 行定义.

被这些函数引用 numberOfGoodSubsets().

num_max

constexpr int leetcode::the_number_of_good_subsets::Solution::num_max = 30

staticconstexprprivate

在文件 leetcode.h 第 1324 行定义.

被这些函数引用 numberOfGoodSubsets().

primes

constexpr array<int, 10> leetcode::the_number_of_good_subsets::Solution::primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

staticconstexprprivate

在文件 leetcode.h 第 1323 行定义.

被这些函数引用 numberOfGoodSubsets().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp