LeetCode Weekly Contest 146

刺骨的言语ヽ痛彻心扉 2023-06-01 05:48 24阅读 0赞

### 1128. Number of Equivalent Domino Pairs ###

Given a list of `dominoes`, `dominoes[i] = [a, b]` is *equivalent* to `dominoes[j] = [c, d]` if and only if either (`a==c` and `b==d`), or (`a==d`and `b==c`) - that is, one domino can be rotated to be equal to another domino.

Return the number of pairs `(i, j)` for which `0 <= i < j < dominoes.length`, and `dominoes[i]` is equivalent to `dominoes[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`

题目大意：给你一个数字键值对数组，让你判断有多少个数组元素是相等的。两个键值对相等的条件是：键1=键2并且值1=值2或者键1=值2并且键2=值1。

思路：将键值的和中放前面加上“\_”以及键值中较小的数作为map的key存入map，然后遍历map求和就好。（其实可以将键值中较小的数乘100或者1000然后加上大的那个数作为key，但是竞赛的时候，脑子没转过来，就用了这个方法，也是AC了）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

class Solution {
        public int numEquivDominoPairs(int[][] dominoes) {
            Map<String, Integer> map = new HashMap<>();
            int len = dominoes.length;
            for(int i=0; i<len; i++) {
                int a = dominoes[i][0];
                int b = dominoes[i][1];
                String te = a+b + "-";
                if( a > b ) te = te + b;
                else te = te + a;
                Integer cnt = map.get(te);
                if( cnt==null ) {
                    map.put(te, 1);
                } else {
                    map.put(te, cnt+1);
                }
            }
            int sum = 0;
            for(Map.Entry<String, Integer> entry : map.entrySet() ) {
                int v = entry.getValue();
                sum += (v*(v-1))/2;
            }
            return sum;
        }
    }

转载于:https://www.cnblogs.com/Asimple/p/11258542.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/ef5b9a5050364d8c8b583d6cff36cea3.png