LeetCode 914. 卡牌分组 (Java版; Easy)

川长思鸟来 2023-07-18 12:36 4阅读 0赞

### [welcome to my blog][] ###

## LeetCode 914. 卡牌分组 (Java版; Easy) ##

#### 题目描述 ####

给定一副牌，每张牌上都写着一个整数。
    
    此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
    
    每组都有 X 张牌。
    组内所有的牌上都写着相同的整数。
    仅当你可选的 X >= 2 时返回 true。
    
     
    
    示例 1：
    
    输入：[1,2,3,4,4,3,2,1]
    输出：true
    解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
    示例 2：
    
    输入：[1,1,1,2,2,2,3,3]
    输出：false
    解释：没有满足要求的分组。
    示例 3：
    
    输入：[1]
    输出：false
    解释：没有满足要求的分组。
    示例 4：
    
    输入：[1,1]
    输出：true
    解释：可行的分组是 [1,1]
    示例 5：
    
    输入：[1,1,2,2,2,2]
    输出：true
    解释：可行的分组是 [1,1]，[2,2]，[2,2]
    
    提示：
    
    1 <= deck.length <= 10000
    0 <= deck[i] < 10000

#### 第一次做; 核心: 1) 找出数组中所有元素的最大公因数, 如果最大公因数大于1, 说明可以满足条件; 如果最大公因数等于1, 说明不能满足条件 ####

class Solution { 
        public boolean hasGroupsSizeX(int[] deck) { 
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int a : deck){ 
                map.put(a, map.getOrDefault(a, 0)+1);
            }
            int res = 0;
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){ 
                int tmp = entry.getValue();
                if(tmp==1){ 
                    return false;
                }
                res = gcd(tmp, res);
                if(res==1){ 
                    return false;
                }
            }
            return true;
        }
    
        private int gcd(int a, int b){ 
            int tmp;
            while(b!=0){ 
                tmp = a;
                a = b;
                b = tmp%b;
            }
            return a;
        }
    }

#### 第一次做; 核心: 1) \{2,2,3,3\}是最普通的案例, \{2,2,3,3,3,3\}是特殊案例, \{2,2,2,2,3,3,3,3,3,3\}是更特殊的案例, 需要用到求最大公因数 ####

class Solution { 
        public boolean hasGroupsSizeX(int[] deck) { 
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int a : deck){ 
                map.put(a, map.getOrDefault(a, 0)+1);
            }
            int count = map.get(deck[0]);
            int min = deck.length;
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){ 
                int tmp = entry.getValue();
                if(tmp==1){ 
                    return false;
                }
                min = Math.min(min, tmp);
            }
            //1,1,2,2,2,2也是正确的!
            //1,1,1,1,2,2,2,2,2,2也是正确的!
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){ 
                int tmp = entry.getValue();
                if(tmp%min!=0){ 
                    int cur = gcd(min, tmp);
                    if(cur == 1){ 
                        return false;
                    }
                    min = cur;
                }
            }
            return true;
        }
    
        //求最大公因数: 递归版
        private int gcd(int a, int b){ 
            return b==0? a : gcd(b, a%b);
        }
        
        //求最大公因数: 迭代版
        private int gcd2(int a, int b){ 
            int tmp;
            while(b!=0){ 
                tmp = a;
                a = b;
                b = tmp%b;
            }
            return a;
        }
    }

[welcome to my blog]: https://littlehaes.com