LeetCode --- 413周赛

题目列表

3274. 检查棋盘方格颜色是否相同

3275. 第 K 近障碍物查询

3276. 选择矩阵中单元格的最大得分

3277. 查询子数组最大异或值

一、检查棋盘方格颜色是否相同

题目给定两个字符串来表示两个方格的坐标，让我们判断这两个方格的颜色是否相同，这里我们要观察棋盘的颜色特征，我们就会发现奇数行的奇数列和偶数行的偶数列是黑色，其他都是白色，所以我们可以直接计算出每个方格的颜色，代码如下

class Solution {
public:
    bool checkTwoChessboards(string coordinate1, string coordinate2) {
        // 只要考虑坐标的奇偶性即可
        int x1 = (coordinate1[0] - 'a' + 1) % 2;
        int y1 = (coordinate1[1] - '0') % 2;
        int x2 = (coordinate2[0] - 'a' + 1) % 2;
        int y2 = (coordinate2[1] - '0') % 2;
        return (x1 == y1 && x2 == y2) || (x1 != y1 && x2 != y2);
    }
};

二、第k近障碍物查询

看到这个题目，我们就应该想到 215. 数组中的第K个最大元素 这个经典的题目，可以用堆来实现，这题也是同理，我们可以借助堆来维护第 k 近的障碍物，代码如下

class Solution {
public:
    vector<int> resultsArray(vector<vector<int>>& queries, int k) {
        int n = queries.size();
        vector<int> ans(n, -1);
        priority_queue<int> pq; // 大堆
        for(int i = 0; i < n; i++){
            int x = abs(queries[i][0]), y = abs(queries[i][1]);
            pq.push(x + y);
            if(pq.size() > k){
                pq.pop();
            }
            if(pq.size() == k) 
                ans[i] = pq.top();
        }
        return ans;
    }
};

三、选择矩阵中单元格的最大得分

这题的一般思路就是枚举每一行，依次决定每一行选什么数，同时记录下每一行选的数来判断剩余的行中不能选的数字有哪些。这个思路没问题，但是我们如何快速的记录每一行选的数呢？数字的范围为1~100，100个数的选择状态有 2^100 个，很显然会超时，那该如何做？

我们在仔细看一眼题目，除了枚举行，我们同样可以枚举选的数字，这样的好处是由于矩阵最多只有10行，我们可以用一个int类型的变量来记录哪些行被使用过了(共有2^10个状态)，大大降低了时间复杂度。

具体思路如下：我们从大到小枚举出现过的数，对于每一个数，我们可以选，也可以不选，如果选，那么我们就枚举它出现过的行有哪些，返回最大值即可，代码如下

class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        unordered_map<int, int> pos; // 预处理出每个数字出现的行有哪些
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                pos[grid[i][j]] |= (1<<i); // 用二进制来记录数字出现的行数有哪些
            }
        }
        vector<int> nums; // 记录grid中出现的数字
        for(auto &[x,_]: pos){
            nums.push_back(x);
        }
        ranges::sort(nums);
        
        int memo[nums.size()][1<<10];
        memset(memo, -1, sizeof(memo));
        function<int(int,int)> dfs = [&](int i, int j)->int{
            if(i < 0) return 0;
            if(memo[i][j] != -1) return memo[i][j];
            int res = dfs(i - 1, j); // 不选
            int x = nums[i]; // 选
            for(int t = pos[x], lb; t; t ^= lb){ // 用来枚举 x 出现过的行
                lb = t & -t; // 获取到二进制中的最右边的1
                if(j & lb) continue; // 如果结果不为 0，说明当前行已经被选过了
                res = max(res, dfs(i - 1, j | lb) + x);
            }
            return memo[i][j] = res;
        };
        return dfs(nums.size()-1, 0);
    }
};

四、查询子数组最大异或值

首先我们要去看看异或值的求法，并去找找规律，如下图

在算出所有区间的异或值后，我们还要计算出任意区间的子数组的最大异或值，依旧可以用动规来做，设 dp[i][j] 表示区间内的最大异或值，则 dp[i][j] = max( dp[i][j-1]，dp[i+1][j]，f[i][j] )，代码如下

class Solution {
public:
    vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), m = queries.size();
        vector<vector<int>> f(n, vector<int>(n));
        auto dp = f;
        // f[i][j] = f[i][j-1] ^ f[i+1][j]
        // dp[i][j] = max(dp[i][j-1], dp[i+1][j], f[i][j])
        for(int i = n - 1; i >= 0; i--){
            dp[i][i] = f[i][i] = nums[i];
            for(int j = i + 1; j < n; j++){
                f[i][j] = f[i][j-1] ^ f[i+1][j];
                dp[i][j] = max({dp[i][j - 1], dp[i+1][j], f[i][j]});
            }
        }
        vector<int> ans(m);
        for(int i = 0; i < m; i++){
            int l = queries[i][0], r = queries[i][1];
            ans[i] = dp[l][r];
        }
        return ans;
    }
};