第 337 场周赛

6319. 奇偶位数

位运算，也可以转换为字符串查找。

Python 和 JavaScript 内置支持直接转换为二进制字符串查找，C/C++ 编译器/库内置函数 __builtin_popcount() 支持计数 $1$ 的个数，其他多数语言都有函数库支持直接操作。

class Solution {
public:
    vector<int> evenOddBit(int n) {
        int even = 0, odd = 0;
        int mask = 0;
        while (n) {
            // 如果是 1
            if (n & 1) {
                if (mask & 1) {
                    odd += 1;
                } else {
                    even += 1;
                }
            }
            n >>= 1;
            mask += 1;
        }
        return {even, odd};
    }
};

内置函数 __builtin_popcount() 计算，（C++ 20 正式支持了 std::popcount）：

class Solution {
public:
    vector<int> evenOddBit(int n) {
        const int MASK = 0x5555;
        return {__builtin_popcount(n & MASK), __builtin_popcount(n & (MASK >> 1))};
    }
};

6322. 检查骑士巡视方案

遍历 + 模拟，遍历数组得到每次跳跃的顺序，然后模拟跳跃，如果发现不合法就返回 false，最后返回 true。

跳跃条件可以概况为下面的公式，其中 $x_1$、$x_2$ 代表前后两次的位置。

$$|x_1 - x_2| = 1 \text{ and } |y_1 - y_2| = 2$$

或者

$$|x_1 - x_2| = 2 \text{ and } |y_1 - y_2| = 3$$

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        // 将每个位置保存下来
        vector<pair<int, int>> order(m * n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                order[grid[i][j]] = {i, j};
            }
        }
        // 如果第一个位置不是 0，返回 false
        if (order[0].first != 0 || order[0].second != 0) return false;
        for (int i = 1; i < n * m; ++i) {
            int x1 = order[i - 1].first;
            int y1 = order[i - 1].second;
            int x2 = order[i].first;
            int y2 = order[i].second;
            // 条件是 |x1 - x2| = 1 && |y1 - y2| == 2 或交换
            if (!((abs(x1 - x2) == 1 && abs(y1 - y2) == 2) ||
                (abs(x1 - x2) == 2 && abs(y1 - y2) == 1))) {
                return false;
            }
        }
        return true;
    }
};

6352. 美丽子集的数目

回溯搜索，或是 DFS，每次创建临时数组，不包括最后一个数字，然后计算不包括最后一个数字的美丽子集数目（递归过程），然后弹出最后一个数字。

TODO 每次创建数组带来巨大开销，可优化空间复杂度，并且可使用 DP 优化时间复杂度。

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        int n = (int)nums.size();
        // 特殊情况直接返回
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return abs(nums[0] - nums[1]) == k ? 2 : 3;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            // 创建临时数组，保存可以和最后一个数字在一个子集的数字
            vector<int> tmp;
            for (int j = 0; j < n - i - 1; ++j) {
                if (abs(nums[n - i - 1] - nums[j]) != k) tmp.push_back(nums[j]);
            }
            // 递归查找，结果是包含最后一个数字的子集数量，加上 1 是只有最后一个数字的集合
            res += beautifulSubsets(tmp, k) + 1;
        }
        return res;
    }
};

6321. 执行操作后的最大 MEX

遍历，由于可以进行任意次操作，最终都能得到 nums[i] % value 的值即可，然后统计，出现次数最少的那个就是最终结果。

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        int* counts = new int[100003];
        memset(counts, 0, sizeof(int) * 100003);
        // C++ 的取模结果可能为负，而 Python 不包含
        for (int v : nums) {
            int index = v % value;
            if (index < 0) {
                index += value;
            }
            ++counts[index];
        }
        // 计算最小值和最小位置
        int min_pos = 0;
        int min_count = counts[0];
        for (int i = 1; i < value; ++i) {
            if (counts[i] < min_count) {
                min_count = counts[i];
                min_pos = i;
            }
        }
        return value * min_count + min_pos;
    }
};

Python 做法更简洁（双百解法）：

class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        ct = Counter(x % value for x in nums)
        min_pos = 0
        min_value = ct[0]
        for i in range(value):
            if ct[i] < min_value:
                min_value = ct[i]
                min_pos = i
        return value * min_value + min_pos

C++ 的使用迭代器的简洁版本（效率不会比一般解法高），关于迭代器减法的相关信息可参考 Stackoverflow：

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        vector<int> counts(value);
        for (int i = 0; i < nums.size(); ++i)
            counts[((nums[i] % value) + value) % value]++;
        int k = min_element(counts.begin(), counts.end()) - counts.begin();
        return counts[k] * value + k;
    }
};