This is the 7th day of my participation in Gwen Challenge

describe

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: 1Copy the code

Note:

1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
Copy the code

parsing

If I <j, dominoes[I] count as a pair as long as the contents in dominoes[j] are the same. Order dominoes[I] from the smallest to the largest, and then determine if the current dominoes[j] element meets the requirements. If so, increment the count. If not, compare with other dominoes[x] that are the same. When and are different, repeat the above process starting with dominoes[I +1]. The resulting counter value is the result.

answer

class Solution(object):
    def numEquivDominoPairs(self, dominoes):
        """
        :type dominoes: List[List[int]]
        :rtype: int
        """
        dominoes = sorted(dominoes, key=lambda x:sum(x))
        N = len(dominoes)
        count = 0
        i=0
        while i<N-1:
            s = sum(dominoes[i])
            for j in range(i+1,N):
                if s == sum(dominoes[j]):
                    if (dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]) or (dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]):
                        count += 1
                    else:
                        continue
                else:
                    break
            i+=1
        return count
        	      
		
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

Sort each of the elements in dominoes in the same order. Then count the elements in dominoes and save them to the dictionary D. Then count v in D and add v*(V-1)//2 to the counter.

answer

class Solution(object):
    def numEquivDominoPairs(self, dominoes):
        """
        :type dominoes: List[List[int]]
        :rtype: int
        """
        for i in range(len(dominoes)):
            dominoes[i].sort()
        d = {}
        for i in dominoes:
            i = tuple(i)
            if i in d:
                d[i]+=1
            else:
                d[i] = 1
        c = 0
        for k,v in d.items():
            c += v*(v-1)//2
        return c
        	      
		
Copy the code

The results

Given the Python online submission for Number of Equivalent Domino Pairs. Memory Usage: Given in Python online submissions for Number of Equivalent Domino Pairs.Copy the code

Original link: leetcode.com/problems/nu…

Your support is my biggest motivation