LeetCode Weekly Contest 152.

问题 1

思路：从 1 到 n 质数和合数分别计数，结果为质数阶乘 * 合数阶乘 % MOD。
复杂度：时间复杂度 O(n^2)，空间复杂度 O(1)。

Python

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        def is_prime(n):
            for i in range(2, n // 2 + 1):
                if n % i == 0:
                    return False

            return True

        p = 0
        c = 1
        mod = 10 ** 9 + 7

        for i in range(2, n+1):
            if is_prime(i):
                p += 1
            else:
                c += 1

        return math.factorial(p) % mod * math.factorial(c) % mod

C++

class Solution {
public:
    bool prime(int n) {
        if (n < 2)
            return false;

        for (int i = 2; i * i <= n; i++)
            if (n % i == 0)
                return false;

        return true;
    }
    int numPrimeArrangements(int n) {
        const int MOD = 1e9 + 7;
        long long res = 1;

        int p = 0;
        int c = 1;

        for (int i = 2; i <= n; i++){
            if (prime(i)) {
                p += 1;
            } else {
                c += 1;
            }
        }

        for (int i = 1; i <= p; i++)
            res = res * i % MOD;

        for (int i = 1; i <= c; i++)
            res = res * i % MOD;

        return res;
    }
};

问题 2

题目链接

解法：计算前缀和，每次去掉一个元素，加入一个元素。
复杂度：时间复杂度 O(n)，空间复杂度 O(1)。

Python

class Solution:
    def dietPlanPerformance(self, A: List[int], k: int,
                            lower: int, upper: int) -> int:
        res = 0
        n = len(A)

        s = sum(A[:k])

        if s > upper:
            res += 1
        elif s < lower:
            res -= 1

        for i in range(n-k):
            s -= A[i]
            s += A[i+k]

            if s > upper:
                res += 1
            elif s < lower:
                res -= 1

        return res

C++

class Solution {
public:
    int dietPlanPerformance(vector<int>& A, int k, int lower, int upper) {
        int res = 0;

        int n = A.size();

        int s = 0;

        for (int i = 0; i < k; ++i){
            s += A[i];
        }

        if (s > upper) {
                res += 1;
        } else if (s < lower) {
                res -= 1;
        }

        for (int i = 0; i < n-k; i++){
            s -= A[i];
            s += A[i+k];

            if (s > upper) {
                res += 1;
            } else if (s < lower) {
                res -= 1;
            }
        }

        return res;
    }
};

问题 3

题目链接

解法：26 个字母出现个数用前缀哈希存储，查询和比较 key 的差异为 O(1)，注意可以 rearrange，所以字母出现次数差异只保留 % 2 的值，最后对字符串奇偶长度做判断。

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

Python

class Solution:
    def canMakePaliQueries(self, s: str,
                           queries: List[List[int]]) -> List[bool]:
        n = len(s)

        f = [[0 for _ in range(n+1)] for _ in range(26)]

        for c in range(26):
            for i in range(n):
                if s[i] == chr(ord('a') + c):
                    f[c][i+1] = f[c][i] + 1
                else:
                    f[c][i+1] = f[c][i]
        res = []

        for q in queries:
            l, r, k = q[0], q[1] + 1, q[2]
            odd = 0

            for c in range(26):
                if (f[c][r] - f[c][l]) % 2 != 0:
                    odd += 1

            res.append(odd <= 2 * k + 1);

        return res

C++

class Solution {
public:
    vector<bool> canMakePaliQueries(string s,
                                    vector<vector<int>>& queries) {
        int n = s.size();
        vector<vector<int>> freq(26, vector<int>(n + 1, 0));

        for (int c = 0; c < 26; c++)
            for (int i = 0; i < n; i++)
                freq[c][i + 1] = freq[c][i] + (s[i] == 'a' + c ? 1 : 0);

        vector<bool> answer;

        for (vector<int> &query : queries) {
            int l = query[0], r = query[1] + 1, k = query[2];

            int odd = 0;

            for (int c = 0; c < 26; c++)
                if ((freq[c][r] - freq[c][l]) % 2 != 0)
                    odd++;

            answer.push_back(odd <= 2 * k + 1);
        }

        return answer;
    }
};

问题 4

题目链接
解法：参考寒神的解答。利用 26 位整数的 bit 存储是否包含某个字母状态(状态压缩)，遍历 puzzles 中的元素，枚举包括第一个字母的所有子 string 组合，然后求和。

复杂度：时间复杂度 O(max(W, P))，空间复杂度 O(W)。

Python

class Solution:
    def findNumOfValidWords(self, words: List[str],
                            puzzles: List[str]) -> List[int]:
        count = collections.Counter()
        for w in words:
            m = 0
            for c in w:
                m |= 1 << (ord(c) - ord('a'))
            count[m] += 1

        res = []

        for p in puzzles:
            bfs = [1 << (ord(p[0]) - ord('a'))]
            for c in set(p[1:]):
                bfs += [m | 1 << (ord(c) - ord('a')) for m in bfs]
            res.append(sum(count[m] for m in bfs))

        return res

C++

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words,
                                    vector<string>& puzzles) {
        unordered_map<int, int> count;

        for (auto& w: words) {
            int mask = 0;
            for (auto& c : w)
                mask |= (1 << (c - 'a'));
            count[mask] ++;
        }

        vector<int> res;

        for (auto& p : puzzles) {
            vector<int> mask_p;
            vector<int> mask_new;

            mask_p.push_back(1 << (p[0] - 'a'));

            for (int i = 1; i < p.size(); i++) {
                mask_new = mask_p;
                for (auto& m : mask_p) {
                    mask_new.push_back(m | (1 << (p[i] - 'a')));
                }
                mask_p = mask_new;
            }

            int cnt = 0;

            for (auto& m : mask_p)
                cnt += count[m];

            res.push_back(cnt);
        }

        return res;
    }
};

LeetCode Weekly Contest 152

问题 1

问题 2

问题 3

问题 4

留言