周赛题解

337 周（2023.3.19）

奇偶位数

题目大意

给你任意正整数，分别求出在其二进制表示中，在偶数位和奇数位上 1 的个数。

移位运算求每一位

将二进制的 1 不断像右移，与 n 做与运算并用数组保存下来。之后遍历数组求出解。

vector<int> getBit(int n)
{
    vector<int> bits(32, 0);
    int tmp = 1;

    for (int i = 0; i < 31; ++i)
    {
        if (n & tmp)
            bits[i] = 1;
        tmp <<= 1;
    }

    return bits;
}
    
vector<int> evenOddBit(int n) 
{
    vector<int> bits = getBit(n);
    int even = 0, odd = 0;
    for (int i = 0; i < 32; ++i)
    {
        if (bits[i] == 1)
        {
            if (i % 2 == 0)
                ++even;
            else
                ++odd;
        }
    }

    return {even, odd};
}

掩码运算 + __builtin_popcount()

__builtin_popcount() 是 C++ GCC 编译器中内置的计算 unsigned int 数中 1 的个数的函数。对应还有：

• __builtin_popcountl()：对应 unsigned long
• __builtin_popcountll()：对应 unsigned long long

vector<int> evenOddBit(int n) 
{
    int mask = 0x55555555;
    return {__builtin_popcount(n & mask), __builtin_popcount(n & (mask << 1))};    
}

在 C20 标准中，库 <bit> 中新增了 std::popcount() 该函数会显式的要求 传入参数必须是无符号数，这样更加安全。

检查骑士巡视方案

题目大意

给你一个 n * n 大小的棋盘数组矩阵，数组中存储对应位置的巡视顺序序号。问现有一个国际象棋骑士，能否按照序号从小到大，从左上角出发，走完全部格子且每次移动都符合规则。

哈希

遍历一次数组，将每个序号对应的坐标存入哈希表。之后从 1 开始不断比较当前与上一个位置的横纵坐标差是否符合规则。

需要注意的是，根具题意序号 0 必须在左上角，所以遍历前要判断一下特例

bool checkValidGrid(vector<vector<int>>& grid)
{
    if (grid[0][0] != 0) return false;
    
    unordered_map<int, pair<int, int>> pos;
    int size = (int) grid.size();
s
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            pos[grid[i][j]].first = i;
            pos[grid[i][j]].second = j;
        }
    }
    int n = size * size;
    pair<int, int> pre = pos[0];
    for (int i = 1; i < n; ++i)
    {
        pair<int, int> tmp = pos[i];
        if (abs(tmp.first - pre.first) == 1 && abs(tmp.second - pre.second) == 2)
        {
            pre = tmp;
            continue;
        }
        if (abs(tmp.first - pre.first) == 2 && abs(tmp.second - pre.second) == 1)
        {
            pre = tmp;
            continue;
        }

        return false;
    }

    return true;
}

美丽子集的数目

题目大意

给你一个数组，和一个数 k，找到满足：子集内任意数绝对值之差不等于 k 的子集数量。有相同的数，但是对应索引不同的子集视作不同子集。

哈希 + DFS 回溯

最开始想这道题的时候太执着于想着直接判断子集内任意数之差符不符合题目定义了。

其实换一种思维，只需要判断，当前待选择的数 ± k 是否能够在哈希中找到，就可以判断是否能选择当前的数了。

int beautifulSubsets(vector<int>& nums, int k) 
{
    int res = 0;
    unordered_map<int, bool> selected;
	
    // 简洁写法：匿名函数传给函数指针
    function<void(int)> dfs = [&](int cur)
    {
        for (int i = cur; i < nums.size(); ++i)
        {
            // 判断之前是否选中过不符合规则的数
            if (!selected[nums[i]-k] && !selected[nums[i]+k])
            {
                ++res; selected[nums[i]] = true;
                dfs(i+1);
                selected[nums[i]] = false;
            }
        }
    };

    dfs(0);
    return res;
}