LeetCode|LeetCode Weekly Contest 266
第一题
文章图片
【LeetCode|LeetCode Weekly Contest 266】题解：模拟题
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 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第三题
文章图片
二分满足每一个商店商品数量 大于等于 k，通过商品数组中的商品数量计算店铺数量是否超过 n 来进行二分。
class Solution {
public:
int minimizedMaximum(int n, vector& 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 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
class Solution {
public:
unordered_map g;
int res = 0, maxTimeV;
int maximalPathQuality(vector& values, vector>& 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 path;
// 记录路径
dfs(values, 0, 0, 0, path);
return res;
}
void dfs(vector& values,int u, int time, int value, vector 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;
}
};
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- 推酷《Guru|推酷《Guru Weekly》第十四期
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路