1128. 等价多米诺骨牌对的数量.md

1128. 等价多米诺骨牌对的数量

• 基本思路

/*
 *  思路:
 *  对于两张多米诺股牌而言: [a, b] = [b, a]就会被认为两张牌是等价的
 *  A. 如果你知道[a, b](包括等价的[b, a])在数组中重复出现n次,那么[a, b]的骨牌对的数量是多少呢?答案是: (n - 1) + (n - 2) + ... 1 = (n * (n - 1)) / 2 (ps: 等差数列求和)
 * 
 *  B. 现在要是能统计出[a, b]重复出现了多少次就好了,这时候我们可以用map来完成这个统计.我们需要一种hash的方式,使它认为[a, b]和[b, a]对应的key是一样的就可以了.
 * 
 *  C. 有了上面的前提,我们可以统计每种骨牌重复出现的次数,再计算各自的骨牌对数量,累加起来就是我们要的答案
 */
function numEquivDominoPairs(dominoes: number[][]): number {
    // 第一步: 我们统计一下每种骨牌重复出现的次数
    let key: string, // 
        value: number, // 骨牌重复出现的次数
        count = 0;
    const map: Map<string, number> = dominoes.reduce((
        map: Map<string, number>,
        currentValue: number[]
    ) => {
        currentValue.sort((a, b) => a - b);
        // hash的方式: 较小的数值和较大的数值通过符号.连接组成唯一的key,这样[1, 3],[3, 1]它们的key都会是"1.3"
        key = `${currentValue[0]}.${currentValue[1]}`;
        value = map.get(key) || 0;
        map.set(key, ++value);
        return map;
    }, new Map<string, number>());

    // 第二步: 计算出所有种类的骨牌对的数量之和
    for (value of map.values()) {
        count += calculate(value);
    }
    return count;
};
/*
 * 已知某种骨牌重复出现的次数为n次,返回这种骨牌对的数量
 */
function calculate(n: number): number {
    if (n <= 1) {
        return 0;
    }
    return ((n - 1) * n) / 2;
}

• 更简洁的(启发于官方题解,思路是一样的,但是官方题解比我的更加简洁)

function numEquivDominoPairs(dominoes: number[][]): number {
    const table: { [key: string]: number } = Object.create(null);
    let count: number = 0;
    for (const [x, y] of dominoes) {
        const key: string = x < y ? `${x}:${y}` : `${y}:${x}`;
        const value: number = table[key] || 0;
        count += value;
        table[key] = value + 1;
    }
    return count;
};