LeetCode刷题笔记
目录
2744.最大字符串配对数目
思路：模拟
遍历每一个字符串，将每一个字符串都放入哈希表中，在放入哈希表之前，反转字符串，判断哈希表中是否已存在反转后的字符串，若已存在，则证明配对成功。
代码
class Solution {
public:
int maximumNumberOfStringPairs(vector<string>& words) {
unordered_set<string> st;
int ans = 0;
for (auto &s : words) {
auto r = s;
reverse(r.begin(), r.end());
if (st.count(r)) ans++;
st.insert(s);
}
return ans;
}
};
2745.构造最长的新字符串
思路：分类讨论
(1)如果x>y，显然 AA 最多只能放进来 (y+1) 个，因为剩下的 AA 后面就没东西可以接了。而 AB 可以放在最开头，形成 ABAB...ABAABBAABB...AA 这样的字符串。因此这种情况的答案是 (2y+1+z)×2。
(2)如果 x=y，我们可以形成
ABAB...ABAABBAABB...AABB这样的字符串。因此这种情况的答案是2(x+y+z)×2。(3)如果 x<y，和第一类情况相似，
BB最多只能放进来(x+1) 个，否则剩下的BB前面就没东西可以接了。而 AB 可以放在最末尾，形成 BBAABBAA...BBABAB...AB 这样的字符串。因此这种情况的答案是 (2x+1+z)×2。
代码：
class Solution {
public:
int longestString(int x, int y, int z) {
if (x > y) return (2 * y + 1 + z) * 2;
else if (x == y) return (x + y + z) * 2;
else return (2 * x + 1 + z) * 2;
}
};
2746.字符串连接删减字母
思路：DP
DP。一个经典的状态压缩方式是因为处理完前 i 个串时，第 i 个串要么在最前面，要么在最后面，所以拼成的串的头或者尾是确定的。这样先消掉一个 ∣Σ∣ 的复杂度。
具体地，添加完第 i−1 个字符串 x…y，接下来将添加第 i 个字符串 时，令 f[j] 表示使用前 i−1 个字符串得到的字符串开头为 j，结尾为 y（即以第 i−1 个字符串结尾）时能重叠的最多字符数。类似地，令 [j] 表示使用前 i−1 个字符串得到的字符串结尾为 j，开头为 x（即以第 i−1 个字符串开头）时能重叠的最多字符数。
(1)在 f[j] 前添加第 i 个字符串。转移到 f1[y]，如果 y1=j 则可以多重叠一个字符。注意对于所有 j 转移到的地方是一样的，所以只需维护 f 数组中的 max。
(2)在 f[j] 后添加第 i 个字符串。仍然转移到 f[j]，但如果 y=x1 则可以多重叠一个字符。注意对于所有 j 这个增量是一样的，所以可以维护对整个 f 的一个增量标记 add。
代码：
const int N=1005,CH=256,inf=1<<20;
int f[CH],f1[CH];
inline void upd(int &x,int y){if (y>x)x=y;}
class Solution {
public:
int minimizeConcatenatedLength(vector<string>& a) {
int n=a.size(),add=0,add1=0,ma=0,ma1=0;
for (int i='a';i<='z';++i)f[i]=f1[i]=-inf;
f[a[0][0]]=0; f1[a[0].back()]=0;
for (int i=1;i<n;++i){
char x=a[i-1][0],y=a[i-1].back(),x1=a[i][0],y1=a[i].back();
int v=max(f[y1]+1+add,ma),v1=max(f1[x1]+1+add1,ma1);
if (y==x1)++add,++ma;
if (y1==x)++add1,++ma1;
upd(ma1,v); upd(ma,v1);
upd(f1[y],v-add1); upd(f[x],v1-add);
}
int ans=-max(ma,ma1);
for (int i=0;i<n;++i)ans+=a[i].size();
return ans;
}
};
2747.统计没有收到请求的服务器数目
思路：滑动窗口
为方便回答询问，可以把 logs 的时间和询问都从小到大排序。对于询问，为了不打乱顺序，可以创建一个下标数组对其排序。由于询问的窗口大小是固定的，所以可以用滑动窗口（双指针）来算，维护窗口内的各个服务器收到了多少次请求 cntcnt，以及没有收到请求的服务器数目。
代码：
class Solution {
public:
vector<int> countServers(int n, vector<vector<int>> &logs, int x, vector<int> &queries) {
int nq = queries.size(), id[nq], cnt[n + 1];
memset(cnt, 0, sizeof(cnt));
iota(id, id + nq, 0);
sort(id, id + nq, [&](int i, int j) {
return queries[i] < queries[j];
});
sort(logs.begin(), logs.end(), [](const auto &a, const auto &b) {
return a[1] < b[1]; // 按照 time 排序
});
vector<int> ans(nq);
int out_of_range = n, left = 0, right = 0;
for (int i: id) {
while (right < logs.size() && logs[right][1] <= queries[i]) // 进入窗口
if (cnt[logs[right++][0]]++ == 0)
out_of_range--;
while (left < logs.size() && logs[left][1] < queries[i] - x) // 离开窗口
if (--cnt[logs[left++][0]] == 0)
out_of_range++;
ans[i] = out_of_range;
}
return ans;
}
};
- 点赞
- 收藏
- 关注作者
评论（0）