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

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

思路

暴力

暴力双重循环可以很容易得到答案。

改进

遍历，将等价多米诺牌进行计数，若不存在，则在哈希表中开始记录，若存在，说明当前牌可以和这个等价牌堆里的所有牌组成一个新对子，若当前牌堆有 n 个，组成的新对子数量新增 n 个。

解答

暴力

/**
 * @param {number[][]} dominoes
 * @return {number}
 */
var numEquivDominoPairs = function (dominoes) {
  let res = 0;
  for (let i = 0; i < dominoes.length; i++) {
    const [a, b] = dominoes[i];
    for (let j = i + 1; j < dominoes.length; j++) {
      const [c, d] = dominoes[j];
      if ((a === d && b === c) || (a === c && b === d)) res++;
    }
  }
  return res;
};

改进

/**
 * @param {number[][]} dominoes
 * @return {number}
 */
var numEquivDominoPairs = function (dominoes) {
  let res = 0;
  const map = {};
  for (const dominoe of dominoes) {
    let [a, b] = dominoe;
    const key = a > b ? a + 10 * b : b + a * 10;
    if (map[key]) res += map[key]++;
    else map[key] = 1;
  }
  return res;
};