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

给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。

形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是
a==d 且 b==c。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j]
等价的骨牌对 (i, j) 的数量。

示例：

**输入：** dominoes = [[1,2],[2,1],[3,4],[5,6]]
**输出：** 1

提示：

• 1 <= dominoes.length <= 40000
• 1 <= dominoes[i][j] <= 9

方法一：二元组表示 + 计数

思路及解法

本题中我们需要统计所有等价的多米诺骨牌，其中多米诺骨牌使用二元对代表，「等价」的定义是，在允许翻转两个二元对的的情况下，使它们的元素一一对应相等。

于是我们不妨直接让每一个二元对都变为指定的格式，即第一维必须不大于第二维。这样两个二元对「等价」当且仅当两个二元对完全相同。

注意到二元对中的元素均不大于 9，因此我们可以将每一个二元对拼接成一个两位的正整数，即 (x, y) \to 10x + y。这样就无需使用哈希表统计元素数量，而直接使用长度为 100 的数组即可。

代码

[sol1-C++]

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        vector<int> num(100);
        int ret = 0;
        for (auto& it : dominoes) {
            int val = it[0] < it[1] ? it[0] * 10 + it[1] : it[1] * 10 + it[0];
            ret += num[val];
            num[val]++;
        }
        return ret;
    }
};

[sol1-Java]

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] num = new int[100];
        int ret = 0;
        for (int[] domino : dominoes) {
            int val = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];
            ret += num[val];
            num[val]++;
        }
        return ret;
    }
}

[sol1-JavaScript]

var numEquivDominoPairs = function(dominoes) {
    const num = new Array(100).fill(0);
    let ret = 0;
    for (const domino of dominoes) {
        const val = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];
        ret += num[val];
        num[val]++;
    }
    return ret;
};

[sol1-Golang]

func numEquivDominoPairs(dominoes [][]int) (ans int) {
    cnt := [100]int{}
    for _, d := range dominoes {
        if d[0] > d[1] {
            d[0], d[1] = d[1], d[0]
        }
        v := d[0]*10 + d[1]
        ans += cnt[v]
        cnt[v]++
    }
    return
}

[sol1-C]

int numEquivDominoPairs(int** dominoes, int dominoesSize, int* dominoesColSize) {
    int num[100];
    memset(num, 0, sizeof(num));
    int ret = 0;
    for (int i = 0; i < dominoesSize; i++) {
        int val = dominoes[i][0] < dominoes[i][1] ? dominoes[i][0] * 10 + dominoes[i][1] : dominoes[i][1] * 10 + dominoes[i][0];
        ret += num[val];
        num[val]++;
    }
    return ret;
}

[sol1-Python3]

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        num = [0] * 100
        ret = 0
        for x, y in dominoes:
            val = (x * 10 + y if x <= y else y * 10 + x)
            ret += num[val]
            num[val] += 1
        return ret

复杂度分析

• 时间复杂度：O(n)，其中 n 是多米诺骨牌的数量。我们至多只需要遍历一次该数组。

• 空间复杂度：O(1)，我们只需要常数的空间存储若干变量。