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

朴灿烈づ我的快乐病毒、 2022-11-19 07:45 132阅读 0赞

# [1128. 等价多米诺骨牌对的数量][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`

# 英文 #

Given a list of `dominoes`, `dominoes[i] = [a, b]` is *equivalent* to `dominoes[j] = [c, d]` if and only if either (`a==c` and `b==d`), or (`a==d` and `b==c`) - that is, one domino can be rotated to be equal to another domino.

Return the number of pairs `(i, j)` for which `0 <= i < j < dominoes.length`, and `dominoes[i]` is equivalent to `dominoes[j]`.

**Example 1:**

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
    Output: 1

**Constraints:**

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

# 代码与思路 #

假设某一类\[等价\]的对象的总数为N，这一类中任意取出2个的组合数 C N 2 = N ( N − 2 ) 2 C\_\{N\}^\{2\}=\\frac\{N(N-2)\}\{2\} CN2=2N(N−2)就是这一类对总数量。

java

class Solution { 
        public int numEquivDominoPairs(int[][] dominoes) { 
            //先统计每种等价的骨牌数量，然后对于每一种都是组合数C(N)(2)，加起来即可
            int[] map = new int[100];
            int res = 0;
            for(int i = 0; i < dominoes.length; i++){ 
                int m = dominoes[i][0];
                int n = dominoes[i][1];
                int k = m > n ? m * 10 + n : n * 10 + m;
                map[k] ++;
            }
            for(int i = 0; i < 100; i++){ 
                res += map[i] * (map[i] - 1) / 2;
            }
            return res;
        }
    }

cpp

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;
        }
    };

[1128.]: https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/