Weekly Contest 152

5173. 质数排列

请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。

让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。

示例 1：

输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。

示例 2：

输入：n = 100
输出：682289015

提示：

• 1 <= n <= 100

思路：

首先分析题意，得到中心思想：

数列包含从1到n的所有元素，其中质数的索引也应该是质数，那么非质数的索引也应该是非质数。

以[1,2,5,4,3]为例，其中2、5、3对应的索引为2、3、5，可以观察到，数字和索引的内容相同，只是位置不同，于是可以想到全排列的解法。

res = num_prime! * num_nonprime!

其中，$num_prime$是数组中质数的个数，$num_nonprime$是数组中非质数的个数。唯一需要注意的问题就是溢出问题了。

代码：

class Solution{
public:
    int mod = 1000000007;
    long long f(int n)
    {
        long long res = 1;
        for (int i = 1; i <= n; i++)
            res = res * i % mod;
        return res;
    }
    int numPrimeArrangements(int n) {
        vector<int> prime{
            2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
        };

        int prime_num = upper_bound(prime.begin(), prime.end(), n) - prime.begin();
        int non_prime_num = n - prime_num;
        return static_cast<int>(f(prime_num) * f(non_prime_num) % mod);
    }
};

5174. 健身计划评估

你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。

他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。

计划的统计周期通常是 k 天，你需要计算他在每一段连续的 k 天内消耗的总卡路里 T：

• 如果 T < lower，那么这份计划相对糟糕，并失去 1 分；
• 如果 T > upper，那么这份计划相对优秀，并获得 1 分；
• 否则，这份计划普普通通，分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。

注意：总分可能是负数。

示例 1：

输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
输出：0
解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.

示例 2：

输入：calories = [3,2], k = 2, lower = 0, upper = 1
输出：1
解释：calories[0] + calories[1] > upper, 总分 = 1.

示例 3：

输入：calories = [6,5,0,0], k = 2, lower = 1, upper = 5
输出：0
解释：calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 总分 = 0.

提示：

• 1 <= k <= calories.length <= 10^5
• 0 <= calories[i] <= 20000
• 0 <= lower <= upper

思路：

分析题意，k天一次结算，然后用这k天之间消耗的卡路里和upper和lower比较，得到结果。

注意k天之间是重叠的。因此解题方法是设置一个长度为k的滑动窗口，每次计算这个窗口中所有元素的和，大于upper就加一分，小于lower就减一分。计算窗口中元素和的时候可以暴力解答也可以使用积分，这里我直接暴力做了（懒）。

代码：

class Solution {
public:
    int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
        int res = 0;
        for (auto it = calories.begin(); it + k <= calories.end(); it++)
        {
            if (accumulate(it, it + k, 0) > upper)
                res++;
            else if (accumulate(it, it + k, 0) < lower)
                res--;
        }
        return res;
    }
};

5175. 构建回文串检测

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

提示：

• 1 <= s.length, queries.length <= 10^5
• 0 <= queries[i][0] <= queries[i][1] < s.length
• 0 <= queries[i][2] <= s.length
• s 中只有小写英文字母

思路：

我一开始忽略了题目中的一句话

我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母

如果没有重新排列这个条件的话，直接从子串的两头对比就可以完成判断。

但要求重新排列的话，就丢失了子串中每个字符的位置关系，所以需要对子串中的所有字符出现的次数进行统计，然后进行判断。

那么，怎么重排并且判断呢？

最直接的思路是，尽量把子串中相同的字符放在满足回文的位置，然后对剩下不满足回文的字符进行替换。

举个例子，对于”aabcdef”：

1. 其中a出现了两次，其余五个字母都出现了奇数次。要对其进行最少次数的替换使其满足回文串，则可以先把两个”a”放在回文串对应的位置，此时子串为”aabcdef”，重排列之后的子串”a * a”
2. 对剩下的五个字符进行替换，则只需要替换其中的两个，使得这两个字符包含于剩下三个字符中，替换d->b，e->c，此时子串为”aabcbcf”，重排列之后的子串”a * a”
3. 把相同的字符再次放在对应的位置，多出来的一个字符可以放在中心的位置。此时子串为”aabcbcf”，重排列之后的子串”abcfbca”
4. 此时替换次数为2

可以看出，最少的替换次数为子串中出现次数为奇数的字符数的一半。

简而言之，给定子串之后进行判断的流程：

1. 统计子串中每个字符出现的次数，记录出现次数为奇数的字符数为odd
2. 判断 odd / 2 和 k 的大小关系，如果 odd / 2 <= k ，则该子串可以在k次替换以内变成回文串

另一个问题来了，如果每次对子串进行判断，则时间复杂度会很高，而且会出现很多次重复的统计。怎么解决呢，那当然是以空间换时间了！

因此可以维护一个unordered_map<char, vector<int>> m来保存每个字符在字符串中累计出现的次数。（好吧，上一道题没用积分，这道题却没绕过）

例如，对于字符串”abcabe”，m[‘a’]的值为[0, 1, 1, 1, 2, 2, 2]，m[‘b’]的值为[0, 0, 1, 1, 1, 2, 2]。当query为[0, 3, 1]的时候，子串为”abca”，可以用m[‘a’][4] - m[‘a’][0] = 2，得到子串中’a’出现的次数为2，以此类推得到所有字符的出现次数。

代码：

class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        unordered_map<char, vector<int>> m;
        for (int i = 0; i < 26; i++)
        {
            m['a' + i] = vector<int>(s.size() + 1, 0);
        }
        for (int i = 0; i < s.size(); i++)
        {
            for (char c = 'a'; c <= 'z'; c++)
            {
                if (c == s[i])
                    m[c][i + 1] = m[c][i] + 1;
                else
                    m[c][i + 1] = m[c][i];
            }
        }

        vector<bool> res;
        for (auto q : queries)
        {
            int odd = 0;
            for (char c = 'a'; c <= 'z'; c++)
            {
                int cnt = m[c][q[1] + 1] - m[c][q[0]];
                if (cnt % 2 == 1)
                    odd++;
            }
            res.push_back(odd / 2 <= q[2]);
        }
        return res;
    }
};