DEV Community ·

1128. 等价多米诺骨牌对的数量

💡 原文英文，约600词，阅读约需2分钟。

📝

内容提要

给定多米诺骨牌列表，判断等价对的数量。两个骨牌等价当且仅当可以旋转匹配。通过标准化表示和哈希表统计频率，计算每个唯一骨牌的组合对数，时间复杂度为O(n)。

🎯

🔎

在处理多米诺骨牌时，标准化表示是关键步骤。通过将每个骨牌转换为(min(a, b), max(a, b))的形式，可以确保相同的骨牌无论顺序如何都被视为相同。这种方法简化了后续的频率统计和对数计算，避免了重复计算，提高了效率。

使用哈希表来统计标准化骨牌的出现次数，使得在遍历骨牌列表时能够快速查找和更新频率。这种方法不仅提高了计算速度，还使得整体时间复杂度保持在O(n)，适合处理大规模输入。

在计算等价骨牌对数时，使用组合公式c * (c - 1) / 2可以有效地从频率中得出结果。这种方法避免了暴力搜索每一对骨牌的低效做法，确保了在大数据量下的高效性。

❓

两个多米诺骨牌等价当且仅当可以旋转匹配，即[a, b]与[c, d]等价当且仅有(a == c且b == d)或(a == d且b == c)。

通过标准化每个多米诺骨牌的表示，使用哈希表统计频率，然后应用组合公式c * (c - 1) / 2计算每个唯一骨牌的对数。

标准化表示是将每个多米诺骨牌[a, b]转换为(min(a, b), max(a, b))，以确保等价的骨牌被一致处理。

该算法的时间复杂度为O(n)，适用于大输入规模。

使用哈希表记录每个标准化多米诺骨牌的出现次数，以便后续计算等价对。

例如，输入[[1,2],[2,1],[3,4],[5,6]]，等价对为(0, 1)，输出为1。

🏷️