Java 第 30 课 914. 卡牌分组 904. 水果成篮

• [914. 卡牌分组](https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/)
• [904. 水果成篮](https://leetcode-cn.com/problems/fruit-into-baskets/)

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:        
        d = defaultdict(int)
        for i in deck: d[i] += 1
        x = min(d.values())
        if x == 1:return False        
        for i in range(2, x + 1):
            for j in d.values():
                if j % i: break
            else: return True                
        return False

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {        
        int[] counter = new int[10000]; // 计数
        for (int num: deck) {counter[num]++;}        
        int x = 0; // 迭代求多个数的最大公约数
        for(int cnt: counter) {
            if (cnt > 0) {
                x = gcd(x, cnt); 
                if (x == 1) return false; // 如果某步中gcd是1，直接返回false                
            }
        }
        return x >= 2;
    }    
    // 辗转相除法
    private int gcd (int a, int b) {return b == 0 ? a : gcd(b, a % b);}
}

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        d, k, res, left = defaultdict(int), 2, 0, 0
        for i, f in enumerate(fruits):
            if d[f] == 0: k -= 1
            d[f] += 1
            # while k == -1: # 更新 res
            if k < 0: # 不需要 res
                x = fruits[left]
                d[x] -= 1
                if d[x] == 0: k += 1
                left += 1
            #res = max(res, i-left+1)
        #return res
        return len(fruits) - left

class Solution {
    public int totalFruit(int[] fruits) {        
        int n = fruits.length, res = 0, left = 0, k = 2;
        int[] d = new int[n + 1];      
        for (int i = 0; i < n; i++) {
            int x = fruits[i];
            if (d[x] == 0) k--;
            d[x]++;
            while (k == -1) { 
                int y = fruits[left];
                d[y]--;
                if (d[y] == 0) k++;
                left++;
            }
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}