当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--55--等价多米诺骨牌对的数量(J
给你一个由一些多米诺骨牌组成的列表 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) 的数量。
(题目来源：力扣（LeetCode）)
示例：
输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1
示例(自写，方便理解题目意思)：
输入：dominoes =[[1,1],[2,2],[1,1],[1,2],[1,2],[1,1],[3,1],[2,3],[1,4],[4,7],[3,2],[2,3]]
相同多米诺骨牌对：
[1,1],[1,1],[1,1]:3对
[1,2],[1,2]:1对
[2,3],[3,2],[2,3]:3对
输出：3+1+3=7
提示：
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9
1. 二维数组记录
package com.lxf.test;
public class NumEquivDominoPairs {
/**
* 解决方法一
* @param dominoes
* @return
*/
public int numEquivDominoPairs1(int[][] dominoes) {
//二维记录数组，将多米诺骨牌换成二维坐标
int[][] records = new int[9][9];
//等价的多米诺骨牌数量
int pairs=0;
for (int i = 0; i < dominoes.length; i++) {
//获取多米诺骨牌对应二维横坐标
int row=dominoes[i][0]-1;
//获取多米诺骨牌对应二维纵坐标
int col=dominoes[i][1]-1;
if(records[row][col]!=0){
//一类归类
//比如[1,3],[3,1] 两个都会归类到[1,3]下面
//同时将等价多米诺对数加上之前的数量(排列组合)
//比如：
// [[1,3],[3,1]]，在[3,1]归类时加上1
// [[1,3],[3,1],[1,3]]，在第二个[1,3]归类时加上2
// [[1,3],[3,1],[1,3],[3,1]]，在第二个[3,1]归类时加上3
pairs+=records[row][col]++;
}else if(records[col][row]!=0){
//二类归类
//比如[3,1],[1,3] 两个都会归类到[3,1]下面
//操作过程同一类归类
pairs+=records[col][row]++;
}else{
//每一个多米诺骨牌第一次初始化
records[row][col]=1;
}
}
return pairs;
}
/**
* 解决方法二
* @param dominoes
* @return
*/
public int numEquivDominoPairs2(int[][] dominoes) {
//二维记录数组，将多米诺骨牌换成二维坐标，扩大数组直接对应下标1-9，虽说浪费19个空间，但是理解起来容易
int[][] records = new int[10][10];
//等价的多米诺骨牌数量
int pairs=0;
for (int i = 0; i < dominoes.length; i++) {
if(records[dominoes[i][0]][dominoes[i][1]]!=0){
//一类归类
//比如[1,3],[3,1] 两个都会归类到[1,3]下面
//同时将等价多米诺对数加上之前的数量(排列组合)
//比如：
// [[1,3],[3,1]]，在[3,1]归类时加上1
// [[1,3],[3,1],[1,3]]，在第二个[1,3]归类时加上2
// [[1,3],[3,1],[1,3],[3,1]]，在第二个[3,1]归类时加上3
pairs+=records[dominoes[i][0]][dominoes[i][1]]++;
}else if(records[dominoes[i][1]][dominoes[i][0]]!=0){
//二类归类
//比如[3,1],[1,3] 两个都会归类到[3,1]下面
//操作过程同一类归类
pairs+=records[dominoes[i][1]][dominoes[i][0]]++;
}else{
//每一个多米诺骨牌第一次初始化
records[dominoes[i][0]][dominoes[i][1]]=1;
}
}
return pairs;
}
}
2. 交换+排序（评论区方法）
import java.util.Arrays;
class Solution {
public int numEquivDominoPairs(int[][] nums) {
int n = nums.length;
if(n == 0){
return 0;
}
int count = 0;
//交换
//将所有逆序多米诺骨牌改成正序
//比如[3,1]->[1,3]
for(int i = 0 ;i < n;i ++){
if(nums[i][0] > nums[i][1]){
int tmp = nums[i][0];
nums[i][0] = nums[i][1];
nums[i][1] = tmp;
}
}
//排序
Arrays.sort(nums , new Comparator<int[]>(){
public int compare(int[] m ,int[] n){
if(m[0] != n[0]){
return m[0] - n[0];
}else{
return m[1] - n[1];
}
}
});
//求连续长度 && 求和
for(int i = 0 ;i < n - 1;i ++){
int j = 0;
//找到等价多米诺骨牌的数量
while(i < n - 1 && nums[i][0] == nums[i + 1][0] && nums[i][1] == nums[i + 1][1]){
j ++;
i ++;
}
//等差数列求和
count += (1 + j) * j / 2;
}
//返回
return count;
}
}
3. 对称矩阵（评论区方法）
class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
int[][] a = new int[10][10];
int sum = 0, n;
for(int i = 0; i < dominoes.length; i++) a[dominoes[i][0]][dominoes[i][1]]++;
for(int i = 0; i < 10; i++){
for(int j = 0; j <= i; j++){
if (i != j){
n = a[i][j] + a[j][i];
}else{
n = a[i][j];
}
//求和公式
sum +=
