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 <= 400001 <= dominoes[i][j] <= 9
第一版，直接遍历，超出时间限制
intnumEquivDominoPairs(vector<vector<int>>&dominoes) {
intcut=0;
for (inti=0; i<dominoes.size(); ++i) {
for (intj=i+1; j<dominoes.size(); ++j) {
if ((dominoes[i][0] ==dominoes[j][0] &&dominoes[i][1] ==dominoes[j][1]) || (dominoes[i][0] ==dominoes[j][1] &&dominoes[i][1] ==dominoes[j][0]))
cut++;
}
}
returncut;
}
第二版，自己定义unordered_map的键值，为其他类型
执行用时 :52 ms, 在所有 cpp 提交中击败了87.56%的用户
内存消耗 :21 MB, 在所有 cpp 提交中击败了100.00%的用户
实例：https://blog.csdn.net/zhangpiu/article/details/49837387?utm_source=blogxgwz9
structKEY
{
intminNum;
intmaxNum;
KEY(intf, ints) : minNum(f), maxNum(s) {}
};
structHashFunc
{
std::size_toperator()(constKEY&key) const
{
usingstd::size_t;
usingstd::hash;
return ((hash<int>()(key.minNum)
^ (hash<int>()(key.maxNum) <<1)) >>1);
}
};
structEqualKey
{
booloperator () (constKEY&lhs, constKEY&rhs) const
{
returnlhs.minNum==rhs.minNum
&&lhs.maxNum==rhs.maxNum;
}
};
intnumEquivDominoPairs(vector<vector<int>>&dominoes) {
unordered_map<KEY,int,HashFunc,EqualKey>unmp;
intcut=0;
intmaxNum=0, minNum=0;
for (auto&n:dominoes) {
minNum=min(n[0], n[1]);
maxNum=max(n[0], n[1]);
if (unmp.find({ minNum,maxNum }) !=unmp.end()) {
cut+=unmp[{ minNum, maxNum }];
unmp[{minNum, maxNum}]++;
}
else
unmp[{minNum,maxNum}]++;
}
returncut;
}
第三版，参考别人的，会更快一点了
执行用时 :48 ms, 在所有 cpp 提交中击败了95.27%的用户
内存消耗 :21.1 MB, 在所有 cpp 提交中击败了100.00%的用户
intnumEquivDominoPairs(vector<vector<int>>&dominoes) {
unordered_map<int, int>ret;
intcut=0,minNum=0,maxNum=0;
for (auto&a : dominoes) {
maxNum=max(a[0], a[1]);
minNum=min(a[0], a[1]);
if (ret.find(minNum*10+maxNum) !=ret.end()) {
cut+=ret[minNum*10+maxNum];
}
ret[minNum*10+maxNum] +=1;
}
returncut;
}
第四版，别人的写法，化为数学公式来做的
执行用时 :44 ms, 在所有 cpp 提交中击败了97.76%的用户
内存消耗 :21.1 MB, 在所有 cpp 提交中击败了100.00%的用户
intnumEquivDominoPairs(vector<vector<int>>&dominoes) {
map<int, int>ret;
intcount=0;
for(inti =0; i<dominoes.size(); ++i)
{
intk=0;
intm=dominoes[i][0];
intn=dominoes[i][1];
(m>n) ?k=n*10+m : k=m*10+n;//这种表达式也是可以的
ret[k] +=1;
}
for(autoiter=ret.begin(); iter!=ret.end(); ++iter)
{
count+=iter->second* (iter->second-1) /2;
}
returncount;
}
第五版，结合一下，最快的
执行用时 :40 ms, 在所有 cpp 提交中击败了99.00%的用户
内存消耗 :21 MB, 在所有 cpp 提交中击败了100.00%的用户
intnumEquivDominoPairs(vector<vector<int>>&dominoes) {
unordered_map<int, int>ret;
intk=0, m=0, n=0;
for (inti=0; i<dominoes.size(); ++i)
{
m=dominoes[i][0];
n=dominoes[i][1];
(m>n) ?k=n*10+m : k=m*10+n;//这种表达式也是可以的
ret[k] +=1;
}
intcount=0;
for (auto&iter:ret)
{
count+=iter.second* (iter.second-1) /2;
}
returncount;
}
