个人技术分享

【华为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. 为了过滤一些无意义的信息，这里***可以匹配任意长度的内容，例如：

    给出相似对"(****)",""时，"异世邪君（人气玄幻作家）" 和 "异世邪君" 认为是相似，此时相似符号返回 *** 即可
     
  3. 不相似的内容，需要给出不相似的字符串，多处不相似的字符串用空格分隔

1.2 输入描述

  • 第一行表示第一张专辑的专辑名，其中 0 < 专辑长度 ≤ 50
  • 第二行表示第二张专辑的专辑名，其中 0 < 专辑长度 ≤ 50
  • 第三行开始每行为相似的字符串，每行一组，每组字符串不超过10个
  • 总共相似字符串行不超过10行

1.3 输出描述

  • 第一行返回相似判断的结果，即True或者False
  • 第二行开始返回相似/不相似的字符串，每行一组

1.4 用例

输入 林汉达上下五千年
林汉达上下5千年
五 5 ⑤ 伍 wu
输出 True
五 5
说明 无
输入 幸福de猪的个人专辑
幸福的猪的个人专辑
得 的
得 de
输出 True
de 的
说明 无
输入 异世邪君(人气玄幻作家)
异世邪君
(***)
输出

True

(***)
说明 无
输入 浩然爸爸讲成语
浩然爸爸讲论语
论语 三字经
输出 False
成语 论语
说明 无

二、题目解析

2.1 题目分析

这个题目主要考察以下几个算法和数据结构的知识：

  1. 字符串匹配和替换：

    • 在判断两个字符串是否相似时，需要能够快速匹配和替换字符串中的相似字符对。

  2. 并查集（Union-Find）算法：

    • 由于相似关系是传递性的，可以用并查集算法来处理这种相似关系，方便快速查找和合并相似字符的集合。

  3. 哈希表：

    • 使用哈希表存储相似字符对，方便快速查找和匹配。

2.2 实现思路

  1. 读取输入：包括两个专辑名和相似字符对。
  2. 构建并查集：用并查集来处理相似字符对，构建每个字符的相似集合。
  3. 字符串归一化：根据并查集，将两个专辑名归一化，即将所有相似字符替换成它们的代表字符。
  4. 比较归一化后的字符串：判断归一化后的字符串是否相同。如果相同，返回 True 和相似字符对；否则，返回 False 和第一个专辑名中不相似的信息。

三、Java实现

3.1 详细代码

import java.util.*;

public class SimilarContentChecker {
    private static class UnionFind {
        private Map<String, String> 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<String[]> 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; i < pair.length - 1; i++) {
                uf.union(pair[i], pair[i + 1]);
            }
        }
        
        // 字符串归一化
        String normalizedAlbum1 = normalizeString(album1, uf);
        String normalizedAlbum2 = normalizeString(album2, uf);
        
        // 比较归一化后的字符串
        if (normalizedAlbum1.equals(normalizedAlbum2)) {
            System.out.println("True");
            printSimilarPairs(similarPairs);
        } else {
            System.out.println("False");
            System.out.println(getDifferences(album1, normalizedAlbum1, normalizedAlbum2));
        }
    }
    
    private static String normalizeString(String s, UnionFind uf) {
        StringBuilder normalized = new StringBuilder();
        for (char c : s.toCharArray()) {
            String str = String.valueOf(c);
            normalized.append(uf.find(str));
        }
        return normalized.toString();
    }
    
    private static void printSimilarPairs(List<String[]> similarPairs) {
        for (String[] pair : similarPairs) {
            System.out.println(Arrays.toString(pair));
        }
    }
    
    private static String getDifferences(String original, String normalized1, String normalized2) {
        StringBuilder differences = new StringBuilder();
        for (int i = 0; i < original.length(); i++) {
            if (normalized1.charAt(i) != normalized2.charAt(i)) {
                differences.append(original.charAt(i)).append(" ");
            }
        }
        return differences.toString().trim();
    }
}

3.2 代码解析

详细讲解代码实现步骤

  1. 并查集（Union-Find）类：

    • UnionFind 类用于处理字符的相似关系。find 方法用于查找字符的根代表，union 方法用于合并两个字符的相似集合。

  2. 读取输入：

    • 使用 Scanner 读取两个专辑名和相似字符对。
    • 将相似字符对存储在 similarPairs 列表中。

  3. 构建并查集：

    • 对于每一对相似字符对，调用 union 方法将它们合并到同一个集合中。

  4. 字符串归一化：

    • 遍历专辑名中的每一个字符，使用 find 方法将其归一化为相似集合的代表字符。

  5. 比较归一化后的字符串：

    • 比较归一化后的两个专辑名是否相同。如果相同，输出 True 和相似字符对；否则，输出 False 和第一个专辑名中不相似的信息。

这种方法使用了并查集来高效处理相似关系，并使用哈希表进行字符查找和归一化处理，确保了算法的高效性和准确性。

四、C#实现

4.1 详细代码

using System;
using System.Collections.Generic;

public class SimilarContentChecker
{
    private class UnionFind
    {
        private Dictionary<string, string> parent;

        public UnionFind()
        {
            parent = new Dictionary<string, string>();
        }

        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<string[]> similarPairs = new List<string[]>();
        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; i < pair.Length - 1; i++)
            {
                uf.Union(pair[i], pair[i + 1]);
            }
        }
        
        string normalizedAlbum1 = NormalizeString(album1, uf);
        string normalizedAlbum2 = NormalizeString(album2, uf);
        
        if (normalizedAlbum1 == normalizedAlbum2)
        {
            Console.WriteLine("True");
            PrintSimilarPairs(similarPairs);
        }
        else
        {
            Console.WriteLine("False");
            Console.WriteLine(GetDifferences(album1, normalizedAlbum1, normalizedAlbum2));
        }
    }
    
    private static string NormalizeString(string s, UnionFind uf)
    {
        char[] normalized = new char[s.Length];
        for (int i = 0; i < s.Length; i++)
        {
            normalized[i] = uf.Find(s[i].ToString())[0];
        }
        return new string(normalized);
    }
    
    private static void PrintSimilarPairs(List<string[]> similarPairs)
    {
        foreach (var pair in similarPairs)
        {
            Console.WriteLine(string.Join(",", pair));
        }
    }
    
    private static string GetDifferences(string original, string normalized1, string normalized2)
    {
        List<char> differences = new List<char>();
        for (int i = 0; i < original.Length; i++)
        {
            if (normalized1[i] != normalized2[i])
            {
                differences.Add(original[i]);
            }
        }
        return string.Join(" ", differences);
    }
}

4.2 代码解析

详细讲解代码实现步骤

  1. 并查集（Union-Find）类：

    • UnionFind 类用于处理字符的相似关系。Find 方法用于查找字符的根代表，Union 方法用于合并两个字符的相似集合。

  2. 读取输入：

    • 使用 Console.ReadLine() 读取两个专辑名和相似字符对。
    • 将相似字符对存储在 similarPairs 列表中。

  3. 构建并查集：

    • 对于每一对相似字符对，调用 Union 方法将它们合并到同一个集合中。

  4. 字符串归一化：

    • 遍历专辑名中的每一个字符，使用 Find 方法将其归一化为相似集合的代表字符。

  5. 比较归一化后的字符串：

    • 比较归一化后的两个专辑名是否相同。如果相同，输出 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 代码解析

详细讲解代码实现步骤

  1. 并查集（Union-Find）类：

    • UnionFind 类用于处理字符的相似关系。find 方法用于查找字符的根代表，union 方法用于合并两个字符的相似集合。
    • __init__ 方法初始化一个空的父节点字典 parent。
    • find 方法使用路径压缩来查找并更新字符的根代表。
    • union 方法合并两个字符的相似集合。

  2. 读取输入：

    • 使用 sys.stdin.read() 读取输入数据，并将其按行分割成列表。
    • 前两行是两个专辑名，从第三行开始是相似字符对。
    • 将相似字符对存储在 similar_pairs 列表中。

  3. 构建并查集：

    • 对于每一对相似字符对，调用 union 方法将它们合并到同一个集合中。

  4. 字符串归一化：

    • normalize_string 函数遍历专辑名中的每一个字符，使用 find 方法将其归一化为相似集合的代表字符。
    • 返回归一化后的字符串。

  5. 比较归一化后的字符串：

    • 比较归一化后的两个专辑名是否相同。如果相同，输出 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 < original.length; i++) {
        if (normalized1[i] !== normalized2[i]) {
            differences.push(original[i]);
        }
    }
    return differences.join(' ');
}

function main(input) {
    let lines = input.trim().split('\n');
    
    let album1 = lines[0];
    let album2 = lines[1];
    
    let similarPairs = lines.slice(2).map(line => line.split(','));

    let uf = new UnionFind();
    for (let pair of similarPairs) {
        for (let i = 0; i < pair.length - 1; i++) {
            uf.union(pair[i], pair[i + 1]);
        }
    }

    let normalizedAlbum1 = normalizeString(album1, uf);
    let normalizedAlbum2 = normalizeString(album2, uf);

    if (normalizedAlbum1 === normalizedAlbum2) {
        console.log("True");
        for (let pair of similarPairs) {
            console.log(pair.join(','));
        }
    } else {
        console.log("False");
        console.log(getDifferences(album1, normalizedAlbum1, normalizedAlbum2));
    }
}

// Example usage:
const input = `albumOne
albumTwo
a,b
b,c
c,d`;

main(input);

6.2 代码解析

详细讲解代码实现步骤

  1. 并查集（Union-Find）类：

    • UnionFind 类用于处理字符的相似关系。find 方法用于查找字符的根代表，union 方法用于合并两个字符的相似集合。
    • constructor 初始化一个空的 Map 对象 parent。
    • find 方法使用路径压缩来查找并更新字符的根代表。
    • union 方法合并两个字符的相似集合。

  2. 读取输入：

    • 使用 trim().split('\n') 读取输入数据，并将其按行分割成列表。
    • 前两行是两个专辑名，从第三行开始是相似字符对。
    • 将相似字符对存储在 similarPairs 列表中。

  3. 构建并查集：

    • 对于每一对相似字符对，调用 union 方法将它们合并到同一个集合中。

  4. 字符串归一化：

    • normalizeString 函数遍历专辑名中的每一个字符，使用 find 方法将其归一化为相似集合的代表字符。
    • 返回归一化后的字符串。

  5. 比较归一化后的字符串：

    • 比较归一化后的两个专辑名是否相同。如果相同，输出 True 和相似字符对；否则，输出 False 和第一个专辑名中不相似的信息。
    • getDifferences 函数用于找出原始字符串中不相似的字符，并将它们连接成一个字符串返回。

七、总结

 这道题目要求我们实现一个系统，用于判断两个字符串是否相似，并且在相似时返回相似的字符对，在不相似时返回第一个字符串中的不相似信息。主要用到了并查集（Union-Find）算法来处理字符的相似关系

下期见啦~