【华为OD机试|02】音乐小说内容重复识别（Java/C/Py/JS）
目录
一、题目介绍
1.1 题目描述
1.2 输入描述
1.3 输出描述
1.4 用例
二、题目解析
2.1 题目分析
2.2 实现思路
三、Java实现
3.1 详细代码
3.2 代码解析
四、C#实现
4.1 详细代码
4.2 代码解析
五、Python实现
5.1 完整代码
5.2 代码解析
六、JS实现
6.1 完整代码
6.2 代码解析
七、总结
一、题目介绍
1.1 题目描述
实现一个简易的重复内容识别系统，通过给定的两个内容名称，和相似内容符号，判断两个内容是否相似；如果相似，返回相似内容；如果不相似，返回不相似的内容。
初始化：给出两个字符串，一些相似字符对，如顿号和逗号相似，的和de相似，猪和潴，给出两个字符串的相似判断结果
输入：两条语句，给出是否相似，对于相似的语句，返回True和相似的字符对；对于不相似的内容，则返回第一个内容的不相似信息，方便后续补充
注意：
- 相似关系是 具有 传递性的。例如，如果"顿号"和"逗号"是相似的，"逗号"和"分号"是相似的，则"顿号"和"逗号"是相似的。
- 为了过滤一些无意义的信息，这里***可以匹配任意长度的内容，例如：
给出相似对"(****)",""时，"异世邪君（人气玄幻作家）" 和 "异世邪君" 认为是相似，此时相似符号返回 *** 即可
- 不相似的内容，需要给出不相似的字符串，多处不相似的字符串用空格分隔
1.2 输入描述
- 第一行表示第一张专辑的专辑名，其中 0
- 第二行表示第二张专辑的专辑名，其中 0
- 第三行开始每行为相似的字符串，每行一组，每组字符串不超过10个
- 总共相似字符串行不超过10行
1.3 输出描述
- 第一行返回相似判断的结果，即True或者False
- 第二行开始返回相似/不相似的字符串，每行一组
1.4 用例
输入 林汉达上下五千年 林汉达上下5千年
五 5 ⑤ 伍 wu
输出 True 五 5
说明 无 输入 幸福de猪的个人专辑 幸福的猪的个人专辑
得 的
得 de
输出 True de 的
说明 无 输入 异世邪君(人气玄幻作家) 异世邪君
(***)
输出 True
(***)
说明 无 输入 浩然爸爸讲成语 浩然爸爸讲论语
论语 三字经
输出 False 成语 论语
说明 无 二、题目解析
2.1 题目分析
这个题目主要考察以下几个算法和数据结构的知识：
-
字符串匹配和替换：
- 在判断两个字符串是否相似时，需要能够快速匹配和替换字符串中的相似字符对。
-
并查集（Union-Find）算法：
- 由于相似关系是传递性的，可以用并查集算法来处理这种相似关系，方便快速查找和合并相似字符的集合。
-
哈希表：
- 使用哈希表存储相似字符对，方便快速查找和匹配。
2.2 实现思路
- 读取输入：包括两个专辑名和相似字符对。
- 构建并查集：用并查集来处理相似字符对，构建每个字符的相似集合。
- 字符串归一化：根据并查集，将两个专辑名归一化，即将所有相似字符替换成它们的代表字符。
- 比较归一化后的字符串：判断归一化后的字符串是否相同。如果相同，返回 True 和相似字符对；否则，返回 False 和第一个专辑名中不相似的信息。
三、Java实现
3.1 详细代码
import java.util.*; public class SimilarContentChecker { private static class UnionFind { private Map parent; public UnionFind() { parent = new HashMap(); } public String find(String x) { if (!parent.containsKey(x)) { parent.put(x, x); } if (!x.equals(parent.get(x))) { parent.put(x, find(parent.get(x))); } return parent.get(x); } public void union(String x, String y) { String rootX = find(x); String rootY = find(y); if (!rootX.equals(rootY)) { parent.put(rootX, rootY); } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取输入 String album1 = scanner.nextLine(); String album2 = scanner.nextLine(); List similarPairs = new ArrayList(); while (scanner.hasNextLine()) { String line = scanner.nextLine(); if (line.isEmpty()) break; similarPairs.add(line.split(",")); } // 构建并查集 UnionFind uf = new UnionFind(); for (String[] pair : similarPairs) { for (int i = 0; i3.2 代码解析
详细讲解代码实现步骤
-
并查集（Union-Find）类：
- UnionFind 类用于处理字符的相似关系。find 方法用于查找字符的根代表，union 方法用于合并两个字符的相似集合。
-
读取输入：
- 使用 Scanner 读取两个专辑名和相似字符对。
- 将相似字符对存储在 similarPairs 列表中。
-
构建并查集：
- 对于每一对相似字符对，调用 union 方法将它们合并到同一个集合中。
-
字符串归一化：
- 遍历专辑名中的每一个字符，使用 find 方法将其归一化为相似集合的代表字符。
-
比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出 True 和相似字符对；否则，输出 False 和第一个专辑名中不相似的信息。
这种方法使用了并查集来高效处理相似关系，并使用哈希表进行字符查找和归一化处理，确保了算法的高效性和准确性。
四、C#实现
4.1 详细代码
using System; using System.Collections.Generic; public class SimilarContentChecker { private class UnionFind { private Dictionary parent; public UnionFind() { parent = new Dictionary(); } public string Find(string x) { if (!parent.ContainsKey(x)) { parent[x] = x; } if (x != parent[x]) { parent[x] = Find(parent[x]); } return parent[x]; } public void Union(string x, string y) { string rootX = Find(x); string rootY = Find(y); if (rootX != rootY) { parent[rootX] = rootY; } } } public static void Main(string[] args) { string album1 = Console.ReadLine(); string album2 = Console.ReadLine(); List similarPairs = new List(); string line; while (!string.IsNullOrEmpty(line = Console.ReadLine())) { similarPairs.Add(line.Split(',')); } UnionFind uf = new UnionFind(); foreach (var pair in similarPairs) { for (int i = 0; i4.2 代码解析
详细讲解代码实现步骤
-
并查集（Union-Find）类：
- UnionFind 类用于处理字符的相似关系。Find 方法用于查找字符的根代表，Union 方法用于合并两个字符的相似集合。
-
读取输入：
- 使用 Console.ReadLine() 读取两个专辑名和相似字符对。
- 将相似字符对存储在 similarPairs 列表中。
-
构建并查集：
- 对于每一对相似字符对，调用 Union 方法将它们合并到同一个集合中。
-
字符串归一化：
- 遍历专辑名中的每一个字符，使用 Find 方法将其归一化为相似集合的代表字符。
-
比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出 True 和相似字符对；否则，输出 False 和第一个专辑名中不相似的信息。
五、Python实现
5.1 完整代码
class UnionFind: def __init__(self): self.parent = {} def find(self, x): if x not in self.parent: self.parent[x] = x if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.parent[rootX] = rootY def normalize_string(s, uf): normalized = [] for char in s: normalized.append(uf.find(char)) return ''.join(normalized) def get_differences(original, normalized1, normalized2): differences = [] for o, n1, n2 in zip(original, normalized1, normalized2): if n1 != n2: differences.append(o) return ' '.join(differences) def main(): import sys input = sys.stdin.read().strip().split('\n') album1 = input[0] album2 = input[1] similar_pairs = [line.split(',') for line in input[2:] if line] uf = UnionFind() for pair in similar_pairs: for i in range(len(pair) - 1): uf.union(pair[i], pair[i + 1]) normalized_album1 = normalize_string(album1, uf) normalized_album2 = normalize_string(album2, uf) if normalized_album1 == normalized_album2: print("True") for pair in similar_pairs: print(','.join(pair)) else: print("False") print(get_differences(album1, normalized_album1, normalized_album2)) if __name__ == "__main__": main()5.2 代码解析
详细讲解代码实现步骤
-
并查集（Union-Find）类：
- UnionFind 类用于处理字符的相似关系。find 方法用于查找字符的根代表，union 方法用于合并两个字符的相似集合。
- __init__ 方法初始化一个空的父节点字典 parent。
- find 方法使用路径压缩来查找并更新字符的根代表。
- union 方法合并两个字符的相似集合。
-
读取输入：
- 使用 sys.stdin.read() 读取输入数据，并将其按行分割成列表。
- 前两行是两个专辑名，从第三行开始是相似字符对。
- 将相似字符对存储在 similar_pairs 列表中。
-
构建并查集：
- 对于每一对相似字符对，调用 union 方法将它们合并到同一个集合中。
-
字符串归一化：
- normalize_string 函数遍历专辑名中的每一个字符，使用 find 方法将其归一化为相似集合的代表字符。
- 返回归一化后的字符串。
-
比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出 True 和相似字符对；否则，输出 False 和第一个专辑名中不相似的信息。
- get_differences 函数用于找出原始字符串中不相似的字符，并将它们连接成一个字符串返回。
六、JS实现
6.1 完整代码
class UnionFind { constructor() { this.parent = new Map(); } find(x) { if (!this.parent.has(x)) { this.parent.set(x, x); } if (this.parent.get(x) !== x) { this.parent.set(x, this.find(this.parent.get(x))); } return this.parent.get(x); } union(x, y) { let rootX = this.find(x); let rootY = this.find(y); if (rootX !== rootY) { this.parent.set(rootX, rootY); } } } function normalizeString(s, uf) { return s.split('').map(char => uf.find(char)).join(''); } function getDifferences(original, normalized1, normalized2) { let differences = []; for (let i = 0; i line.split(',')); let uf = new UnionFind(); for (let pair of similarPairs) { for (let i = 0; i6.2 代码解析
详细讲解代码实现步骤
-
并查集（Union-Find）类：
- UnionFind 类用于处理字符的相似关系。find 方法用于查找字符的根代表，union 方法用于合并两个字符的相似集合。
- constructor 初始化一个空的 Map 对象 parent。
- find 方法使用路径压缩来查找并更新字符的根代表。
- union 方法合并两个字符的相似集合。
-
读取输入：
- 使用 trim().split('\n') 读取输入数据，并将其按行分割成列表。
- 前两行是两个专辑名，从第三行开始是相似字符对。
- 将相似字符对存储在 similarPairs 列表中。
-
构建并查集：
- 对于每一对相似字符对，调用 union 方法将它们合并到同一个集合中。
-
字符串归一化：
- normalizeString 函数遍历专辑名中的每一个字符，使用 find 方法将其归一化为相似集合的代表字符。
- 返回归一化后的字符串。
-
比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出 True 和相似字符对；否则，输出 False 和第一个专辑名中不相似的信息。
- getDifferences 函数用于找出原始字符串中不相似的字符，并将它们连接成一个字符串返回。
七、总结
这道题目要求我们实现一个系统，用于判断两个字符串是否相似，并且在相似时返回相似的字符对，在不相似时返回第一个字符串中的不相似信息。主要用到了并查集（Union-Find）算法来处理字符的相似关系
下期见啦~
-
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
