leetcode每日一题2020.1.26

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) 的数量。

示例1：

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

提示：

1 ≤ dominoes.length ≤ 40000
1 ≤ dominoes[i][j] ≤ 9

二、题解

方法1：排序 + 哈希map + 计数

1	将 dominoes 数组中每一项按从小到大排个序变为字符串，然后哈希表记录下出每个字符串出现的次数，最后遍历哈希表即可得

时间复杂度：O(n)，n 是数组的长度。
空间复杂度：O(n)

var numEquivDominoPairs = function(dominoes) {
    dominoes = dominoes.map(e => e[0] < e[1] ? '' + e[0] + e[1] : '' + e[1] + e[0]);
    let map = new Map();
    for (let dominoe of dominoes) {
        if (map.has(dominoe)) {
            map.set(dominoe, map.get(dominoe) + 1)
        } else {
            map.set(dominoe, 1)
        }
    }
    let ret = 0;
    map.forEach(value => {
        ret += value * (value - 1) / 2
    })
    return ret
};

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

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

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

时间复杂度：O(n)，n 是数组的长度。
空间复杂度：O(1)

var numEquivDominoPairs = function (dominoes) {
    let arr = Array(100).fill(0);
    let ret = 0;
    for (const ele of dominoes) {
        let val = ele[0] > ele[1] ? 10 * ele[1] + ele[0] : 10 * ele[0] + ele[1];
        arr[val]++;
    }
    for (const n of arr) {
        ret += n * (n - 1) / 2
    }
    return ret
};