2023‐03‐19 第 337 场周赛

奇偶位数

• 第一题直接模拟 A

class Solution {
public:
    vector<int> evenOddBit(int n) {
        vector<int> res;
        
        int even = 0, odd = 0;
        
        vector<int> tem;
        
        while (n) {
            tem.push_back(n % 2);
            
            n /= 2;
        }
        
        for (int i = 0; i < tem.size(); i ++) {
            if (i % 2 == 0 && tem[i] == 1) odd ++;
            
            if (i % 2 != 0 && tem[i] == 1) even ++;
        }
        
        //reverse(tem.begin(), tem.end());
        
        res.push_back(odd);
        res.push_back(even);
        
        return res;
    }
};

检查骑士巡视方案

• 这道题也简单
• 很容易就想到思路
• 但最后被题目 每次从左上角开始检查 坑了一次罚时

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        unordered_map<int, int> al_row; // 记录数字的行数
        unordered_map<int, int> al_col; // 记录数字的列数
        
        for (int i = 0; i < grid.size(); i ++) {
            for (int j = 0; j < grid[i].size(); j ++) {
                int tem = grid[i][j];
                
                al_row[tem] = i;
                al_col[tem] = j;
            }
        }
        
        int n = grid.size();
        
        int idx_row = al_row[0];
        int idx_col = al_col[0];
        
        if (idx_row != 0 || idx_col != 0) return false;
        
        for (int i = 1; i < n * n; i ++) {
            int tem_row = al_row[i], tem_col = al_col[i];
            
            bool f1 = ((idx_row - 2) == tem_row && (idx_col - 1) == tem_col);
            bool f2 = ((idx_row - 2) == tem_row && (idx_col + 1) == tem_col);
            bool f3 = ((idx_row - 1) == tem_row && (idx_col - 2) == tem_col);
            bool f4 = ((idx_row - 1) == tem_row && (idx_col + 2) == tem_col);
            bool f5 = ((idx_row + 1) == tem_row && (idx_col - 2) == tem_col);
            bool f6 = ((idx_row + 1) == tem_row && (idx_col + 2) == tem_col);
            bool f7 = ((idx_row + 2) == tem_row && (idx_col - 1) == tem_col);
            bool f8 = ((idx_row + 2) == tem_row && (idx_col + 1) == tem_col);
            
            if (f1 || f2 || f3 || f4 || f5 || f6 || f7 || f8) {
                idx_col = tem_col, idx_row = tem_row;
            } else {
                return false;
            }
        }
        
        return true;
        
    }
};

美丽子集的数目

• 对子集题目的敏感度还是不够
• 看完想了想没有什么具体思路
• 子集型回溯

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        // 子集型回溯
        // 这种求子集的问题还是做的太少了

        int cnt[30001]{};

        int res = -1; // 去掉空集

        function<void(int)> dfs=[&](int i) {
            if (i == nums.size()) {
                res ++;
                return ;
            }

            // 不选
            dfs(i + 1);

            // 选
            int x = nums[i] + k; // 避免出现负数下标

            if (cnt[x - k] == 0 && cnt[x + k] == 0) {
                cnt[x] ++;
                dfs(i + 1);
                cnt[x] --;
            }
        };

        dfs(0);

        return res;
    }
};

执行操作后的最大MEX

• 这道题测试数据过了一半多
• 贪心的想法应该是没错的
• 但是思路有漏洞

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        sort(nums.begin(), nums.end());
        
        unordered_map<int, bool> cnt;
        
        for (int i = 0; i < nums.size(); i ++) {
            while (nums[i] < 0) nums[i] += value;
        }
        
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i ++) cnt[nums[i]] = 1;
        
        for (int i = nums.size() - 1; i >= 0; i --) {
            int tem_mod = nums[i] % value;
            
            int tem = nums[i] / value;
            
            if (tem <= 0) break;
            
            if (!cnt[tem_mod]) cnt[tem_mod] = 1, cnt[nums[i]] = -1;
        }
        
        int res = 0;
        
        for(int i = 0; i < cnt.size(); i ++) {
            if (!cnt[i]) {
                res = i;
                
                break;
            }
        }
        
        return res;
    }
};

正确思路

• 没想到这么简单
• 之前的大致的思路是对的 做取模运算 但是还是走偏了

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        unordered_map<int, int> cnt;

        for (int i = 0; i < nums.size(); i ++) {
            cnt[(nums[i] % value + value) % value] ++; // 取模的通用写法 可以避免 -4 % 5 = -4 这样的情况
        }

        int res = 0;

        while (cnt[res % value]) {
            cnt[res % value] --;

            res ++;
        }

        return res;
    }
};