5130-等价多米诺骨牌对的数量
文章目录
前言
Weekly Contest 146的 等价多米诺骨牌对的数量:
给你一个由一些多米诺骨牌组成的列表
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 <= 400001 <= dominoes[i][j] <= 9
解题思路
一开始我是试了一下暴力破解这个方法,可惜运行超时,只好另想它法了。
后续参考了Java中的HashMap的位桶的设计,思路如下:
- 数字
result表示等价的骨牌对个数,数组arr表示多米诺骨牌出现的次数,其中数组下标i(假设骨牌dominoe=[a,b],则i=a*10+b)表示对应的多米诺骨牌,arr[i]表示该骨牌出现的次数 -
遍历多米诺骨牌列表
dominoes,对于每个骨牌dominoe,假设dominoe=[a,b],然后按照以下逻辑处理- 使用
a*10+b计算出旋转0度时在arr的下标index1;使用b*10+a计算出旋转180度是在arr的下标index2 - 如果
index1等于index2,即表示dominoe的a等于b,此时result增加arr[index1],同时arr[index1]的值自增(避免多累加一次)即可 - 如果
index1不等于index2,即表示dominoe的a不等于b,此时result增加arr[index1],同时arr[index1]和arr[index2]都自增。
- 使用
实现代码
暴力破解
暴力破解的方法会出现运行超时的情况,这个是一个错误的示例,列出来给大家参考一下。
/**
* 5130. 等价多米诺骨牌对的数量
* 暴力破解法
* @param dominoes
* @return
*/
public int numEquivDominoPairs(int[][] dominoes) {
int result = 0;
for (int i = 0; i < dominoes.length; i++) {
int a = dominoes[i][0];
int b = dominoes[i][1];
for (int j = i+1; j < dominoes.length; j++) {
int c = dominoes[j][0];
int d = dominoes[j][1];
if((a==c && b==d) || (a==d && b==c)){
++result;
}
}
}
return result;
}
有效解答
/**
* 5130. 等价多米诺骨牌对的数量
*
* @param dominoes
* @return
*/
public int numEquivDominoPairs(int[][] dominoes) {
int result = 0;
// 由于1 <= dominoes[i][j] <= 9,所以最大值不会超过99
int[] arr = new int[100];
for (int i = 0; i < dominoes.length; i++) {
// 以ij形式表示骨牌对(i,j),这个是翻转0度(即本身)
int index1=dominoes[i][0]*10+dominoes[i][1];
// 翻转180度后
int index2=dominoes[i][1]*10+dominoes[i][0];
if(index1 == index2){ // i==j,只要累加一次即可
result+=arr[index1];
arr[index1]++;
}else{
result+=arr[index1];
arr[index1]++;
arr[index2]++;
}
}
return result;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论