多米诺骨牌等价问题

Posted on Edited on In Word count in article: 701 Reading time ≈ 1 mins.
多米诺骨牌等价问题

给你一个由一些多米诺骨牌组成的列表 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
2
input = [[1,2],[1,2],[1,1],[1,2],[2,2]]
res = 3

通过map的方式进行过滤，符合多米诺骨牌的条件都加1，然后对这个数字求其对数

通过这个结果10* i[0] + i[1] 判断，i，j不同的大小比较，算一种结果

最后求对数，遍历字典，加起来，k* (k-1)/2，去算有同样骨牌可以产出的对数，最后都加起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func numEquivDominoPairs(dominoes [][]int) int {
    count := 0
    res := make(map[int]int, len(dominoes))
    for _, i := range dominoes {
        var num int
        if i[0] < i[1] {
            num = 10*i[0] + i[1]
        } else {
            num = 10*i[1] + i[0]
        }
        res[num] += 1
    }
    for _, i := range res {
        count += int(i*(i-1)/2)
    }
    return count
}