求解思路
首先，我们需要提取每个序列的特征，即计算相邻元素的差分数组。
为了方便存储和查找，将这些差分数值转换为字符串格式，并在每个数值后添加特殊分隔符（如 #）以区分多位数（防止 1, 2 和 12 混淆），同时处理负号。
接着，构建一个静态数组实现的字典树（Trie），将 a 数组中所有序列生成的差分字符串插入树中，利用 Trie 节点的 pass 计数功能记录每种差分模式出现的次数。
最后，遍历查询数组 b，以同样的方式生成差分字符串并在 Trie 中进行检索，检索路径终点的 pass 值即为该模式在 a 中出现的总次数。
完整实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
import java.util.Arrays;
public class Solution {
// 统计 b 中每个序列在 a 中有多少个“一致”的序列
public static int[] countConsistentKeys(int[][] b, int[][] a) {
// 初始化静态空间
build();
StringBuilder builder = new StringBuilder();
// 将每个序列转换为差分字符串并在 Trie 中注册
for (int[] nums : a) {
builder.setLength(0);
// 计算相邻元素的差值
for (int i = 1; i < nums.length; i++) {
// 使用 # 作为分隔符，防止数字粘连（如 1,2 变成 12）
builder.append(String.valueOf(nums[i] - nums[i - 1]) + "#");
}
insert(builder.toString());
}
int[] ans = new int[b.length];
// 生成差分字符串并在 Trie 中查询计数
for (int i = 0; i < b.length; i++) {
builder.setLength(0);
int[] nums = b[i];
for (int j = 1; j < nums.length; j++) {
builder.append(String.valueOf(nums[j] - nums[j - 1]) + "#");
}
// count 方法返回该路径（模式）被经过的次数
ans[i] = count(builder.toString());
}
// 清理静态内存，防止污染下一次调用
clear();
return ans;
}
// 根据题目数据范围预估的最大节点数
public static int MAXN = 2000001;
// tree[i][j] 表示节点 i 经过字符 j 指向的下一个节点索引
// 字符集大小为 12：包含 0-9 十个数字，以及 '#' 和 '-'
public static int[][] tree = new int[MAXN][12];
// pass[i] 记录经过节点 i 的字符串数量
public static int[] pass = new int[MAXN];
// 当前使用的节点计数器
public static int cnt;
// 初始化 Trie
public static void build() {
cnt = 1; // 1 号点作为根节点
}
// 将字符映射到 tree 数组的列索引 0~11
public static int path(char cha) {
if (cha == '#') {
return 10; // '#' 映射为 10
} else if (cha == '-') {
return 11; // '-' 映射为 11
} else {
return cha - '0'; // '0'~'9' 映射为 0~9
}
}
// 插入字符串到 Trie
public static void insert(String word) {
int cur = 1; // 从根节点开始
pass[cur]++; // 根节点计数+1
for (int i = 0, path; i < word.length(); i++) {
path = path(word.charAt(i));
// 如果当前路径不存在，分配新节点
if (tree[cur][path] == 0) {
tree[cur][path] = ++cnt;
}
cur = tree[cur][path];
pass[cur]++; // 沿途节点计数+1
}
}
// 利用 pass 数组，返回完全匹配该前缀（即整个差分串）的次数
public static int count(String pre) {
int cur = 1;
for (int i = 0, path; i < pre.length(); i++) {
path = path(pre.charAt(i));
// 如果路径断了，说明该模式从未出现过
if (tree[cur][path] == 0) {
return 0;
}
cur = tree[cur][path];
}
// 返回终点的 pass 值，即为该模式的总出现次数
return pass[cur];
}
// 清空静态数组，服务于多测试用例场景
public static void clear() {
for (int i = 1; i <= cnt; i++) {
Arrays.fill(tree[i], 0);
pass[i] = 0;
}
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~