LeetCode 第 218 场周赛题解

第 218 场周赛（如果喜欢记得点赞并关注作者噢~~~）

题目1：5617. 设计 Goal 解析器

思路：模拟

代码：

class Solution {
public:
    string interpret(string s) {
        int n = s.size();
        int i = 0;
        string ret = "";
        while(i < n) {
            if(s[i] == '(' && s[i + 1] == ')') {
                i += 2;
                ret += "o";
            } else if(s[i] == '(') {
                i += 4;
                ret += "al";
            } else {
                i++;
                ret += "G";
            }
        }
        return ret;
    }
};

复杂度分析：

题目2：5618. K 和数对的最大数目

思路：哈希表

代码：

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int ret = 0;
        for(int x : nums) {
            if(mp[k - x]) {
                mp[k - x]--;
                ret++;
            } else {
                mp[x]++;
            }
        }
        return ret;
    }
};

复杂度分析：

题目3：5620. 连接连续二进制数字

思路：模拟

代码：

class Solution {
public:
    const int M = 1e9 + 7;
    int concatenatedBinary(int n) {
        int ret = 0;
        int p = 1;
        for (int i = 1; i <= n; ++i) {
            while (p <= i) {	// 相当于求log(i)
                p *= 2;
            }
            ret = ((long long)ret * p + i) % M;
        }
        return ret;
    }
};

复杂度分析：

题目4：5619. 最小不兼容性

思路：状压DP

代码：

const int INF = 0x3f3f3f3f;
int memo[65536], v[16];

class Solution {
    int n, k, sz;
    vector<int> nums;
    int solve(int state) {
        if (memo[state] != -1)
            return memo[state];
        
        // 边界条件：当前集合刚好包含n/k个元素，不需要继续划分
        if (__builtin_popcount(state) == sz) {
            int idx = 0;
            for (int i = 0; i < n; ++i) {
                if (state & (1 << i)) {
                    // 将包含的元素存入分组
                   v[idx++] = i;
                }
        	}
            for (int i = 0; i + 1 < sz; ++i) {
                // 一个分组有两数相同，则说明是不满足要求的分组
                if (nums[v[i]] == nums[v[i + 1]]) {
                    return memo[state] = INF;
                }
            }
            return memo[state] = nums[v[n / k - 1]] - nums[v[0]];
        }
        int ans = INF;
        
        // 优化二：子集枚举优化
        for (int sub = state - 1; sub; sub = (sub - 1) & state) {
            if (__builtin_popcount(sub) % sz != 0)
                continue;
            // left 和 right 分别表示将当前集合再分为两个子集
            int left = solve(sub);
            
            // 优化三：如果左边的最优值已经达到了当前总和的最优值，则不需要继续计算右边。
            if (left >= ans)
                continue;
            int right = solve(state ^ sub);
            ans = min(ans, left + right);
        }
        return memo[state] = ans;
    }

public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        n = nums.size();
        sz = n / k;
        
        // 优化一：每个子集的大小为1，不兼容性显然为0，总和也是0。
        // 这种情况的筛除非常重要，因为它需要最多的枚举次数。
        if (sz == 1)
            return 0;
        
        sort(nums.begin(), nums.end());
        vector<int> cnt(n + 1);
        for (int num : nums) {
            // 记录每个数字出现的次数，若大于组数则说明不能分组
            cnt[num]++;
            if (cnt[num] > k)
                return -1;
        }
        this->k = k;	// 更新全局变量
        this->nums = nums;
        for (int i = 0; i < (1 << n); ++i)
            memo[i] = -1; 
        return solve((1 << n) - 1);
    }
};