914.卡牌分组.md

914. 卡牌分组

url

题目

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

• 每组都有 X 张牌。
• 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。
输入：[1]
输出：false
解释：没有满足要求的分组。
输入：[1,1]
输出：true
解释：可行的分组是 [1,1]
输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]

方法

code

js

let hasGroupSizeX = deck => {
    // hash
    let map = new Map();
    deck.forEach(num => {
        if (map.has(num)) {
            map.set(num, map.get(num) + 1);
        } else {
            map.set(num, 1);
        }
    });
    // 最大公约数
    let t = 0;
    for (let value of map.values()) {
        t = gcd(t, value);
    }
    return t >= 2;
};
let gcd = (a, b) => {
    return b === 0 ? a : gcd(b, a % b);
};
console.log(hasGroupSizeX([1,2,3,4,4,3,2,1]))
console.log(hasGroupSizeX([1,1,1,2,2,2,3,3]))

go

func hasGroupSizeX(deck []int) bool {
	m := make(map[int]int, 0)
	for _, k := range deck {
		if v, ok := m[k]; ok {
			m[k] = v + 1
		} else {
			m[k] = 1
		}
	}
	// 最大公约数
	t := 0
	for _, k := range m {
		t = gcd(t, m[k])
	}
	return t >= 2
}
func gcd(a int, b int) int {
	if b == 0 {
		return a
	} else {
		return gcd(b, a % b)
	}
}

java

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        // hash
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num : deck) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        // 最大公约数
        int t = 0;
        for(int a : map.values()) {
            t = gcd(t, a);
        }
        return t >= 2;
    }
    // 最大公约数
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}