周赛传送门
来补leetcode的周赛了
先补上传送门：https://leetcode-cn.com/contest/weekly-contest-137
1046. 最后一块石头的重量
题目
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎；
- 如果
x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
题解
首先我们的目标是让石头剩下越少越好，所以意味着我们每次需要去找最接近的两块石头进行碰撞，得到了这个思路之后我们就可以使用优先队列快速解决这个问题(排序也可以，但是每次碰撞完之后需要将得到的新石头插入到原来的石头的序列中，时间复杂度和代码复杂度都比用优先队列高了点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
priority_queue<int> que;
int lastStoneWeight(vector<int>& stones) {
while(que.size()) que.pop();
for(int i=0;i<stones.size();i++)
que.push(stones[i]);
while(que.size()>1){
int y=que.top();que.pop();
int x=que.top();que.pop();
if(x==y){
continue;
}
else{
que.push(y-x);
}
}
if(que.size()==0)
return 0;
else
return que.top();
}
};
|
1047. 删除字符串中的所有相邻重复项
题目
1047. 删除字符串中的所有相邻重复项
显示英文描述
我的提交返回竞赛
- 用户通过次数398
- 用户尝试次数455
- 通过次数400
- 提交次数964
- 题目难度**Easy**
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
1
2
3
4
| 输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
|
提示：
1 <= S.length <= 20000S 仅由小写英文字母组成。
题解
这题不想多说。。。莽就完了，我居然还在考虑更精致的解法，事实证明莽就完了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
string removeDuplicates(string S) {
int flag=1;
for(int k=0;flag;k++){
flag=0;
for(int i=0;i<S.length();i++){
if(S[i+1]==S[i]){
S.erase(i,2);
flag=1;
}
}
}
return S;
}
};
|
1048. 最长字符串链
题目
给出一个单词列表，其中每个单词都由小写英文字母组成。
如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。
从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
示例：
1
2
3
| 输入：[,,,,,]
输出：4
解释：最长单词链之一为 ,,,。
|
提示：
1 <= words.length <= 10001 <= words[i].length <= 16words[i] 仅由小写英文字母组成。
题解
这题好像出题方失误了，比赛中这道题一直卡着大家都过不去
赛后诸葛亮补一波题
这道题首先分两步，第一步是建图(有向无环图)，第二步是求最长的路径，首先建图应该比较简单了(因为judge函数传参没有用实参而是拷贝string疯狂超时QAQ)，然后求最长路径
这里有两种方法解决问题，第一种是DFS求最长路径，第二种是利用SPFA和迪杰斯特拉的松弛操作来求出最长路径
首先先放上DFS的版本
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
| int mp[1010][1010];
int vis[1010];
int n,ans;
class Solution {
public:
bool judge(const string& a,const string& b){
int len1=a.length();
int len2=b.length();
if(len1+1!=len2)
return false;
int i=0,j=0;
while(j<len2){
if(a[i]==b[j])
i++,j++;
else{
j++;
if(j-i>1)
return false;
}
}
return true;
}
void dfs(int u,int d){
vis[u]=1;
for(int v=0;v<n;v++){
if(!vis[v]&&mp[u][v])
dfs(v,d+1);
}
ans=max(ans,d);
}
int longestStrChain(vector<string>& words) {
memset(mp,0,sizeof(mp));
n=words.size();
sort(words.begin(),words.end(),[](string& a,string& b){return a.length()<b.length();});
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(judge(words[i],words[j]))
mp[i][j]=1;
}
}
ans=-(1<<30);
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++){
if(!vis[i])
dfs(i,1);
}
return ans;
}
};
|
然后是SPFA和迪杰斯特拉的松弛版本(将min函数改成max就可以求最长路径)
这题judge函数一开始写的时候没有传引用，结果string类的拷贝直接超时了，以后千万要注意用容器类得加引用
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
| int mp[1010][1010];
int vis[1010];
int n,ans;
class Solution {
public:
bool judge(const string& a,const string& b){
int len1=a.length();
int len2=b.length();
if(len1+1!=len2)
return false;
int i=0,j=0;
while(j<len2){
if(a[i]==b[j])
i++,j++;
else{
j++;
if(j-i>1)
return false;
}
}
return true;
}
int longestStrChain(vector<string>& words) {
memset(mp,0,sizeof(mp));
n=words.size();
sort(words.begin(),words.end(),[](string& a,string& b){return a.length()<b.length();});
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(judge(words[i],words[j]))
mp[i][j]=1;
}
}
vector<int> v(n,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(mp[j][i]){
v[i]=max(v[j]+1,v[i]);
}
}
}
return *max_element(v.begin(),v.end());
}
};
|
1049. 最后一块石头的重量 II
题目
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎；
- 如果
x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
1
2
3
4
5
6
7
| 输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
|
提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
题解
通过严格的分析我们会发现这道题就是将石头分成两个阵营，然后使两个阵营相减得到的答案最小即可，也就是对两个阵营的石头求和的结果越接近越好。
然后我们考虑对所有石块求和为sum，我们只要从石块中挑出一些尽量逼近sum/2，然后选出来的石头和没选出来的石头自然地就被分成了两个阵营。
然后就是如何逼近sum/2的算法，当时比赛中想到了状态压缩dp，可惜超时了，这里先把状态压缩dp的代码放出来(毕竟也是一种思路，虽然时间复杂度是真的高)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int lastStoneWeightII(vector<int>& s){
int len=s.size();
long long ans=1<<30;
for(int n=0;n<(1<<len);n++){
long long sum1=0,sum2=0;
for(int i=0;i<len;i++)
{
if((n>>i)&1)
sum1+=s[i];
else
sum2+=s[i];
}
ans=min(ans,abs(sum1-sum2));
}
return ans;
}
};
|
后来到比赛结束也没想到好的办法。
知道突然醒悟这个是一个01背包，就是选与不选的问题，无非是体积和价值都是石头的和而已，然后背包的初始容量是sum/2，然后就AC了。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int dp[50000];
class Solution {
public:
int lastStoneWeightII(vector<int>& s){
int n=s.size();
int sum=0;
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
sum+=s[i];
for(int i=0;i<n;i++)
for(int j=sum/2;j>=s[i];j--)
dp[j]=max(dp[j],dp[j-s[i]]+s[i]);
return sum-2*dp[sum/2];
}
};
|
总结
还是输在了做题太少，思路不快，还有第二题想得太多不敢暴力，来日再战！