题目:
给你一个由一些多米诺骨牌组成的列表 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
解题方法:
这道题一开始想到使用set来处理,但是没有想到用map+set来做,数据结构用的不够熟练,所以特意记录一下。程序的思路就是:
创建一个set,把多米诺骨牌的两个数存进去;
通过map记录这个set出现的次数;
遍历map,统计总共出现的等价骨牌对数,这里因为不是排列是组合,所以应该加Cn^2。
代码和结果:
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& dominoes) {
map<set<int>,int> map1;
int count=0;
for(int i=0;i<dominoes.size();i++)
{
set<int> set1;
set1.insert(dominoes[i][0]);
set1.insert(dominoes[i][1]);
map1[set1]++;
}
map<set<int>,int>::iterator it;
for(it = map1.begin();it != map1.end();it++)
{
if(it->second >1) count += (it->second)*(it->second - 1)/2;
}
return count;
}
};
运行结果:在内存占用和速度方面,这个方法并不好,但是这种解法让我对map和set使用有了更深的认识,而且代码实现非常简洁,在性能要求不苛刻的条件下,我觉得是一个比较容易学会和使用的方法,值得一记。
原题链接:https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/