Algorithm
lc1948_删除系统中的重复文件夹
思路:
每个节点都由所有的子路径树编码成一串字符串，如果发现两个节点的编码相同，则可以删除这个编码。
编码可以由map+set/sorted_vec实现，map的key是编码，value是节点，set/sorted_vec的value是节点。
编码的生成方式:
- 从根节点开始，遍历所有子节点，将子节点的编码拼接起来，形成一个编码。
- 如果发现两个节点的编码相同，则可以删除这个编码。
- 如果发现两个节点的编码不同，则可以保留这个编码。
代码实现:
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
|
use std::collections::{HashMap, HashSet};
#[derive(Debug)]
struct TreeNode {
name: String,
children: HashMap<String, TreeNode>,
}
impl Solution {
pub fn delete_duplicate_folder(paths: Vec<Vec<String>>) -> Vec<Vec<String>> {
// 构建树结构
let mut root = TreeNode {
name: "".to_string(),
children: HashMap::new(),
};
for path in paths {
let mut current = &mut root;
for folder in path {
current.children.entry(folder.clone()).or_insert_with(|| TreeNode {
name: folder.clone(),
children: HashMap::new(),
});
current = current.children.get_mut(&folder).unwrap();
}
}
// 用于存储编码到节点的映射
let mut encoding_map: HashMap<String, Vec<*mut TreeNode>> = HashMap::new();
// 生成编码并收集重复节点
Self::generate_encoding(&mut root, &mut encoding_map);
// 标记需要删除的节点
let mut to_delete: HashSet<*mut TreeNode> = HashSet::new();
for (encoding, nodes) in encoding_map {
if nodes.len() > 1 && !encoding.is_empty() {
// 有重复的编码且编码非空，标记所有节点为删除
for node_ptr in nodes {
to_delete.insert(node_ptr);
}
}
}
// 收集结果
let mut result = Vec::new();
Self::collect_paths(&root, &to_delete, &mut Vec::new(), &mut result);
result
}
fn generate_encoding(node: &mut TreeNode, encoding_map: &mut HashMap<String, Vec<*mut TreeNode>>) -> String {
if node.children.is_empty() {
return "".to_string();
}
// 收集所有子节点的编码，包含子节点名字
let mut child_encodings = Vec::new();
for child in node.children.values_mut() {
let child_encoding = Self::generate_encoding(child, encoding_map);
// child_encodings.push(format!("({})", child_encoding));
child_encodings.push(format!("{}({})", child.name, child_encoding));
}
// 排序确保相同结构的编码一致
child_encodings.sort();
// 生成当前节点的编码
let encoding = child_encodings.join("");
// 将编码和节点指针存储到映射中
encoding_map.entry(encoding.clone()).or_insert_with(Vec::new).push(node as *mut TreeNode);
encoding
}
fn collect_paths(
node: &TreeNode,
to_delete: &HashSet<*mut TreeNode>,
current_path: &mut Vec<String>,
result: &mut Vec<Vec<String>>
) {
// 如果当前节点被标记为删除，不收集路径
if to_delete.contains(&(node as *const TreeNode as *mut TreeNode)) {
return;
}
// 如果有路径且不是根节点，添加到结果中
if !current_path.is_empty() {
result.push(current_path.clone());
}
// 递归处理子节点
for child in node.children.values() {
current_path.push(child.name.clone());
Self::collect_paths(child, to_delete, current_path, result);
current_path.pop();
}
}
}
|
这个实现的关键点：
- 树结构构建：将输入的路径列表构建成树结构，每个节点包含名称和子节点映射。
- 编码生成：递归地为每个节点生成编码，编码由所有子节点的编码组成，并按照字典序排序确保相同结构的编码一致。
- 重复检测：使用HashMap存储编码到节点指针的映射，如果某个编码对应多个节点，说明存在重复结构。
- 路径收集：遍历树结构，收集所有未被标记为删除的节点的路径。
- 内存安全：使用原始指针来标识节点，但要注意在Rust中需要确保指针的有效性。
这个算法的时间复杂度是O(n * m)，其中n是路径数量，m是平均路径长度。空间复杂度是O(n * m)。
题解:
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
|
use std::collections::HashMap;
#[derive(Default)]
struct Trie {
serial: String, // 当前节点结构的序列化表示
children: HashMap<String, Trie>, // 当前节点的子节点
}
impl Solution {
pub fn delete_duplicate_folder(paths: Vec<Vec<String>>) -> Vec<Vec<String>> {
let mut root = Trie::default(); // 根节点
// 构建字典树
for path in paths {
let mut cur = &mut root;
for node in path {
cur = cur.children.entry(node.clone()).or_default();
}
}
let mut freq = HashMap::new(); // 哈希表记录每一种序列化表示的出现次数
// 基于深度优先搜索的后序遍历，计算每一个节点结构的序列化表示
fn construct(node: &mut Trie, freq: &mut HashMap<String, usize>) {
if node.children.is_empty() {
return; // 如果是叶节点，无需操作
}
let mut v = Vec::new();
for (folder, child) in node.children.iter_mut() {
construct(child, freq);
v.push(format!("{}({})", folder, child.serial));
}
v.sort();
node.serial = v.join("");
*freq.entry(node.serial.clone()).or_default() += 1;
}
construct(&mut root, &mut freq);
let mut ans = Vec::new();
let mut path = Vec::new();
// 操作字典树，删除重复文件夹
fn operate(node: &Trie, freq: &HashMap<String, usize>, path: &mut Vec<String>, ans: &mut Vec<Vec<String>>) {
if freq.get(&node.serial).unwrap_or(&0) > &1 {
return; // 如果序列化表示出现超过1次，需要删除
}
if !path.is_empty() {
ans.push(path.clone());
}
for (folder, child) in &node.children {
path.push(folder.clone());
operate(child, freq, path, ans);
path.pop();
}
}
operate(&root, &freq, &mut path, &mut ans);
ans
}
}
|
编码错误卡很久
分析测试用例：
- 输入：
[["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
- 预期输出：
[["d"],["d","a"]]
分析编码过程：
["a","b"] 和 ["c","b"] 都是叶子节点，编码为空字符串["a"] 有子节点 ["b"]，编码是 "()"（因为 ["b"] 的编码是空字符串）["c"] 有子节点 ["b"]，编码也是 "()"["d","a"] 是叶子节点，编码为空字符串["d"] 有子节点 ["a"]，编码是 "()"（因为 ["a"] 的编码是空字符串）
所以 ["a"]、["c"]、["d"] 的编码都是 "()"，它们被认为是重复的，都被删除了。
但是预期输出是 [["d"],["d","a"]]，说明 ["d"] 应该保留。
问题在于：编码方式没有区分不同名字的子节点！
编码是：
1
|
child_encodings.push(format!("({})", child_encoding));
|
这样 ["a"] 和 ["c"] 的编码都是 "()"，因为它们的子节点 ["b"] 的编码都是空字符串。
但是 ["d"] 的子节点是 ["a"]，["a"] 的编码是 "()"，所以 ["d"] 的编码也是 "()"。
正确的编码应该包含子节点的名字：
1
|
child_encodings.push(format!("{}({})", child.name, child_encoding));
|
这样：
["a"] 的编码是 "b()"（子节点名字是 “b”，编码是空字符串）["c"] 的编码是 "b()"（子节点名字是 “b”，编码是空字符串）["d"] 的编码是 "a()"（子节点名字是 “a”，编码是空字符串）
这样 ["a"] 和 ["c"] 的编码相同，会被删除，而 ["d"] 的编码不同，会被保留。
总结：编码方式缺少了子节点的名字信息，导致不同名字但结构相同的子树被误认为是相同的。
Review
【TED演讲】当计算机变得比我们更聪明时会发生什么
AI很强大，未来可能会强大到失控，所以应该提前让AI学习道德约束，控制好很多控制性问题，防止AI失控后毁灭人类。
Tips
链上皇0xSun推荐的币圈新闻推特
币圈相关新闻推特，最主流和权威的，
英文源DB @tier10k 和Tree @TreeNewsFeed ，
中文源方程式 @bwenews ，
虽然他们有时候也会出错，但是大新闻99%是这几家最先推送。
Share
Claude Code 的常见工作流程
实践证明: 学习 Claude 的常见工作流程，就算不用 Claude Code, 只 Cursor 调用 Claude 的 API 也可以使得使用效果大幅提升。