這是小川的第394次更新香伴，第428篇原創(chuàng)
01 看題和準(zhǔn)備
今天介紹的是LeetCode算法題中Easy級別的第259題（順位題號是1128）妻率。給定多米諾骨牌列表，當(dāng)且僅當(dāng)(a == c且b == d)或(a == d且b == c)，dominoes[i] = [a,b]等價于dominoes[j] = [c,d]指蚜，也就是說，一個多米諾骨牌可以旋轉(zhuǎn)到等價于另一個多米諾骨牌涨椒。
返回0 <= i < j < dominoes.length摊鸡，并且dominoes[i]等價于dominoes[j]的(i，j)對數(shù)蚕冬。
例如：
輸入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
輸出：1
注意：
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
02 第一種解法
暴力解法免猾，直接使用兩層循環(huán)，會超時囤热。
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 第二種解法
題目的意思是找可以配對的數(shù)組猎提，也就是元素值相等的數(shù)組，為了降低時間復(fù)雜度旁蔼，就必須將二維數(shù)組降為一維數(shù)組锨苏。
既然是值相等，那可不可以用加法或者乘法棺聊？
不行伞租，因為加法或乘法不能保證唯一性。比如[1,6]和[2,3]限佩，做乘法后都等于6葵诈，但是這兩數(shù)組明顯不配對。
那我們把它變成一個兩位數(shù)祟同，較小的一個當(dāng)做十位數(shù)作喘，較大的當(dāng)做個位數(shù)，這樣一轉(zhuǎn)換后耐亏，二維數(shù)組就變成了一維數(shù)組徊都，此時題目也就變成了計數(shù)的問題。
因為數(shù)組元素的取值范圍是[1,9]广辰，所以最大的兩位數(shù)是99暇矫，最小的兩位數(shù)是11，使用一個長度為100的整型數(shù)組即可择吊。
最后遍歷計數(shù)數(shù)組中的元素李根，計算對數(shù)，其實就是計算排列組合几睛，有n個數(shù)房轿，分兩次取，總共有n*(n-1)種可能，但是需要去重囱持，因為i要小于j夯接，所以最后就是n*(n-1)/2種可能，將每次的結(jié)果累加纷妆，最后返回即可盔几。
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 第三種解法
和第二種解法一樣的處理邏輯，只是將計數(shù)數(shù)組換成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是字符串，先轉(zhuǎn)為一個兩位數(shù)际邻，然后再轉(zhuǎn)成字符串芯丧。另外，計算配對的對數(shù)也有一點不同世曾，是用累加來算的缨恒，不算最后的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 小結(jié)
算法專題目前已連續(xù)日更超過八個月，算法題文章265+篇蕊程，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】椒袍、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞藻茂，獲取系列文章合集驹暑。
以上就是全部內(nèi)容，如果大家有什么好的解法思路辨赐、建議或者其他問題优俘，可以下方留言交流，在看掀序、留言帆焕、轉(zhuǎn)發(fā)就是對我最大的回報和支持！
