欢迎大家加QQ群：623375442。最后一道题目强行优化过了，之后看看有啥更好的解答。
100529. Find the Most Common Response
给你一个二维字符串数组 responses，其中每个 responses[i] 是一个字符串数组，表示第 i 天调查的回答结果。
请返回在对每个 responses[i] 中的回答 去重 后，所有天数中 最常见 的回答。如果有多个回答出现频率相同，则返回 字典序最小 的那个回答。
一个字符串 a 在字典序上 小于 另一个字符串 b 的条件是：在第一个不相同的位置上，a 中的字母比 b 中对应的字母在字母表中靠前。
如果前 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。
测试样例：
输入：responses = [["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]
输出："good"
解释：
- 每个列表去重后，得到 responses = [["good", "ok"], ["ok", "bad", "good"], ["good"], ["bad"]]。
- "good" 出现了 3 次，"ok" 出现了 2 次，"bad" 也出现了 2 次。
- 返回 "good"，因为它出现的频率最高。
解答：
- 对每一天的回答列表去重，保证同一天内同一回答只计数一次。
- 使用哈希表 map 记录每种回答出现的天数。遍历去重后的每一天的回答集合，将对应回答的计数加一。
- 最后遍历 map，找到出现次数最多的回答；如果有多个，选择字典序最小的
class Solution {
public String findCommonResponse(List<List<String>> responses) {
// 用于统计每个回答出现的去重后天数
HashMap<String, Integer> map = new HashMap<>();
// 遍历每一天的回答
for (List<String> row : responses) {
// set 用于去重同一天内的重复回答
Set<String> set = new HashSet<>();
for (String str : row) {
// 如果今天还没计入过该回答，则加入 set 并在 map 中计数
if (!set.contains(str)) {
set.add(str);
map.put(str, map.getOrDefault(str, 0) + 1);
}
}
}
// 用于记录最终答案及其出现次数
String res = null;
int count = 0;
// 遍历 map 中的每种回答
for (Map.Entry<String, Integer> kv : map.entrySet()) {
String key = kv.getKey();
int val = kv.getValue();
// 若出现次数更多，则更新答案
if (val > count) {
count = val;
res = key;
} else if (val == count) {
// 出现次数相同时，取字典序更小的
if (res.compareTo(key) > 0) {
res = key;
}
}
}
return res;
}
}100546. Unit Conversion I
有 n 种单位，编号从 0 到 n - 1。给你一个二维整数数组 conversions，长度为 n - 1，其中 conversions[i] = [sourceUniti, targetUniti, conversionFactori] ，表示一个 sourceUniti 类型的单位等于 conversionFactori 个 targetUniti 类型的单位。
请你返回一个长度为 n 的数组 baseUnitConversion，其中 baseUnitConversion[i] 表示 一个 0 类型单位等于多少个 i 类型单位。由于结果可能很大，请返回每个 baseUnitConversion[i] 对 109 + 7 取模后的值。
测试样例：
输入：conversions = [[0,1,2],[1,2,3]]
输出：[1,2,6]
解释:
- 使用 conversions[0]：将一个 0 类型单位转换为 2 个 1 类型单位。
- 使用 conversions[0] 和 conversions[1] 将一个 0 类型单位转换为 6 个 2 类型单位。
解答：
- 给定 n-1 条转换关系，构造一个有向树（或森林），根节点为单位 0。
- 从单位 0 开始深度优先搜索（DFS），维护一个累乘因子 mul，表示当前节点单位与 0 单位的转换结果。
- 在 DFS 到达每个节点时，将 mul 取模后存入结果数组 res。
- 递归地将转换因子乘到下一层节点。
class Solution {
private static final int mod = 1_000_000_007; // 模数
public int[] baseUnitConversions(int[][] conversions) {
int n = conversions.length + 1; // 单位总数
int[] res = new int[n]; // 存放结果
// 构造邻接表，edges[i] 存储从 i 单位出发的所有转换
List<int[]>[] edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
// 填充转换关系
for (int[] conv : conversions) {
// conv = [sourceUnit, targetUnit, factor]
edges[conv[0]].add(conv);
}
// 从单位 0 开始 DFS，初始乘积为 1
dfs(0, 1, res, edges);
return res;
}
/**
* @param pos 当前单位编号
* @param mul 目前累积的转换因子（mod 取模后传递）
* @param res 结果数组
* @param conversions 邻接表
*/
private void dfs(int pos, long mul, int[] res, List<int[]>[] conversions) {
// 将当前单位对应的转换结果记录下来
res[pos] = (int) (mul % mod);
// 遍历所有从 pos 单位出发的转换
for (int[] conv : conversions[pos]) {
int nextUnit = conv[1];
int factor = conv[2];
// 递归，更新累积乘积并取模
dfs(nextUnit, mul * factor % mod, res, conversions);
}
}
}100625. Count Cells in Overlapping Horizontal and Vertical Substrings
给你一个由字符组成的 m x n 矩阵 grid 和一个字符串 pattern。
水平子串 是从左到右的一段连续字符序列。如果子串到达了某行的末尾，它将换行并从下一行的第一个字符继续。不会 从最后一行回到第一行。
垂直子串 是从上到下的一段连续字符序列。如果子串到达了某列的底部，它将换列并从下一列的第一个字符继续。不会 从最后一列回到第一列。
请统计矩阵中满足以下条件的单元格数量：
- 该单元格必须属于 至少 一个等于 pattern 的水平子串，且属于 至少 一个等于 pattern 的垂直子串。
返回满足条件的单元格数量。
测试样例：
输入：grid = [["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","c","c"]], pattern = "abaca"
输出：1
解释: "abaca" 作为一个水平子串（蓝色）和一个垂直子串（红色）各出现一次，并在一个单元格（紫色）处相交。
解答：
- 利用 KMP 算法在 "展开" 后的水平串和垂直串上分别搜索模式串 pattern，记录每次匹配结束时的全局下标。
- 对于水平串：先扫一遍记录所有匹配结束位置，然后再根据这些位置标记每个字符是否在某次匹配范围内。
- 对于垂直串：同理记录匹配结束位置，同时在第二轮遍历时，若该字符已被水平标记且也在垂直匹配范围内，则计数。
- 最终返回满足两种匹配都覆盖的单元格数量。
class Solution {
public int countCells(char[][] grid, String pattern) {
int m = grid.length, n = grid[0].length;
// 先构建 KMP 的失配表
int[] fail = kmp(pattern);
// horizon[i][j] 表示 (i,j) 在某次水平匹配中被覆盖
boolean[][] horizon = new boolean[m][n];
// ---- 水平匹配 ----
{
TreeSet<Integer> set = new TreeSet<>(); // 存放所有匹配结束的全局索引
int match = -1, count = 0;
// 第一遍：扫描所有字符，计算匹配结束位置
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// KMP 经典失配处理
while (match != -1 && pattern.charAt(match + 1) != grid[i][j]) {
match = fail[match];
}
if (pattern.charAt(match + 1) == grid[i][j]) {
++match;
// 整个模式串匹配完成
if (match == pattern.length() - 1) {
set.add(count);
match = fail[match];
}
}
++count;
}
}
if (set.isEmpty()) return 0;
// 第二遍：根据每次结束位置向前标记 pattern.length() 个字符
count = 0;
Integer nextEnd = set.first();
outer:
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前索引超过本次结束位置，则取下一个结束位置
if (count > nextEnd) {
nextEnd = set.higher(nextEnd);
if (nextEnd == null) break outer;
}
// 若当前字符在 [end - len + 1, end] 范围内，则标记
if (nextEnd - count < pattern.length()) {
horizon[i][j] = true;
}
++count;
}
}
}
// ---- 垂直匹配 & 交叉计数 ----
int res = 0;
{
TreeSet<Integer> set = new TreeSet<>();
int match = -1, count = 0;
// 第一遍：按列展开，记录所有匹配结束位置
for (int j = 0; j < grid[0].length; ++j) {
for (int i = 0; i < grid.length; ++i) {
while (match != -1 && pattern.charAt(match + 1) != grid[i][j]) {
match = fail[match];
}
if (pattern.charAt(match + 1) == grid[i][j]) {
++match;
if (match == pattern.length() - 1) {
set.add(count);
match = fail[match];
}
}
++count;
}
}
if (set.isEmpty()) return 0;
// 第二遍：同样标记，并在水平已标记的格子中统计交集
count = 0;
Integer nextEnd = set.first();
outer2:
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m; ++i) {
if (count > nextEnd) {
nextEnd = set.higher(nextEnd);
if (nextEnd == null) break outer2;
}
// 当该格既在水平匹配范围又在垂直匹配范围时计数
if (horizon[i][j] && nextEnd - count < pattern.length()) {
++res;
}
++count;
}
}
}
return res;
}
// 构建 KMP 失配表，长度为 pattern.length()
private int[] kmp(String pattern) {
int len = pattern.length();
int[] fail = new int[len];
Arrays.fill(fail, -1);
int j = -1;
for (int i = 1; i < len; ++i) {
while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
j = fail[j];
}
if (pattern.charAt(j + 1) == pattern.charAt(i)) {
++j;
}
fail[i] = j;
}
return fail;
}
}100630. Maximum Profit from Valid Topological Order in DAG
给你一个由 n 个节点组成的有向无环图（DAG），节点编号从 0 到 n - 1，通过二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示一条从节点 ui 指向节点 vi 的有向边。每个节点都有一个对应的 得分 ，由数组 score 给出，其中 score[i] 表示节点 i 的得分。
你需要以 有效的拓扑排序 顺序处理这些节点。每个节点在处理顺序中被分配一个编号从 1 开始的位置。
将每个节点的得分乘以其在拓扑排序中的位置，然后求和，得到的值称为 利润。
请返回在所有合法拓扑排序中可获得的 最大利润 。
拓扑排序 是一个对 DAG 中所有节点的线性排序，使得每条有向边 u → v 中，节点 u 都出现在 v 之前。
测试样例：
输入：n = 2, edges = [[0,1]], score = [2,3]
输出：8
解释: 节点 1 依赖于节点 0，因此一个合法顺序是 [0, 1]。所有合法拓扑排序中可获得的最大总利润是 2 + 6 = 8。
解答：
- 将 DAG 转为位掩码状态 pos，长度为 n 个比特，表示哪些节点已被放置。
- 用记忆化 DFS 枚举所有拓扑序：在当前状态 pos，遍历所有尚未使用且其所有前驱节点都已使用的节点 i，尝试将其放到下一个位置。
- 当前深度 depth 表示下一放置节点的位置，将贡献 depth * score[i] 加入递归结果。
- 用 dp[pos] 缓存状态的最大利润。
class Solution {
public int maxProfit(int n, int[][] _edges, int[] score) {
// edgesMask[i] 的二进制表示：第 k 位为 1 表示存在 k->i 的边
int[] edgesMask = new int[n];
for (int[] e : _edges) {
int u = e[0], v = e[1];
edgesMask[v] |= (1 << u);
}
int maxState = 1 << n; // 状态总数
Integer[] dp = new Integer[maxState]; // 记忆化表
// 从空状态开始，深度（位置）为 1
return dfs(0, dp, edgesMask, score, 1);
}
/**
* @param pos 二进制状态，表示哪些节点已放置
* @param dp 记忆化缓存
* @param edgesMask 前驱掩码数组
* @param score 节点分数数组
* @param depth 当前节点放置位置（1 开始）
*/
private int dfs(int pos, Integer[] dp, int[] edgesMask, int[] score, int depth) {
int n = edgesMask.length;
// 若所有节点均已放置，则没有剩余利润
if (pos == (1 << n) - 1) {
return 0;
}
if (dp[pos] != null) {
return dp[pos];
}
int res = 0;
// 遍历所有节点，尝试放下一个节点
for (int i = 0; i < n; ++i) {
// 若节点 i 未被使用，且其所有前驱都已在 pos 中
if (((pos >> i) & 1) == 0 && (pos & edgesMask[i]) == edgesMask[i]) {
// 放置 i 节点，累加利润 depth*score[i]
int profit = depth * score[i] + dfs(pos | (1 << i), dp, edgesMask, score, depth + 1);
res = Math.max(res, profit);
}
}
dp[pos] = res;
return res;
}
}