蹉跎岁月 岁月里蹉跎。今天补交一个题。
这个题在leetcode里是easy的难度,我确没有写完,真不愿意来承认啊。
题目如下:
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]
解:
一开始我就只想到了暴力double for loop,配合一个private method which is used to compare whether it is equal. 测试结果就是时间复杂度太高了,么有accept。
看了别人的解法,原来思路是这样的,as following code.
public int numEquivDominoPairs(int[][] dominoes) { int[] res = {0}; Map<Integer, Integer> map = new HashMap<>(); int key = 0; for (int[] d : dominoes) { key = Math.min(d[0], d[1]) * 10 + Math.max(d[0], d[1]); map.put(key, map.getOrDefault(key, 0) + 1); } map.forEach((k, v) -> { res[0] += v * (v - 1) / 2; }); return res[0]; }
思路是把element array 转换成一个十进制数或者字符串。把得到的数或者字符串放在map里。然后用排列组合算出结果。res = C(2/v)
然后下面的解法就是直接累加计数得到结果:
public int numEquivDominoPairs(int[][] dominoes) { int res = 0; int key = 0; Map<Integer, Integer> map = new HashMap<>(); for (int[] d : dominoes) { key = Math.min(d[0], d[1]) * 10 + Math.max(d[0], d[1]); res += map.getOrDefault(key, 0); map.put(key, map.getOrDefault(key, 0) + 1); } return res; }