给你一个由一些多米诺骨牌组成的列表 dominoes。
如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的。
形式上,dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d,或是 a==d 且 b==c。
在 0 <= i < j < dominoes.length 的前提下,找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
示例:
输入:dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出:1
提示:
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
dominoes
中的值的范围是 [1,9]
,因此可以使用单个骨牌里的两个数来构建成一个范围在 [11,99]
的数。
这里让较小的数作为十位数,较大的数作为个位数。这样就实现了两个等效的骨牌对应的是同一个数。
构造出来的数作为 key,统计每类骨牌的出现次数。
当使用哈希表进行统计之后,对于个数大于等于 2 的骨牌。根据骨牌的出现次数,使用等差数列求和公式来计算对数:
注意:对于数量为 cnt
的骨牌的对数的项数为 n - 1
class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int[] dominoe : dominoes) {
int key = Math.min(dominoe[0], dominoe[1]) * 10 + Math.max(dominoe[0], dominoe[1]);
map.put(key, map.getOrDefault(key, 0) + 1);
}
int ans = 0;
for (int key : map.keySet()) {
int cnt = map.get(key);
if (cnt >= 2) {
ans += (cnt - 1) + (cnt - 1) * (cnt - 2) / 2;
}
}
return ans;
}
}
由于转换出来的数的范围固定为 [11,99]
,我们可以直接使用等长数组来进行计数。
对于数量为 n
的骨牌,其对数等于 1 + 2 + 3 + 4 + ... + (n - 1)
因此可以采用边遍历边累加的方式:
class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
int[] cnt = new int[89];
int ans = 0;
for (int[] dominoe : dominoes) {
int idx = Math.min(dominoe[0], dominoe[1]) * 10 + Math.max(dominoe[0], dominoe[1]) - 11;
ans += cnt[idx];
cnt[idx]++;
}
return ans;
}
}
这是我们「刷穿 LeetCode」系列文章的第 * 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。