T1: 5960. 将标题首字母大写
思路
模拟
Code
class Solution {
public:
string capitalizeTitle(string title) {
title+=" ";
int cnt=0;
vector<string>h;
string s="";
for(auto& i:title){
if(i==' ')
h.emplace_back(s),s="",cnt++;
else
s+=i;
}
int len=h.size();
for(auto& i:h){
int f=i.size();
for(int j=0;j<f;++j){
if(f>2){
if(j==0&&i[j]>='a'&&i[j]<='z')
i[j]-=32;
else if(j!=0&&i[j]>='A'&&i[j]<='Z')
i[j]+=32;
}
if(f<=2){
if(i[j]>='A'&&i[j]<='Z')
i[j]+=32;
}
}
s+=i;
len--;
if(len>0)
s+=" ";
}
return s;
}
};复杂度分析
时间复杂度：O(n2)
空间复杂度：O(1)
T2: 5961. 链表最大孪生和
思路
遍历链表，将数据存进数组里，再按要求计算
Code
class Solution {
public:
int pairSum(ListNode* head) {
vector<int>ha;
while(head){
ha.emplace_back(head->val);
head=head->next;
}
int ma=INT_MIN,n=ha.size()/2-1,len=ha.size();
for(int i=0;i<=n;++i){
ma=max(ma,ha[i]+ha[len-i-1]);
}
return ma;
}
};复杂度分析
- 时间复杂度O(n)。
- 空间复杂度O(n)。
T3: 5962. 连接两字母单词得到的最长回文串
思路
贪心+哈希表
两字母单词最多 26×26 种，我们直接用哈希表统计之后，分两位相同的单词和不同的单词分别处理。
- 对于两位不同的单词，它需要与它的对称单词构成一对才能放入回文串中；
- 对于两位相同的单词，它可以与它自身构成一对；同时，特别的，有且仅有一次，可以把一个两位相同的单词放在正中间。
Code
class Solution {
public:
unordered_map<string,int>ha;
unordered_map<string,bool>f;
int longestPalindrome(vector<string>& words) {
for(auto& i:words)
ha[i]++;
int len=0;
int hh=0;
bool flag=false;
for(auto& i:ha){
string ss=i.first;
if(ss[0]==ss[1]){
if(i.second%2==1)
flag=true;
if(i.second%2==0)
len+=i.second*2;
else if(i.second%2==1)
len+=(i.second-1)*2;
}
else{
int cnt;
string s="";
s+=ss[1];
s+=ss[0];
if(ha.count(s)&&!f.count(s)){
cnt=min(ha[s],i.second);
len+=4*cnt;
f[s]=true,f[ss]=true;
}
}
}
if(flag)
len+=2;
return len;
}
};复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(| ∑^2 |),其中 ∑ 表示字母表
T4: 5931. 用邮票贴满网格图
思路
二维前缀和+二维差分
由于邮票可以互相重叠，我们遵从能放就放邮票的策略，遍历所有的空位，尝试以该空位为左上角放置邮票。如果这一矩形没有出界且区域内没有被占据的格子，那么就可以放置邮票，并按照二维差分的做法将区域内的所有元素值加一。判断区域内有没有被占据的格子，可以先求出 grid 的二维前缀和，这样可以 O(1) 判断。
遍历结束后，我们需要从二维差分矩阵还原出二维计数矩阵，这可以通过对二维差分矩阵求二维前缀和求出。遍历计数矩阵，如果存在一个空格子的计数值为 0，就表明该空格子没有被邮票覆盖，返回 false，否则返回 true。
Code
class Solution {
public:
bool possibleToStamp(vector<vector<int>> &grid, int stampHeight, int stampWidth) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> sum(m + 1, vector<int>(n + 1)), diff(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) { // grid 的二维前缀和
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + grid[i][j];
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x = i + stampHeight, y = j + stampWidth; // 注意这是矩形右下角横纵坐标都 +1 后的位置
if (x <= m && y <= n && sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0) {
++diff[i][j];
--diff[i][y];
--diff[x][j];
++diff[x][y]; // 更新二维差分
}
}
}
// 还原二维差分矩阵对应的计数矩阵
vector<vector<int>> cnt(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
//相当于在一个空数组的基础上利用diff差分数组还原处理后的数组
cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + diff[i][j];
if (cnt[i + 1][j + 1] == 0 && grid[i][j] == 0) {
return false;
}
}
}
return true;
}
};复杂度分析
- 时间复杂度：O(nm)
- 空间复杂度：O(nm)
额外拓展
个人总结
本次双周赛，t1看题不仔细，连wa2次直接白给，t2一眼题，t3考虑情况不清楚，又wa1，t4的话对于二维差分不太熟悉，再加上看题不仔细，然后罚坐到结束。总之，看题应该更仔细不能一味追求时间，反倒疯狂罚时，😭
