本文主要是介绍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; // 获取到二进制中的最右边的1if(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;}
};这篇关于LeetCode --- 413周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
