首页 leetcode

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

输入样例:

dominoes = [[1,2],[2,1],[3,4],[5,6]]

输出样例:

1

ac代码

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int a[105] = {};
        int num = 0;
        int size = dominoes.size();
        for (int i = 0; i < size; i++) {
            int a1 = dominoes[i][0] * 10 + dominoes[i][1];
            int a2 = dominoes[i][1] * 10 + dominoes[i][0];
            a1 = a1 > a2 ? a1 : a2;
            if (a[a1] > 0) a[a1]++;
            else a[a1] = 1;
        }
        for (int i = 1; i < 100; i++) {
            if(a[i] == 2) num++;
            else if(a[i] > 2) num += a[i] * (a[i] - 1) / 2;
        }
        return num;
    }
};

心得:

第1~3次WA:如果有两个相同的是2,三个相同的是3,这里有组合数没想到

第四次AC:考虑到了的组合数情况,写出了解放。

官方方法:

注意统计组合数的方法:(第八行)

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

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/solution/deng-jie-duo-mi-nuo-gu-pai-dui-de-shu-li-yjlz/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



文章评论

目录