这是小川的第394次更新,第428篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第259题(顺位题号是1128)。给定多米诺骨牌列表,当且仅当(a == c
且b == d
)或(a == d
且b == c
),dominoes[i] = [a,b]
等价于dominoes[j] = [c,d]
,也就是说,一个多米诺骨牌可以旋转到等价于另一个多米诺骨牌。
返回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
02 第一种解法
暴力解法,直接使用两层循环,会超时。
public int numEquivDominoPairs(int[][] dominoes) {
int count = 0;
for (int i=0; i<dominoes.length; i++) {
for (int j=i+1; j<dominoes.length; j++) {
int a = dominoes[i][0], b = dominoes[i][1];
int c = dominoes[j][0], d = dominoes[j][1];
if ((a == c && b == d) || (a == d && b == c)) {
count++;
}
}
}
return count;
}
03 第二种解法
题目的意思是找可以配对的数组,也就是元素值相等的数组,为了降低时间复杂度,就必须将二维数组降为一维数组。
既然是值相等,那可不可以用加法或者乘法?
不行,因为加法或乘法不能保证唯一性。比如[1,6]和[2,3],做乘法后都等于6,但是这两数组明显不配对。
那我们把它变成一个两位数,较小的一个当做十位数,较大的当做个位数,这样一转换后,二维数组就变成了一维数组,此时题目也就变成了计数的问题。
因为数组元素的取值范围是[1,9]
,所以最大的两位数是99,最小的两位数是11,使用一个长度为100的整型数组即可。
最后遍历计数数组中的元素,计算对数,其实就是计算排列组合,有n个数,分两次取,总共有n*(n-1)
种可能,但是需要去重,因为i要小于j
,所以最后就是n*(n-1)/2
种可能,将每次的结果累加,最后返回即可。
public int numEquivDominoPairs2(int[][] dominoes) {
int[] count = new int[100];
for (int[] temp : dominoes) {
int num = Math.min(temp[0], temp[1])*10
+ Math.max(temp[0], temp[1]);
count[num]++;
}
int result = 0;
for (int num : count) {
result += num*(num-1)/2;
}
return result;
}
04 第三种解法
和第二种解法一样的处理逻辑,只是将计数数组换成HashMap
来处理。
public int numEquivDominoPairs3(int[][] dominoes) {
Map<Integer, Integer> map = new HashMap<Integer,Integer>();
for (int[] temp : dominoes) {
int num = Math.min(temp[0], temp[1])*10
+ Math.max(temp[0], temp[1]);
map.put(num, map.getOrDefault(num, 0)+1);
}
int result = 0;
for (Integer times : map.values()) {
result += times*(times-1)/2;
}
return result;
}
05 第四种解法
此解法同样利用HashMap
,但是HashMap
的key
是字符串,先转为一个两位数,然后再转成字符串。另外,计算配对的对数也有一点不同,是用累加来算的,不算最后的n,只从1算到n-1
,效果和前面用排列组合的一样。
public int numEquivDominoPairs4(int[][] dominoes) {
Map<String, Integer> map = new HashMap<String,Integer>();
int count = 0;
for (int[] temp : dominoes) {
StringBuilder sb = new StringBuilder();
sb.append(""+Math.min(temp[0], temp[1])
+ Math.max(temp[0], temp[1]));
String str = sb.toString();
if (map.containsKey(str)) {
count += map.get(str);
}
map.put(str, map.getOrDefault(str, 0)+1);
}
return count;
}
06 小结
算法专题目前已连续日更超过八个月,算法题文章265+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,在看、留言、转发就是对我最大的回报和支持!