欢迎大家加QQ群：623375442。第二题脑筋急转弯，第三题不会做。有点毒。
100671. Find Most Frequent Vowel and Consonant
给你一个由小写英文字母（'a' 到 'z'）组成的字符串 s。你的任务是找出出现频率 最高 的元音（'a'、'e'、'i'、'o'、'u' 中的一个）和出现频率最高的辅音（除元音以外的所有字母），并返回这两个频率之和。
注意：如果有多个元音或辅音具有相同的最高频率，可以任选其中一个。如果字符串中没有元音或没有辅音，则其频率视为 0。
一个字母 x 的 频率 是它在字符串中出现的次数。
测试样例：
输入：s = "successes"
输出：6
解释：元音有：'u' 出现 1 次，'e' 出现 2 次。最大元音频率 = 2。辅音有：'s' 出现 4 次，'c' 出现 2 次。最大辅音频率 = 4。输出为 2 + 4 = 6。
解答：
- 统计字符频次：使用长度为 26 的数组 count，遍历字符串 s，将每个字母出现的次数累加到对应索引。
- 判断元音与辅音：定义 isVowel 方法判断字符是否为元音（a, e, i, o, u）。
- 分别查找最大频次：维护 best[0] 表示最高频元音所在的索引，best[1] 表示最高频辅音所在的索引，初始值分别为 0（代表 'a'）和 1（代表 'b'）。遍历所有字母，若是元音且频次更大，则更新 best[0]；若是辅音且频次更大，则更新 best[1]。
- 结果计算：返回 count[best[0]] + count[best[1]] 即为答案。
class Solution {
private static final char[] vowel = {'a','e','i','o','u'}; // 元音数组
public int maxFreqSum(String s) {
// 1. 统计所有字符出现频次
int[] count = new int[26];
for (int i = 0; i < s.length(); ++i) {
count[s.charAt(i) - 'a'] += 1; // 将字符转换为索引，并累加
}
// 2. best[0] 存储最高频元音的索引，best[1] 存储最高频辅音的索引
int[] best = {0, 1};
for (int i = 0; i < 26; ++i) {
if (isVowel((char)(i + 'a'))) {
// 如果是元音且频次大于当前记录，则更新
if (count[i] > count[best[0]]) {
best[0] = i;
}
} else {
// 如果是辅音且频次大于当前记录，则更新
if (count[i] > count[best[1]]) {
best[1] = i;
}
}
}
// 3. 返回最高频元音频次加上最高频辅音频次
return count[best[0]] + count[best[1]];
}
// 判断给定字符是否为元音
private boolean isVowel(char c) {
for (char v : vowel) {
if (v == c) {
return true;
}
}
return false;
}
}100637. Minimum Operations to Convert All Elements to Zero
给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。
在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。
返回使整个数组变为 0 所需的最少操作次数。
一个 子数组 是数组中的一段连续元素。
测试样例：
输入：nums = [0,2]
输出：1
解释: 选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为 [0,0]。因此，所需的最少操作次数为 1。
解答：
- 单调栈思想：利用栈保存当前未处理的递增序列。
- 遍历数组元素 n：
- 若 n 为 0，则将栈中所有大于 0 的元素视为一次操作（因为每个块最低值都可清零），计数累加，然后清空栈。
- 若 n 非 0，则不断弹出栈顶元素 > n，对每次弹出计为一次操作；若栈为空或栈顶 < n，则将 n 入栈。
- 遍历结束后清理栈：将栈中剩余的所有 > 0 的元素逐个弹出，并对每次弹出计为一次操作。这样就能得到最少操作次数。
class Solution {
public int minOperations(int[] nums) {
Stack<Integer> stack = new Stack<>(); // 单调递增栈
int res = 0; // 记录操作次数
for (int n : nums) {
if (n == 0) {
// 遇到 0 时，将栈中所有正数块视为一次操作后清空
while (!stack.isEmpty()) {
if (stack.peek() > 0) res++;
stack.pop();
}
} else {
// 弹出所有大于当前值的元素，每弹出一次代表一次操作
while (!stack.isEmpty() && stack.peek() > n) {
res++;
stack.pop();
}
// 若栈为空或栈顶小于当前值，则将当前值入栈
if (stack.isEmpty() || stack.peek() < n) {
stack.push(n);
}
}
}
// 遍历完毕后，将剩余栈内正数逐个清零
while (!stack.isEmpty()) {
if (stack.peek() > 0) res++;
stack.pop();
}
return res;
}
}100658. Subtree Inversion Sum
给你一棵以节点 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 的节点集合。
测试样例：
输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], nums = [4,-8,-6,3,7,-2,5], k = 2
输出：27
解释: 对节点 0、3、4 和 6 执行反转操作。最终的 nums 数组为 [-4, 8, 6, 3, 7, 2, 5]，总和为 27。
解答：
- DP 状态定义：dp[pos][distance][mark] 表示在以 pos 为当前节点、父节点到最近一次反转节点的距离为 distance、当前节点是否已受到反转影响 (mark=1 表示已反转奇数次，否则为偶数次) 时，子树能获得的最大和。
- 距离维护：当 distance > 0 时，说明当前节点不能再次反转，只能继承 mark 状态，值乘以 (+1 或 -1) 后，继续对孩子节点递归，距离减一。
- 可选反转：当 distance == 0 时，有两种选择：
- 不反转当前节点，保持 mark，将子树全部按当前 mark 递归。
- 反转当前节点：nextMark = mark ^ 1，以 nums[pos] * (nextMark==1?-1:1) 加上孩子节点的 dfs(n, pos, k-1, nextMark)，然后取二者最大值。
- 记忆化：使用 dp 三维数组避免重复计算。
class Solution {
class Data {
List<Integer>[] edges; // 邻接表
int[] nums; // 节点值数组
int k; // 距离约束
Long[][][] dp; // 记忆化 DP 数组
public Data(int[][] _edges, int[] _nums, int _k) {
nums = _nums;
k = _k;
int n = nums.length;
dp = new Long[n][k + 1][2]; // 三维 DP
edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
// 构建无向树的邻接表
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
}
}
public long subtreeInversionSum(int[][] edges, int[] nums, int k) {
Data data = new Data(edges, nums, k);
// 从根节点 0 开始 DFS，初始距离 0，未反转状态 0
return dfs(0, -1, 0, 0, data);
}
// DFS 函数：pos=当前节点，pre=父节点，distance=可再次反转前的最小距离，mark=当前反转状态
private long dfs(int pos, int pre, int distance, int mark, Data data) {
// 如果是叶子节点，直接计算当前值（考虑是否反转）
if (data.edges[pos].size() == 1 && pre != -1) {
// distance==0 意味着不能再受限，直接返回绝对值；否则根据 mark 返回对应符号的值
return distance == 0 ? Math.abs(data.nums[pos]) : ((mark == 0 ? 1 : -1) * data.nums[pos]);
} else if (data.dp[pos][distance][mark] == null) {
if (distance > 0) {
// 距离限制尚未到，不能反转，只能继承 mark
data.dp[pos][distance][mark] = (mark == 0 ? 1L : -1L) * data.nums[pos];
for (int n : data.edges[pos]) {
if (n != pre) {
data.dp[pos][distance][mark] += dfs(n, pos, distance - 1, mark, data);
}
}
} else {
// distance == 0，可选择是否在此节点反转
// 情况一：不反转，保持 mark
long n1 = (mark == 0 ? 1L : -1L) * data.nums[pos];
for (int n : data.edges[pos]) {
if (n != pre) {
n1 += dfs(n, pos, 0, mark, data);
}
}
// 情况二：反转，翻转 mark
int nextMark = mark ^ 1;
long n2 = (nextMark == 0 ? 1L : -1L) * data.nums[pos];
for (int n : data.edges[pos]) {
if (n != pre) {
n2 += dfs(n, pos, data.k - 1, nextMark, data);
}
}
// 取两种选择的最大值
data.dp[pos][distance][mark] = Math.max(n1, n2);
}
}
return data.dp[pos][distance][mark];
}
}