1. 找到频率最高的元音和辅音
给你一个由小写英文字母（
'a'到'z'）组成的字符串s。你的任务是找出出现频率 最高 的元音（'a'、'e'、'i'、'o'、'u'中的一个）和出现频率最高的辅音（除元音以外的所有字母），并返回这两个频率之和。注意：如果有多个元音或辅音具有相同的最高频率，可以任选其中一个。如果字符串中没有元音或没有辅音，则其频率视为 0。
一个字母x的 频率 是它在字符串中出现的次数。
示例 1：
输入: s = "successes"
输出: 6
解释:
- 元音有：
'u'出现 1 次，'e'出现 2 次。最大元音频率 = 2。- 辅音有：
's'出现 4 次，'c'出现 2 次。最大辅音频率 = 4。- 输出为
2 + 4 = 6。示例 2：
输入: s = "aeiaeia"
输出: 3
解释:
- 元音有：
'a'出现 3 次，'e'出现 2 次，'i'出现 2 次。最大元音频率 = 3。s中没有辅音。因此，最大辅音频率 = 0。- 输出为
3 + 0 = 3。提示:
1 <= s.length <= 100s只包含小写英文字母
解题思路：维护两个(元音/辅音)最大值
class Solution {
public:
bool judge(char x){
string s="aeiou";
for(int i=0;i<s.size();i++){
if(s[i]==x){
return true;
}
}
return false;
}
int maxFreqSum(string s) {
unordered_map<char,int> mp;
for(auto& x:s){
mp[x]++;
}
int max_cnt_vo=0,max_cnt_co=0;
for(auto& [x,y]:mp){
if(judge(x)) max_cnt_vo=max(max_cnt_vo,y);
else max_cnt_co=max(max_cnt_co,y);
}
return max_cnt_vo+max_cnt_co;
}
};2. 将所有元素变为 0 的最少操作次数
给你一个大小为
n的 非负 整数数组nums。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。在一次操作中，你可以选择一个子数组
[i, j]（其中0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。返回使整个数组变为 0 所需的最少操作次数。
一个 子数组 是数组中的一段连续元素。
示例 1：
输入: nums = [0,2]
输出: 1
解释:
- 选择子数组
[1,1]（即[2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为[0,0]。- 因此，所需的最少操作次数为 1。
示例 2：
输入: nums = [3,1,2,1]
输出: 3
解释:
- 选择子数组
[1,3]（即[1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为[3,0,2,0]。- 选择子数组
[2,2]（即[2]），将 2 设为 0，结果为[3,0,0,0]。- 选择子数组
[0,0]（即[3]），将 3 设为 0，结果为[0,0,0,0]。- 因此，最少操作次数为 3。
示例 3：
输入: nums = [1,2,1,2,1,2]
输出: 4
解释:
- 选择子数组
[0,5]（即[1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为[0,2,0,2,0,2]。- 选择子数组
[1,1]（即[2]），将 2 设为 0，结果为[0,0,0,2,0,2]。- 选择子数组
[3,3]（即[2]），将 2 设为 0，结果为[0,0,0,0,0,2]。- 选择子数组
[5,5]（即[2]），将 2 设为 0，结果为[0,0,0,0,0,0]。- 因此，最少操作次数为 4。
提示:
1 <= n == nums.length <= 10^50 <= nums[i] <= 10^5
解题思路：用个栈/vector数组进行维护,
请结合图和代码进行理解
class Solution {
public:
int minOperations(vector<int>& nums) {
int ans=0;
stack<int> st;
for(int& x: nums){
while(!st.empty()&&st.top()>x){
st.pop();
}
if(!st.empty()&&x==st.top()){
continue;
}
if (x!=0){
ans++;
st.push(x);
}
}
return ans;
}
};3. K 条边路径的最大边权和
给你一个整数
n和一个包含n个节点（编号从 0 到n - 1）的 有向无环图（DAG）。该图由二维数组edges表示，其中edges[i] = [ui, vi, wi]表示一条从节点ui到vi的有向边，边的权值为wi同时给你两个整数
k和t。你的任务是确定在图中边权和 尽可能大的 路径，该路径需满足以下两个条件：
- 路径包含 恰好
k条边；- 路径上的边权值之和 严格小于
t。返回满足条件的一个路径的 最大 边权和。如果不存在这样的路径，则返回
-1。
解题思路：记忆化搜索
class Solution {
public:
int maxWeight(int n, vector<vector<int>>& edges, int k, int t) {
vector<vector<pair<int, int>>> graph(n);
for (auto& edge : edges) {
int x = edge[0], y = edge[1], z = edge[2];
graph[x].emplace_back(y, z);
}
vector<vector<unordered_map<int, int>>> memo(n, vector<unordered_map<int, int>>(k+1));
int ans = -1;
auto dfs = [&](this auto&&dfs,int x, int s, int sum) {
if (s == k) {
if (sum < t) ans = max(ans, sum);
return;
}
if (memo[x][s].count(sum)) {
return;
}
memo[x][s][sum] = 1;
for (auto& [y, wt] : graph[x]) {
if (sum + wt < t) {
dfs(y, s + 1, sum + wt);
}
}
};
for (int i = 0; i < n; ++i) {
dfs(i, 0, 0);
}
return ans;
}
};4. 子树反转和
给你一棵以节点
0为根节点包含n个节点的无向树，节点编号从 0 到n - 1。该树由长度为n - 1的二维整数数组edges表示，其中edges[i] = [ui, vi]表示节点ui和vi之间有一条边。同时给你一个整数
k和长度为n的整数数组nums，其中nums[i]表示节点i的值。你可以对部分节点执行 反转操作 ，该操作需满足以下条件：
子树反转操作：
当你反转一个节点时，以该节点为根的子树中所有节点的值都乘以 -1。
反转之间的距离限制：
你只能在一个节点与其他已反转节点“足够远”的情况下反转它。
具体而言，如果你反转两个节点
a和b，并且其中一个是另一个的祖先（即LCA(a, b) = a或LCA(a, b) = b），那么它们之间的距离（它们之间路径上的边数）必须至少为k。返回应用 反转操作 后树上节点值的 最大可能 总和 。
在一棵有根树中，某个节点
v的子树是指所有路径到根节点包含v的节点集合。
解题思路：记忆化搜索
class Solution {
public:
long long subtreeInversionSum(vector<vector<int>>& edges, vector<int>& nums, int k) {
int n = nums.size();
vector<vector<int>> graph(n);
for (auto& e : edges) {
int x = e[0], y = e[1];
graph[x].push_back(y);
graph[y].push_back(x);
}
vector<vector<vector<long long>>> memo(n, vector<vector<long long>>(k, vector<long long>(2, -1)));
auto dfs = [&](this auto&& dfs, int x, int fa, int cd, bool f){
auto& res = memo[x][cd][f];
if (res != -1) {
return res;
}
res = f ? -nums[x] : nums[x];
for (int y : graph[x]) {
if (y != fa) {
res += dfs(y, x, max(cd - 1, 0), f);
}
}
if (cd == 0) {
long long s = f ? nums[x] : -nums[x];
for (int y : graph[x]) {
if (y != fa) {
s += dfs(y, x, k - 1, !f);
}
}
res = max(res, s);
}
return res;
};
return dfs(0, -1, 0, 0);
}
};感谢大家的点赞和关注，你们的支持是我创作的动力！(其他细节，有时间再补充...)