day01
检查整数及其两倍数是否存在
水题
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
|
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkIfExist(vector<int>& arr) {
unordered_map<int,int> mp;
for(auto i:arr)
{
if((i%2==0&&mp.count(i/2))||mp.count(i*2))
return 1;
mp[i]=1;
}
return 0;
}
};
signed main()
{
Solution s;
return 0;
}
|
day02
有效的快递序列数目
一开始以为是dp,但看这个范围不太像的样子
推公式也没推出来QAQ
首先如果没有$P_i$和$D_i$的限制,那么就是很快乐的$(2n)!$
接下来考虑条件,对于不满足条件的$P_i$和$D_i$,只需要调换二者的顺序,就可以得到符合条件的答案
剩下的就是考虑重复的问题了
怎么考虑呢
比如说序列
按上述规则调换后为同一个序列
那么有多少重复呢
已知有n对$P_i$和$D_i$,对于每一对可以选择互换位置或者不换,所以共有$2^n$种排列
所以就只需要计算${(2n)!} \over {2^n}$啦
展开 1,2,3,..,2n
把每个偶数除以2
变成 1,2,..n,1,3,5,..,2n-1
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
|
#include<bits/stdc++.h>
using namespace std;
class Solution {
int p=1e9+7;
public:
int countOrders(int n) {
long long x=1;
for(int i=1;i<=n;i++)
x=x*i%p;
n=2*n-1;
for(int i=1;i<=n;i+=2)
x=x*i%p;
return x;
}
};
signed main()
{
Solution s;
return 0;
}
|
day03
日期之间隔几天
快乐模拟
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
|
#include<bits/stdc++.h>
using namespace std;
class Solution {
bool is_r(int y)
{
if(y%400==0) return 1;
if(y%100==0) return 0;
return y%4==0;
}
int r[13]={0,31,29,31,30,31,30,
31,31,30,31,30,31};
int p[13]={0,31,28,31,30,31,30,
31,31,30,31,30,31};
int so(int y,int m,int d)
{
int ans=0;
for(int i=1971;i<y;i++)
if(is_r(i)) ans+=366;
else ans+=365;
if(is_r(y))
for(int i=1;i<m;i++) ans+=r[i];
else
for(int i=1;i<m;i++) ans+=p[i];
ans+=d;
return ans;
}
public:
int daysBetweenDates(string date1, string date2) {
return abs(
so((date1[0]-'0')*1000+(date1[1]-'0')*100+(date1[2]-'0')*10+(date1[3]-'0'),
(date1[5]-'0')*10+(date1[6]-'0'),
(date1[8]-'0')*10+(date1[9]-'0'))-
so((date2[0]-'0')*1000+(date2[1]-'0')*100+(date2[2]-'0')*10+(date2[3]-'0'),
(date2[5]-'0')*10+(date2[6]-'0'),
(date2[8]-'0')*10+(date2[9]-'0'))
);
}
};
signed main()
{
Solution s;
s.daysBetweenDates("2020-01-15","2019-12-31");
return 0;
}
|
day04
上升下降字符串
快乐模拟
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
|
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
string sortString(string s) {
int a[27]={0};
for(auto i:s) a[i-'a']++;
string ans="";
ans.resize(s.size());
bool f=1;
int cnt=0;
while(f)
{
f=0;
for(int i=0;i<26;i++)
{
if(a[i])
{
f=1;
ans[cnt++]='a'+i;
a[i]--;
}
}
for(int i=25;i>=0;i--)
{
if(a[i])
{
f=1;
ans[cnt++]='a'+i;
a[i]--;
}
}
}
return ans;
}
};
signed main()
{
Solution s;
return 0;
}
|
day05
每个元音包含偶数次的最长子字符串
这个数据范围看起来就是o(n) 做法
首先想到前缀和思想,但由于答案只和奇偶有关而和具体数值无关,所以可以简化为01两种状态
只有5个元音字母,采用状压,维护32种状态的最大值和最小值就行了
当i-1和j的状态相同时, [ i,j ]段的字串即为所求
注意,i,j从1开始,0位置状态为0,即ans[0].l=0
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
61
62
63
|
#include<bits/stdc++.h>
using namespace std;
class Solution {
struct no{
int l=-1,r=-1;
};
no ans[35];
public:
int findTheLongestSubstring(string s) {
int x=0;
int a,e,i,o,u;
a=e=i=o=u=0;
int n=s.size();
ans[0].l=0;
for(int j=0;j<n;j++)
{
switch (s[j]) {
case 'a':
a=1-a;
break;
case 'e':
e=1-e;
break;
case 'i':
i=1-i;
break;
case 'o':
o=1-o;
break;
case 'u':
u=1-u;
break;
}
x=a*16+e*8+i*4+o*2+u;
if(ans[x].l==-1) ans[x].l=j+1;
else ans[x].r=j+1;
}
int cnt=0;
for(int j=0;j<32;j++)
{
if(ans[j].l!=-1&&ans[j].r!=-1)
cnt=max(cnt,ans[j].r-ans[j].l);
}
return cnt;
}
};
signed main()
{
Solution s;
s.findTheLongestSubstring("eleetminicoworoep");
return 0;
}
|
day06
二叉树中的最长交错路径
搜索,但跑出来数据不是很好看QAQ
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
|
#include<bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
int ans=0;
void dfs(TreeNode* r,int num,bool f)
{
ans=max(ans,num);
if(f)
{
if(r->right) dfs(r->right,num+1,0);
if(r->left) dfs(r->left,1,1);
}
else
{
if(r->left) dfs(r->left,num+1,1);
if(r->right) dfs(r->right,1,0);
}
return;
}
public:
int longestZigZag(TreeNode* root) {
if(!root) return 0;
if(root->left)
dfs(root->left,1,1);
if(root->right)
dfs(root->right,1,0);
return ans;
}
};
signed main()
{
Solution s;
return 0;
}
|