readme.md

914. 卡牌分组

题目

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

此时，你需要选定一个数字 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. 1 <= deck.length <= 10000
2. 0 <= deck[i] < 10000

 

Python

class Solution:
    def hasGroupsSizeX(self, deck):
        dic = {}
        for num in deck:
            if num in dic:
                dic[num] += 1
            else:
                dic[num] = 1
        g = -1
        # 获取出现次数
        for v in dic.values():
            if g == -1:
                g = v
            else:
                g = self.gcd(g, v)
        return g >= 2

C++

class Solution {
  public:
    bool hasGroupsSizeX(vector<int> &deck) {
        map<int, int> dic;
        for (int num : deck) {
            dic[num] += 1;
        }
        int g = -1;
        for (auto v : dic) {
            if (g == -1) // g 给赋值第一个
                g = v.second;
            else
                g = gcd(g, v.second); // 一次判断最大公约数
        }
        return g >= 2; // 最大公约数只要大于 2 本题就是正确的
    }
    // 辗转相除法 获取最大公约数
    int gcd(int x, int y) { return x == 0 ? y : gcd(y % x, x); }
};

922. 按奇偶排序数组 II

题目

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

 

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

 

提示：

1. 2 <= A.length <= 20000
2. A.length % 2 == 0
3. 0 <= A[i] <= 1000

 

Python

借助数组求解

class Solution:
    def sortArrayByParityII(self, A: [int]) -> [int]:
        left = []
        for index, num in enumerate(A):
            if (num - index) % 2 != 0:
                if not left:
                    left.append(index)
                else:
                    if (num - A[left[-1]]) % 2 == 0:
                        left.append(index)
                    else:
                        A[index], A[left[-1]] = A[left[-1]], A[index]
                        left.pop()
        return A

双指针法

class Solution:
    def sortArrayByParityII(self, A: [int]) -> [int]:
        odd = 1
        even = 0
        length = len(A)
        while odd < length and even < length:
            print(odd, even)
            is_odd = (A[odd] - odd) % 2
            is_even = (A[even] - even) % 2
            if is_odd == 1 and is_even == 1:
                A[even], A[odd] = A[odd], A[even]
            if is_odd == is_even:
                odd += 2
                even += 2
            elif is_odd == 0:
                odd += 2
            elif is_even == 0:
                even += 2
        return A

C++

class Solution {
  public:
    vector<int> sortArrayByParityII(vector<int> &A) {
        vector<int> v;
        for (int i = 0; i < A.size(); i++) {
            if ((A[i] - i) % 2 != 0) {
                if (v.size() == 0) {
                    v.push_back(i);
                } else {
                    if ((A[i] - A[v[0]]) % 2 == 0) {
                        v.push_back(i);
                    } else {
                        cout << A[i] << " " << A[v[0]] << endl;
                        A[i] = A[i] + A[v[0]];
                        A[v[0]] = A[i] - A[v[0]];
                        A[i] = A[i] - A[v[0]];
                        cout << A[i] << " " << A[v[0]] << endl;
                        cout << endl;
                        v.erase(v.begin());
                    }
                }
            }
        }
        return A;
    }
};