这周leetcode的题还是比较简单的，最近期末了可能更新会变慢，祝大家期末都能考好
希望我期末不挂科！这样我假期就可以好好打cf了，上大分！
A
map,水水水
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
map<int,int>mp1;
map<int,int>mp2;
public:
vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
vector<int>ans(2,0);
for(auto &i:nums1)mp1[i]=1;
for(auto &i:nums2)mp2[i]=1;
for(auto &i:nums1){
if(mp2[i])ans[0]+=mp2[i];
}
for(auto &i:nums2){
if(mp1[i])ans[1]+=mp1[i];
}
return ans;
}
};
|
B
很简单，观察可得如果有一个相邻元素近似的子串，我们一定是隔两个操作一个，所以只用记录长度然后ans+cnt/2就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int removeAlmostEqualCharacters(string word) {
int len=word.size();
int ans=0,cnt=1;
for(int i=1;i<len;i++){
while(abs(word[i]-word[i-1])<=1){
cnt++;
i++;
}
ans+=cnt/2;
cnt=1;
}
return ans;
}
};
|
C
滑动窗口，拿一个map记录元素出现次数，每加进一个元素看看新加的元素的次数是否超过k，while超过就pop，过程中最大的队列长度就是要求的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
map<int,int>mp;
queue<int>q;
public:
int maxSubarrayLength(vector<int>& nums, int k) {
int ans=0;
for(auto &i:nums){
q.push(i);
mp[i]++;
while(q.size()&&mp[i]>k){
mp[q.front()]--;
q.pop();
}
int len=q.size();
ans=max(ans,len);
}
return ans;
}
};
|
D
别看了，没做出来。TxT
想到了floyd但是不太会状态压缩和实现，但是能想到floyd的这种中间节点的桥梁性我觉得说明我对算法的理解也是有上升的。
可惜现在还不太会做，中午听完灵神的思路回来就更新！
第一个双百！！
首先观察数据范围 n是1-10 说明用到的算法时间复杂度可以很高
观察这个过程，非常明显的floyd特性，但是需要想到的是如何表示每一个子集以及选or不选的状态表示呢？
用到的就是状态压缩的模拟
观察到一个很妙的特性，n的子集有2的n次方个，恰好就是二进制位数为n可表示的数据范围，从0一直到1<<n就可以取到n的所有子集，
这里是是<(1<<n)。**如果n位全取1，则最大为1<<n-1,如果全取0就是0，所以我们要枚举的范围就是0-1<<n-1。**接下来要注意的是floyd。首先是邻接矩阵存边，因为会有重边所以取最小值。**别忘记初始化！！**在存储的时候要想到，如果一个点被去掉（未选中）那么所有边都无法到达它，所以将所有可以取到的边复制到d数组就可以。接下来就是floyd的主题，在每一层循环里都要判断当前取得i，j，k都是可选中的点。最后遍历d数组，也要确定都是可取得的点，如果有距离大于maxdistance，那么就返回false，否则返回true。ans累加每一个子集的check结果就好了。
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
| class Solution {
using i64=long long;
int d[15][15],a[15][15];
public:
int numberOfSets(int n, int md, vector<vector<int>>& roads) {
memset(a,0x3f,sizeof a);
for(int i=0;i<n;i++){
a[i][i]=0;
}
for(auto &e:roads){
int x=e[0],y=e[1],w=e[2];
a[x][y]=min(a[x][y],w);
a[y][x]=min(a[y][x],w);
}
auto check=[&](int s)->bool{
for(int i=0;i<n;i++){
if((s>>i)&1){
for(int j=0;j<n;j++){
d[i][j]=a[i][j];
}
}
}
for(int k=0;k<n;k++){
if(((s>>k)&1)==0)continue;
for(int i=0;i<n;i++){
if((s>>i&1)==0)continue;
for(int j=0;j<n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
for(int i=0;i<n;i++){
if(((s>>i)&1)==0)continue;
for(int j=0;j<n;j++){
if((s>>j)&1&&d[i][j]>md)return false;
}
}
return true;
};
int ans=0;
for(int s=0;s<(1<<n);s++){
ans+=check(s);
}
return ans;
}
};
|
