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
Example 2:
Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output: 3
Constraints:
1 <= dominoes.length <= 4 * 104
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9
思路一:用 map 映射,原先想用 x * 10 + y 来作 map 的 key,但是 bug 比较多,最后直接用 string 一把梭了
public static int numEquivDominoPairs(int[][] dominoes) {
int ans = 0;
Map<String, Integer> map = new HashMap<>();
for (int[] dominoe : dominoes) {
if (dominoe[0] > dominoe[1]) {
map.compute(dominoe[0] + "," + dominoe[1], (k, v) -> v == null ? 1 : v + 1);
} else {
map.compute(dominoe[1] + "," + dominoe[0], (k, v) -> v == null ? 1 : v + 1);
}
}
for (Map.Entry<String, Integer> e : map.entrySet()) {
if (e.getValue() <= 1) {
continue;
}
ans += e.getValue() * (e.getValue() - 1);
}
return ans / 2;
}
思路二:补上官方的解
public int numEquivDominoPairs(int[][] dominoes) {
int[] num = new int[100];
int ret = 0;
for (int[] domino : dominoes) {
int val = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];
ret += num[val];
num[val]++;
}
return ret;
}
标签:1128,map,dominoe,int,domino,num,easy,dominoes,leetcode
From: https://www.cnblogs.com/iyiluo/p/17413211.html