LETCODE1128dominoes

LETCODE 1128 dominoes

这个题目暴力不行

int numEquivDominoPairs(int** dominoes, int dominoesSize, int* dominoesColSize)
{
int eqsize = 0;
for (int i = 0; i {
dominoesColSize = dominoes[i];
for (int j = i + 1; j {
if ((dominoesColSize[0] == dominoes[j][0] && dominoesColSize[1] == dominoes[j][1])|| dominoesColSize[0] == dominoes[j][1] && dominoesColSize[1] == dominoes[j][0])
eqsize++;
}
}
return eqsize;
}


此为暴力代码

在测试的最后两例会超时

两遍循环导致超时

后面我使用 map来测试就可以了

class Solution {
public:
int numEquivDominoPairs(vector>& dominoes) {
int eqsize = 0;
int n = dominoes.size();
map

, int>domi;
for(int i = 0; i {
if (dominoes[i][0] > dominoes[i][1])
{
int t = dominoes[i][0];
dominoes[i][0] = dominoes[i][1];
dominoes[i][1] = t;
}
domi[{dominoes[i][0], dominoes[i][1]}]++;
}
for (auto p :domi)
{
int c = p.second;
eqsize += c*(c - 1) / 2;
}
return eqsize;
}
};