5173.质数序列
题目描述
请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。
让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1：
1
2
3
| 输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
|
示例 2：
提示：
解法
明白题意，质数所对应的索引只能放质数，当然非质数所对应的索引只能放非质数
所以我们可以求出质数的个数然后求全排列数x!，非质数的个数求全排列数y!，然后求x!*y!即为最后结果
注意每一步对10^9+7取余
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
int numPrimeArrangements(int n) {
long long sumz=1;
long long sumnz=1;
int z=0;
int nz=1;
for(int i=2;i<=n;i++)
{
if(zhishu(i))
{
z++;
sumz=sumz*z%(1000000007);
}
else
{
nz++;
sumnz=sumnz*nz%(1000000007);
}
}
int sum=(sumz*sumnz)%(1000000007);
return sum;
}
bool zhishu(int i)
{
for(int k=2;k<=i/2;k++)
{
if(i%k==0)
return false;
}
return true;
}
};
|
5174.健身计划评估
题目描述
你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。
他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。
为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他 「这一天以及之后的连续几天」 （共 k 天）内消耗的总卡路里 T：
- 如果
T < lower，那么这份计划相对糟糕，并失去 1 分；
- 如果
T > upper，那么这份计划相对优秀，并获得 1 分；
- 否则，这份计划普普通通，分值不做变动。
请返回统计完所有 calories.length 天后得到的总分作为评估结果。
注意：总分可能是负数。
示例 1：
1
2
3
| 输入：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：
1
2
3
| 输入：calories = [3,2], k = 2, lower = 0, upper = 1
输出：1
解释：calories[0] + calories[1] > upper, 总分 = 1.
|
示例 3：
1
2
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^50 <= calories[i] <= 200000 <= lower <= upper
解题思路
理解题干，注意：每次计划表是移动1个单位，并不是移动k个单位
解法1：暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
int n=calories.size();
int res=0;
for(int i=0;i<=n-k;i++)
{
int sum=0;
for(int j=0;j<k;j++)
{
sum+=calories[i+j];
}
if(sum<lower)
res--;
else if(sum>upper)
res++;
}
return res;
}
};
|
解法2：动态规划
记录每个位置到开头总的消耗卡路里总量，计算a[i]与a[i-k]之差就可得到这份计划表的卡路里量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
int n=calories.size();
int res=0;
vector<int> a(n+1,0);
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+calories[i-1];
}
for(int i=k;i<=n;i++)
{
int temp=a[i]-a[i-k];
if(temp>upper)
res+=1;
else if(temp<lower)
res-=1;
}
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，可以认为每次检测都是独立的）
示例：
1
2
3
4
5
6
7
8
| 输入：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^50 <= queries[i][0] <= queries[i][1] < s.length0 <= queries[i][2] <= s.lengths 中只有小写英文字母
解题思路
同样是dp策略，构建dp数组a[n][26]，对s字符串，记录从0到当前位置各个字符出现的次数；
然后分析queries 对于每个query来说
我们构建一个数组b[26] 来表示在这段字符串中每个字符出现的次数，我们通过计算a[r][i]-a[l-1][i]便能得到b[i]的值
判断b[i]里有多少个奇数c，若c//2<=k则能构成回文串，否则为false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int n=s.size();
vector<vector<int>> a(n,vector<int>(26,0));
a[0][s[0]-'a']++;
for(int i=1;i<n;i++)
{
for(int j=0;j<26;j++)
{
a[i][j]=a[i-1][j];
}
a[i][s[i]-'a']++;
}
int m=queries.size();
vector<bool> res(m,false);
int i=0;
for(auto query:queries)
{
int l=query[0];
int r=query[1];
int k=query[2];
int b[26];
for(int i=0;i<26;i++)
{
b[i]=a[r][i];
if(l-1>=0)
b[i]-=a[l-1][i];
}
int c=0;
for(int i=0;i<26;i++)
{
c+=b[i]&1;
}
if(c/2<=k)
res[i]=true;
i++;
}
return res;
}
};
|
5176.猜字谜
题目描述
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
- 单词
word 中包含谜面 puzzle 的第一个字母。
- 单词
word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 “abcdefg”，那么可以作为谜底的单词有 “faced”, “cabbage”, 和 “baggage”；而 “beefed”（不含字母 “a”）以及 “based”（其中的 “s” 没有出现在谜面中）。
返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
示例：
1
2
3
4
5
6
7
8
9
10
11
| 输入：
words = ["aaaa","asas","able","ability","actt","actor","access"],
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
输出：[1,1,3,2,4,0]
解释：
1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。
|
提示：
1 <= words.length <= 10^54 <= words[i].length <= 501 <= puzzles.length <= 10^4puzzles[i].length == 7words[i][j], puzzles[i][j] 都是小写英文字母。- 每个
puzzles[i] 所包含的字符都不重复。
解题思路
此题借鉴大佬：小白二号
思路：
1.首先构建一个map数组map<pair<int,int>,int> wordmap;用来存每个单词 由值对做键，数量做值（学到了，可以这样建map）
2.pair中第一个int 表示该word中个字母组成的bitset用int表示的数，第二个int是用来判断是否存在puzzle[i]的第一个字母，已确定能否让res[i]的个数加1
技巧1：用int bit 存一个单词中每个字母是否出现过，因为字母只有26个 int可以表示32位，我们可以用二进制每一个位置来表示不同的字母，如$(1)_2$表示a，$(10)_2$表示b，依次类推
技巧2：遍历puzzle的子集，同样通过位运算来遍历，
首先我们知道puzzle的非空子集总共为（1<<len)-1个即127个，然后我们同样创建bit来表示该子集中的字母用int表示的数，通过i与（1<<j）进行&运算，可知puzzle[j]能否放入该子集中，若能，我们再进行bit=bit与(1<<(puzzle[j]-‘a’))进行|运算，将其加入到bit中，最后我们将bit放入 ret数组，外层循环遍历完，返回ret数组
3.遍历puzzle[i]的子集sub，count+=map[make_pair(sub,pubble[0]-‘a’)]
count即为puzzle[i]的答案数组res[i]对应的数值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| class Solution {
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
map<pair<int,int>,int> wordmap;
for(auto word:words)
{
int count=0;
int bit=0;
for(auto c:word)
{
int index=c-'a';
if(bit&(1<<index))
{
}
else
{
bit+=(1<<index);
count++;
}
}
if(count>=8)
continue;
for(int i=0;i<26;i++)
{
if(bit&(1<<i))
wordmap[make_pair(bit,i)]++;
}
}
vector<int> res;
for(auto puzzle:puzzles)
{
vector<int> temp=make(puzzle);
int count=0;
for(auto sub:temp)
{
count +=wordmap[make_pair(sub,puzzle[0]-'a')];
}
res.push_back(count);
}
return res;
}
vector<int> make(string puzzle)
{
int len=puzzle.size();
vector<int> ret;
for(int i=1;i<(1<<len);i++)
{
int bit=0;
for(int j=0;j<len;j++)
{
if(i&(1<<j))
{
bit=bit|(1<<puzzle[j]-'a');
}
}
ret.push_back(bit);
}
return ret;
}
};
|
时间复杂度：O($10^4 *(2^7-1)$) puzzles最长10^4 puzzle 又长度固定为7 所以每个的子集 固定为2^7个 ，所以这样时间不会超限