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
Solution: HashTable
Count how many times each key occurred so far.
Time complexity: O(n)
Space complexity: O(100)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int numEquivDominoPairs(vector<vector<int>>& dominoes) { vector<int> m(100); int ans = 0; for (const auto& d : dominoes) { int k1 = d[0] * 10 + d[1]; int k2 = d[1] * 10 + d[0]; ans += m[k1]; if (k1 != k2) ans += m[k2]; ++m[k1]; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment