leetcode_OJ WC146 Report and some notes
These days I usually write the solution report on leetcode official website more than my own github website, serving as a path to communicate with pro algorithmic coders and exchange the ideas throughout the world.
PA. 1128. Number of Equivalent Domino Pairs
- Approach: Use pair and let the smaller value always at the front, then C(i, 2) for combinations of 2 in i same dominoes group
- Analysis:
- Time complexity: O(N)
- Space complexity: O(N) for storing the results
class Solution { public: int numEquivDominoPairs(vector<vector<int>>& d) { int res = 0, n = d.size(); map<pair<int, int>, int> m; for(int i = 0; i < n; i++) { if(d[i][0] > d[i][1]) { m[make_pair(d[i][1], d[i][0])]++; } else { m[make_pair(d[i][0], d[i][1])]++; } } auto it = m.begin(); while(it != m.end()) { if(it -> second > 1) { res += (it -> second) * (it -> second - 1) / 2 ; } it++; } return res; } };