題目描述

思路

• 法一（哈希）：把每個domino都轉(zhuǎn)換成一個對象筒占，該對象重寫了hashCode和equals方法婚被，當兩個domino的兩個數(shù)一樣時認為這兩個domino相等（tips：hashCode的結(jié)果也應該滿足該條件）。遍歷一遍計下每個domino出現(xiàn)的次數(shù)為count，然后將每個count*(count-1)/2相加即為最終結(jié)果。
• 法二（二維轉(zhuǎn)一維）：觀察到dominoes[i][j]為1到9之間的數(shù)∧乎澹可以直接將domino轉(zhuǎn)化為一個100以內(nèi)的整數(shù)寞缝，這個整數(shù)的十位為domino中較大數(shù)，個位為domino中較小數(shù)仰泻。遍歷一遍該數(shù)組荆陆，進行轉(zhuǎn)化的同時使用一個int[100]數(shù)組記錄每個數(shù)出現(xiàn)的次數(shù)count。最終將每個count*(count-1)/2相加即為最終結(jié)果集侯。

哈希

java代碼如下

import java.util.HashMap;
import java.util.Map;

class Solution {
    class Domino {
        int a;
        int b;

        public Domino(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public int hashCode() {
            int hash = 17;
            hash = (hash + a * 31 + b * 31) * 31;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Domino) {
                Domino s = (Domino) obj;
                if ((s.a == this.a && s.b == this.b) || (s.a == this.b && s.b == this.a)) {
                    return true;
                } else {
                    return false;
                }
            }
            return super.equals(obj);
        }

    }

    public int numEquivDominoPairs(int[][] dominoes) {
        int length = dominoes.length;
        int res = 0;
        Map<Domino, Integer> repeatMap = new HashMap<>();
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int i = 0; i < length; i++) {
            Domino domino = new Domino(dominoes[i][0], dominoes[i][1]);
            if (repeatMap.containsKey(domino)) {
                int value = repeatMap.get(domino) + 1;
                repeatMap.put(domino, value);
            } else {
                repeatMap.put(domino, 1);
            }
        }

        for (Integer value : repeatMap.values()) {
            if (value > 1) {
                if (countMap.containsKey(value)) {
                    res += countMap.get(value);
                } else {
                    countMap.put(value, value * (value - 1) / 2);
                    res += countMap.get(value);
                }
            }
        }

        return res;
    }
}

執(zhí)行用時：13 ms, 在所有 Java 提交中擊敗了26.33%的用戶
內(nèi)存消耗：47.2 MB, 在所有 Java 提交中擊敗了96.09%的用戶

結(jié)果不好被啼，如果題目沒有說明1 <= dominoes[i][j] <= 9的話結(jié)果應該是挺不錯的。但是在這一條件下浅悉，有更好的方法趟据。

二維轉(zhuǎn)一維

java代碼如下

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] counts = new int[100];
        int length = dominoes.length;
        int res = 0;
        for (int i = 0; i < length; i++) {
            int num = transform(dominoes[i]);
            counts[num]++;
        }
        for (int i = 0; i < 100; i++) {
            int count = counts[i];
            if (count > 1) {
                res += count * (count - 1) / 2;
            }
        }
        return res;
    }

    public int transform(int[] nums) {
        int a = nums[0];
        int b = nums[1];
        int res = a > b ? a * 10 + b : b * 10 + a;
        return res;
    }
}

執(zhí)行用時：2 ms, 在所有 Java 提交中擊敗了97.76%的用戶
內(nèi)存消耗：48 MB, 在所有 Java 提交中擊敗了9.46%的用戶

ojbk