欢迎大家加QQ群：623375442，可以方便群里面交流。这周看着唬人，其实题目不难。
100607. Unique 3-Digit Even Numbers
给你一个数字数组 digits，你需要从中选择三个数字组成一个三位偶数，你的任务是求出 不同 三位偶数的数量。
注意：每个数字在三位偶数中都只能使用 一次 ，并且 不能 有前导零。
测试样例：
输入：digits = [1,2,3,4]
输出：12
解释：可以形成的 12 个不同的三位偶数是 124，132，134，142，214，234，312，314，324，342，412 和 432。注意，不能形成 222，因为数字 2 只有一个。
解答：暴力循环，查询所有可能出现的3位数。
class Solution {
public int totalNumbers(int[] digits) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < digits.length; ++i) {
for (int j = 0; j < digits.length; ++j) {
for (int k = 0; k < digits.length; ++k) {
if (i != j && i != k && j != k) {
if (digits[k] % 2 == 0 && digits[i] != 0) {
set.add(digits[i] * 100 + digits[j] * 10 + digits[k]);
}
}
}
}
}
return set.size();
}
}100605. Design Spreadsheet
电子表格是一个网格，它有 26 列（从 'A' 到 'Z'）和指定数量的 rows。每个单元格可以存储一个 0 到 10^5 之间的整数值。
请你实现一个 Spreadsheet 类：
- Spreadsheet(int rows) 初始化一个具有 26 列（从 'A' 到 'Z'）和指定行数的电子表格。所有单元格最初的值都为 0 。
- void setCell(String cell, int value) 设置指定单元格的值。单元格引用以 "AX" 的格式提供（例如，"A1"，"B10"），其中字母表示列（从 'A' 到 'Z'），数字表示从 1 开始的行号。
- void resetCell(String cell) 重置指定单元格的值为 0 。
- int getValue(String formula) 计算一个公式的值，格式为 "=X+Y"，其中 X 和 Y 要么 是单元格引用，要么非负整数，返回计算的和。
注意： 如果 getValue 引用一个未通过 setCell 明确设置的单元格，则该单元格的值默认为 0 。
测试样例：
输入：["Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue", "resetCell", "getValue"]
[[3], ["=5+7"], ["A1", 10], ["=A1+6"], ["B2", 15], ["=A1+B2"], ["A1"], ["=A1+B2"]]输出：[null, 12, null, 16, null, 25, null, 15]
解释:
- Spreadsheet spreadsheet = new Spreadsheet(3); // 初始化一个具有 3 行和 26 列的电子表格
- spreadsheet.getValue("=5+7"); // 返回 12 (5+7)
- spreadsheet.setCell("A1", 10); // 设置 A1 为 10
- spreadsheet.getValue("=A1+6"); // 返回 16 (10+6)
- spreadsheet.setCell("B2", 15); // 设置 B2 为 15
- spreadsheet.getValue("=A1+B2"); // 返回 25 (10+15)
- spreadsheet.resetCell("A1"); // 重置 A1 为 0
- spreadsheet.getValue("=A1+B2"); // 返回 15 (0+15)
解答：这题没啥难度，每个单元格引用由一个大写字母 'A' 到 'Z' 和一个介于 1 和 rows 之间的行号组成。所以row这个数字都可以无视。直接一个HashMap记录就行了。
class Spreadsheet {
private HashMap<String, Integer> mem;
public Spreadsheet(int rows) {
mem = new HashMap<>();
}
public void setCell(String cell, int value) {
mem.put(cell, value);
}
public void resetCell(String cell) {
mem.put(cell, 0);
}
public int getValue(String formula) {
String[] tmp = formula.substring(1).split("\\+");
return getNum(tmp[0]) + getNum(tmp[1]);
}
private int getNum(String t) {
if (t.charAt(0) >= 'A' && t.charAt(0) <= 'Z') {
return mem.getOrDefault(t, 0);
} else {
return Integer.parseInt(t);
}
}
}100594. Longest Common Prefix of K Strings After Removal
给你一个字符串数组 words 和一个整数 k。
对于范围 [0, words.length - 1] 中的每个下标 i，在移除第 i 个元素后的剩余数组中，找到任意 k 个字符串（k 个下标 互不相同）的 最长公共前缀 的 长度。
返回一个数组 answer，其中 answer[i] 是 i 个元素的答案。如果移除第 i 个元素后，数组中的字符串少于 k 个，answer[i] 为 0。
一个字符串的 前缀 是一个从字符串的开头开始并延伸到字符串内任何位置的子字符串。
一个 子字符串 是字符串中一段连续的字符序列。
测试样例：
输入：words = ["dog","racer","car"], k = 2
输出：[0,0,0]
解释:
- 移除任何元素的结果都是 0。
解答：
- 问题转换：对于每次移除操作，我们需要在剩下的单词中找出任意 k 个单词，其最长公共前缀的长度最大。这意味着我们要预处理所有单词的前缀信息，并统计每个前缀出现的次数，从而确定在整体集合中哪些前缀可以被至少 k 个单词共享。
- 前缀哈希与排序：为了高效计算前缀，使用了滚动哈希（取模 mod = 10^9+7），并用一个数组存储每个单词当前前缀的哈希值。为了避免计算冗余，首先将所有单词的下标按照单词长度从小到大排序，这样在扩展前缀时，只需考虑长度足够的单词。
- 构造有效前缀集合 mem利用 while 循环，从前缀长度 0 开始逐层扩展，对于每个前缀长度：
- 更新所有长度足够单词的前缀哈希值；
- 统计每个前缀哈希值的出现次数；
- 只保留那些出现次数至少为 k 的前缀，并存入 mem 列表。 如果当前层级没有满足条件的前缀，则停止扩展。这样 mem 的大小即为在全局中存在的能够被 k 个或更多单词共享的最大前缀长度。
- 考虑移除单个单词的情况对于每个单词，若其长度不足 mem 的最大前缀长度，则移除该单词不会对剩下的前缀集合产生影响，答案直接为 mem.size()。否则，
- 计算该单词的所有前缀的哈希值；
- 通过二分查找，判断移除该单词后对公共前缀集合的影响，即找到哪一个前缀长度开始，剩余单词中共享该前缀的情况不再满足唯一且恰好 k 个单词的要求，从而得到答案。
- 整体思路总结： 该解法通过预处理全局有效前缀集合，再结合二分查找，快速判断移除每个单词后能获得的最长公共前缀长度。关键在于：
- 利用滚动哈希实现前缀快速计算；
- 通过排序和维护候选集合，减少无效计算；
- 使用二分查找针对每个移除操作高效确定答案。
这种方法兼顾了预处理的全局信息与针对局部变动（移除单词）的二分查找，能够高效解决题目要求。
class Solution {
// 模数，用于滚动哈希计算
private static final int mod = 1_000_000_007;
public int[] longestCommonPrefix(String[] words, int k) {
// sort 数组存储 words 的下标，并根据对应单词长度从小到大排序
Integer[] sort = new Integer[words.length];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (Integer.compare(words[a].length(), words[b].length())));
// pos 指向当前有效的最短单词下标位置，len 为当前考察的前缀长度
int pos = 0, len = 0;
// hash 数组保存每个单词的前缀哈希值（不断累积）
long[] hash = new long[words.length];
// mem 列表保存每个前缀长度下（从 len = 0 开始）的哈希值出现次数（只保留出现次数 >= k 的）
List<HashMap<Long, Integer>> mem = new ArrayList<>();
// 当剩余单词数（即长度足够的单词数）不少于 k 时继续迭代
while (words.length - pos >= k) {
// count 统计当前前缀位置上，各前缀哈希值的出现次数
HashMap<Long, Integer> count = new HashMap<>();
for (int i = pos; i < sort.length; ++i) {
int t = sort[i];
String w = words[t];
// 更新单词 t 的哈希值，扩展当前前缀
hash[t] = (hash[t] * 31 + w.charAt(len) - 'a') % mod;
count.put(hash[t], count.getOrDefault(hash[t], 0) + 1);
}
// 只保留出现次数大于等于 k 的前缀哈希值
HashMap<Long, Integer> result = new HashMap<>();
for (Map.Entry<Long, Integer> kv : count.entrySet()) {
if (kv.getValue() >= k) {
result.put(kv.getKey(), kv.getValue());
}
}
// 如果当前前缀长度下没有前缀被 k 个或更多单词共享，则退出循环
if (result.isEmpty()) {
break;
}
// 保存该前缀长度下的有效哈希集合
mem.add(result);
++len;
// 更新 pos：将那些长度不足 len+1 的单词移出候选范围
while (words.length - pos >= k && words[sort[pos]].length() <= len) {
++pos;
}
}
// 结果数组，res[i] 表示移除第 i 个单词后的答案
int[] res = new int[words.length];
for (int i = 0; i < words.length; ++i) {
// 如果当前单词长度不足 mem 的最大前缀长度，则答案直接为 mem.size()
if (words[i].length() < mem.size()) {
res[i] = mem.size();
} else {
// 计算当前单词的前缀哈希值数组
long[] prefix = new long[mem.size()];
long last = 0;
for (int j = 0; j < prefix.length; ++j) {
last = (last * 31 + words[i].charAt(j) - 'a') % mod;
prefix[j] = last;
}
// 二分查找：判断移除该单词后，在哪个前缀长度处会影响 k 个单词的公共前缀情况
int st = 0, ed = mem.size();
while (st < ed) {
int mid = (st + ed) / 2;
HashMap<Long, Integer> map = mem.get(mid);
// 如果当前前缀下：
// 1. 不止一种有效前缀（map.size() >= 2），
// 2. 或该单词的前缀不在有效前缀中，
// 3. 或该前缀的出现次数大于 k，
// 则说明移除该单词后，这个前缀不会成为唯一且恰好 k 个单词的公共前缀
if (map.size() >= 2 || !map.containsKey(prefix[mid]) || map.get(prefix[mid]) > k) {
st = mid + 1;
} else {
ed = mid;
}
}
res[i] = st;
}
}
return res;
}
}100606. Longest Special Path II
给你一棵无向树，根节点为 0，树有 n 个节点，节点编号从 0 到 n - 1。这个树由一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和 vi 之间有一条长度为 lengthi 的边。同时给你一个整数数组 nums，其中 nums[i] 表示节点 i 的值。
一条 特殊路径 定义为一个从祖先节点到子孙节点的 向下 路径，路径中所有节点值都是唯一的，最多允许有一个值出现两次。
返回一个大小为 2 的数组 result，其中 result[0] 是 最长 特殊路径的 长度 ，result[1] 是所有 最长 特殊路径中的 最少 节点数。
测试样例：
输入：edges = [[0,1,1],[1,2,3],[1,3,1],[2,4,6],[4,7,2],[3,5,2],[3,6,5],[6,8,3]], nums = [1,1,0,3,1,2,1,1,0]
输出：[9，3]
解释: 最长的特殊路径是 1 -> 2 -> 4 和 1 -> 3 -> 6 -> 8，两者的长度都是 9。所有最长特殊路径中最小的节点数是 3 。
解答：
- 深度优先搜索 (DFS)：利用 DFS 遍历整棵树，同时记录从根节点到当前节点的路径信息。
- 滑动窗口维护特殊路径条件：
- 使用一个数组
path保存 DFS 路径上经过的节点值。 - 使用
freq数组统计当前窗口（连续子路径）中各个节点值的出现频率。 - 使用
dupCount记录当前窗口中出现次数正好为 2 的不同数值的个数，保证最多只允许一个数重复。 - 利用
windowLeft指针动态维护一个有效的窗口，使得窗口内的节点值满足“所有值唯一，最多有一个重复”的条件。
- 使用一个数组
- 路径长度和节点数的计算：
- 使用
cumSum数组记录从根节点到当前节点的累计边权和，窗口内路径长度为curSum - cumSum[windowLeft]。 - 当前窗口节点数为
depth - windowLeft + 1。 - 在 DFS 过程中不断更新全局变量
bestLength和bestCount，保存最长特殊路径及对应的最小节点数。
- 使用
- 状态回溯：
每次 DFS 递归结束后，通过回溯恢复freq、dupCount以及windowLeft的状态，保证其他分支的 DFS 能够在正确的状态下运行。 - 总结：该解法巧妙结合 DFS 与滑动窗口的思想，在遍历树的过程中维护一段满足特殊路径条件的连续路径，并通过累计边权和计算路径长度，同时记录符合条件的最优答案。关键在于：
- 动态维护和调整当前路径的状态，
- 通过滑动窗口确保路径内节点值最多只有一个重复，
- 利用回溯正确恢复状态以遍历所有可能的路径。
class Solution {
// path：记录当前 DFS 路径上每个节点的值
int[] path;
// cumSum：记录从根节点到当前节点的累计边权和，用于计算路径长度
int[] cumSum;
// freq：统计当前窗口中各个数值出现的频率（节点值范围 0 ~ 50000）
int[] freq;
// windowLeft：当前滑动窗口的左边界索引，表示有效特殊路径的起始位置
int windowLeft;
// dupCount：记录当前窗口中出现次数正好为 2 的不同数值的个数（允许最多一个重复）
int dupCount;
// bestLength：全局最长特殊路径的长度（边权和）
int bestLength;
// bestCount：在所有最长特殊路径中节点数最少的那一条路径的节点数
int bestCount;
// graph：用邻接表表示树，每个元素存储一个 [child, weight] 数组
List<int[]>[] graph;
// nums：每个节点的值
int[] nums;
// n：节点总数
int n;
public int[] longestSpecialPath(int[][] edges, int[] nums) {
// 初始化节点数量和节点值数组
this.n = nums.length;
this.nums = nums;
// 初始化邻接表表示
graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
// 构建无向树
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
graph[u].add(new int[]{v, w});
graph[v].add(new int[]{u, w});
}
// 初始化 DFS 路径数组和累计边权和数组
path = new int[n];
cumSum = new int[n];
// 初始化频率数组（节点值范围 0 ~ 50000）
freq = new int[50001];
windowLeft = 0;
dupCount = 0;
bestLength = 0;
bestCount = Integer.MAX_VALUE;
// 将根节点加入 DFS 路径
path[0] = nums[0];
cumSum[0] = 0;
freq[nums[0]]++;
// 从根节点开始 DFS，初始 parent 设为 -1，当前累计边权为 0，深度为 0
dfs(0, -1, 0, 0);
// 返回结果：最长特殊路径的长度和所有最长特殊路径中节点数最少的那一条的节点数
return new int[]{bestLength, bestCount};
}
// DFS 函数，node 当前节点，parent 父节点，curSum 当前累计边权和，depth DFS 当前深度
void dfs(int node, int parent, int curSum, int depth) {
// 当前有效窗口 [windowLeft, depth] 对应的路径长度为：
// 当前累计边权 curSum 减去窗口起始位置的累计边权 cumSum[windowLeft]
int currentLength = curSum - cumSum[windowLeft];
// 当前窗口中的节点数
int nodesCount = depth - windowLeft + 1;
// 更新全局答案：若当前路径更长，或相等时节点数更少
if (currentLength > bestLength) {
bestLength = currentLength;
bestCount = nodesCount;
} else if (currentLength == bestLength && nodesCount < bestCount) {
bestCount = nodesCount;
}
// 遍历当前节点的所有相邻节点
for (int[] edge : graph[node]) {
int child = edge[0], weight = edge[1];
// 避免返回父节点
if (child == parent) continue;
// 计算从当前节点到子节点的新累计边权
int newSum = curSum + weight;
// 保存当前 windowLeft 以便回溯时恢复状态
int oldWindowLeft = windowLeft;
// 记录本次 DFS 调用中滑动窗口向右移动的步数
int removedCount = 0;
// 子节点在 DFS 路径中的深度
int newDepth = depth + 1;
// 将子节点的值添加到 DFS 路径
path[newDepth] = nums[child];
// 记录子节点处的累计边权
cumSum[newDepth] = newSum;
int val = nums[child];
// 更新子节点值的出现频率
freq[val]++;
// 如果该值出现次数刚好变为 2，重复计数加一
if (freq[val] == 2) {
dupCount++;
}
// 当窗口不满足特殊路径要求时调整窗口：
// 条件：当前子节点值出现次数超过 2 或窗口中重复值种类超过 1
while (freq[val] > 2 || dupCount > 1) {
// 移除窗口最左侧的节点
int remVal = path[windowLeft];
// 如果移除后该值的频率从 2 降为 1，则重复计数减一
if (freq[remVal] == 2) {
dupCount--;
}
freq[remVal]--;
windowLeft++;
removedCount++;
}
// 递归访问子节点
dfs(child, node, newSum, newDepth);
// 回溯：撤销对子节点值的影响
if (freq[val] == 2) {
dupCount--;
}
freq[val]--;
// 恢复之前被滑动窗口移除的节点状态
for (int i = oldWindowLeft; i < oldWindowLeft + removedCount; i++) {
int restoreVal = path[i];
if (freq[restoreVal] == 1) {
dupCount++;
}
freq[restoreVal]++;
}
// 恢复窗口左边界到原来的位置
windowLeft = oldWindowLeft;
}
}
}