LeetCode.914-一副牌中的X(X of a Kind

作者: 程序员小川 | 来源:发表于2019-06-13 08:39 被阅读8次

    这是悦乐书的第352次更新,第377篇原创

    01 看题和准备

    今天介绍的是LeetCode算法题中Easy级别的第214题(顺位题号是914)。在一副牌中,每张牌上都写有一个整数。

    当且仅当您可以选择X >= 2时才返回true,以便可以将整个牌组分成一组或多组牌,其中:

    • 每组都有X张牌。

    • 每组中的所有牌都具有相同的整数。

    例如:

    输入:[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]

    注意

    • 1 <= deck.length <= 10000

    • 0 <= deck[i] <10000

    02 第一种解法

    题目的意思是将数组deck中的元素进行分组,值相等的划分为同一组,每一组中的元素个数都相等,且大于等于2。我们可以使用一个HashMap,以deck中的元素为key,以其出现次数为value,对HashMapvalue值进行遍历。

    最理想的情况,HashMap中只有一组key-value,但测试用例中肯定不会这么轻易让你AC。来看几组例子分析下规律:

    {1,1,1,2,2,2,3,3} 
    {{1,1,1},{2,2,2},{3,3}} --> {3,3,2}
    
    {1,1,2,2,2,2,3,3,3,3,3,3} 
    {{1,1},{2,2,2,2},{3,3,3,3,3,3}} --> {2,4,6}
    

    第一个例子中,他们的最大公约数为1,即分组的组数存在奇偶分布的情况。

    第二个例子中,他们的最大公约数为2,即分组的组数都是偶数,并且对于其中的4个2和6个3,是还可以继续拆分的,4个2拆成两组2个2,6个3拆成三组2个3。

    因此,我们只需要判断HashMap中每对数据的最大公约数是不是等于1即可。

    public boolean hasGroupsSizeX(int[] deck) {
        if (deck.length < 2) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : deck) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int count = 0;
        for (Integer value : map.values()) {
            if (value < 2) {
                return false;
            }
            if (count == 0) {
                count = value;
            } else {
                if (count != value) {
                    int gcd = 1;
                    for (int i=1; i<= count || i<=value; i++) {
                        if (count%i == 0 && value%i == 0) {
                            gcd = i;
                        }
                    }
                    if (gcd == 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    

    03 第二种解法

    思路和第一种解法一样,只是将其中部分代码抽离了出来,并且简化了一些if-else判断。

    public boolean hasGroupsSizeX2(int[] deck) {
        if (deck.length < 2) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : deck) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int min = 10001;
        for (Integer num : map.values()) {
            min = Math.min(min, num);
        }
        if (min == 1) {
            return false;
        }
        for (Integer num : map.values()) {
            if (getGCD(min, num) == 1) {
                return false;
            }
        }
        return true;
    }
    
    public int getGCD(int a, int b) {
        int gcd = 1;
        for (int i=1; i<= a || i<=b; i++) {
            if (a%i == 0 && b%i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }
    

    04 第三种解法

    因为限定了数组deck中元素值范围,因此我们可以使用一个整型数组count来计算deck中各元素的出现次数,然后遍历count中的元素,求出他们的最大公约数,只要有一对数的最大公约数等于1,就直接返回false。

    public boolean hasGroupsSizeX3(int[] deck) {
        int[] count = new int[10001];
        for (int num : deck) {
            count[num]++;
        }
        int temp = -1;
        for (int num : count) {
            if (num > 0) {
                if (num < 2) {
                    return false;
                }
                if (temp == -1) {
                    temp = num;
                } else {
                    if (getGCD(temp, num) == 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    
    public int getGCD(int a, int b) {
        int gcd = 1;
        for (int i=1; i<= a || i<=b; i++) {
            if (a%i == 0 && b%i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }
    

    05 第四种解法

    对第三种解法,我们还可以再优化下,将求最大公约数的方法独立处理,并且用递归处理。

    public boolean hasGroupsSizeX4(int[] deck) {
        int[] count = new int[10001];
        for (int num : deck) {
            count[num]++;
        }
        int tem = count[deck[0]];
        for (int num : count) {
            if (num > 0) {
                tem = gcd(tem, num);
            }
        }
        return tem > 1;
    }
    
    /**
     * 利用递归求a和b的最大公约数
     * @param a
     * @param b
     * @return
     */
    public int gcd(int a, int b) {
        return a == 0 ? b : gcd(b%a, a);
    }
    

    06 小结

    算法专题目前已连续日更超过六个月,算法题文章220+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:LeetCode.914-一副牌中的X(X of a Kind

        本文链接:https://www.haomeiwen.com/subject/seadfctx.html