LeetCode Weekly Contest 266
2024-10-15 23:40:13
第一题
题解：模拟题
class Solution {
public:
int countVowelSubstrings(string w) {
int n = w.length();
int i = 0, res = 0;
string p = "aeiou";
while(i < n){
if(p.find(w[i]) != -1){
int j = i;
while(j < n && p.find(w[j]) != -1){
if(j < i+4) {
j++;
continue;
}
string s = w.substr(i, j-i+1);
set<char> set;
for(auto c : s){
if(!set.count(c)){
set.insert(c);
}
}
if(set.size() >=5){
res++;
}
j++;
}
}
i++;
}
return res;
}
};
第二题
题解：不能直接求子集判断超时，将问题转化为求每一个字母被使用的次数，第i个字母会在出现在 (n - i) * (i + 1) 个子串中
class Solution {
public:
long long countVowels(string w) {
string p = "aeiou";
long long res = 0;
for(int i=0; i<w.length(); i++){
if(p.find(w[i]) != -1){
res += (long long)(i+1) *(w.length()-i);
}
}
return res;
}
};
第三题
二分满足每一个商店商品数量 大于等于 k，通过商品数组中的商品数量计算店铺数量是否超过 n 来进行二分。
class Solution {
public:
int minimizedMaximum(int n, vector<int>& q) {
int l = 1;
int r = 0;
for(auto c : q) r = max(r, c);
while(l < r){
int mid = l+r >>1;
if(check(q, mid, n)){
r = mid;
}else{
l = mid+1;
}
}
return r;
}
bool check(vector<int> q, int k, int n){
int cnt = 0;
for(auto c : q){
if(c%k == 0){
cnt += c/k;
}else cnt += (c/k)+1;
if(cnt > n) return false;
}
return true;
}
};
第四题
题解：dfs， 注意 路径中节点值只能计算一次， 另外方法传递vector参数使用引用，不用最后一个用例超时了。
#define PII pair<int, int>
class Solution {
public:
unordered_map<int, vector<PII>> g;
int res = 0, maxTimeV;
int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
maxTimeV = maxTime;
for(auto e : edges){
// 无向边
g[e[0]].push_back({e[1], e[2]});
g[e[1]].push_back({e[0], e[2]});
}
vector<int> path; // 记录路径
dfs(values, 0, 0, 0, path);
return res;
}
void dfs(vector<int>& values,int u, int time, int value, vector<int> path){
path.push_back(u);
int prevVal = values[u];
value += values[u];
// 置为 0，节点只计算一次value
values[u] = 0;
if(u == 0){
res = max(res, value);
}
for(auto c : g[u]){
if(time + c.second > maxTimeV) continue;
dfs(values, c.first, time+c.second, value, path);
}
// 恢复现场
path.pop_back();
values[u] = prevVal;
value -= prevVal;
}
};
最新文章
- Codeforces Round #258 (Div. 2)
- Leetcode:378. Kth Smallest Element in a Sorted Matrix
- Linux正则表达式grep
- POJ 1068
- [SAP ABAP开发技术总结]程序自己以JOB方式运行
- [CSS]置换和非置换元素
- 解决Windows8系统磁盘占用太多100%或99%
- getting start with storm 翻译 第八章 part-2
- jar包和war包的区别：
- Excel教程(13) - 统计函数
- Gentoo挂载ntfs的NTFS分区
- Spinnerd的功能和用法
- Redis 学习笔记-入门
- springboot+VUE(二)
- mysql 开发进阶篇系列 6 锁问题(事务与隔离级别介绍)
- 转载：搭建完整的arm-linux-gcc等交叉编译环境（感谢CSDN博主的分享）
- 异步编程（async&await）
- Mac下的安装 mongodb
- 6.13 py网络编程
- jquery不能实时获取CKEDITOR值的解决方法