1128. Number of Equivalent Domino Pairs

问题:

给出数对构成的数组dominoes,若其中一对数对dominoes[i]和另一对数对dominoes[j]包含两个数字相同(忽略顺序),那么称这两对数对等价,

求给定数组dominoes,有多少对(i,j)为等价数对。

Example 1:
Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1
 

Constraints:
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9

  

解法:

由于限制条件:数对内数字在0~9之间,

因此,我们可以考虑,桶排序,

int sumct[100]

将每个数对,使用【较小数*10+较大数】标记,

拥有相同标记的,则为满足条件的等价数对,

计数等价数对,

遍历所有数对,每增加一个等价数对,

所求等价数对的对数+=目前存在的等价数对个数。

res+=sumct[sum];

 

参考代码:

 1 class Solution {
 2 public:
 3     int numEquivDominoPairs(vector<vector<int>>& dominoes) {
 4         int sumct[100]={0};
 5         int res=0;
 6         for(auto dom:dominoes){
 7             int sum=(dom[0]>dom[1])?dom[1]*10+dom[0]:dom[0]*10+dom[1];
 8             res+=sumct[sum];
 9             sumct[sum]++;
10         }
11         return res;
12     }
13 };

 

上一篇:LeetCode--412.Fizz Buzz(C++描述)


下一篇:【数据结构1-1】线性表 P4387 【深基15.习9】验证栈序列