413力扣周赛

3274. 检查棋盘方格颜色是否相同- 给你两个字符串 coordinate1 和 coordinate2代表 8 x 8 国际象棋棋盘上的两个方格的坐标。以下是棋盘的参考图。如果这两个方格颜色相同返回 true否则返回 false。分析问题由图知假设a、b… … 用 1、2… … 代表则黑色方格的行标和列表的奇偶性一定相同反之为白格。class Solution { public: bool check(string a) { int x a[0] - a 1, y a[1] - 0; return (x1) ^ (y1); } bool checkTwoChessboards(string c1, string c2) { return !(check(c1) ^ check(c2)); } };3275. 第 K 近障碍物查询有一个无限大的二维平面。 给你一个正整数 k 同时给你一个二维数组 queries 包含一系列查询 queries[i] [x, y] 在平面上坐标 (x, y) 处建一个障碍物数据保证之前的查询 不会 在这个坐标处建立任何障碍物。 每次查询后你需要找到离原点第 k 近 障碍物到原点的 距离 。 请你返回一个整数数组 results 其中 results[i] 表示建立第 i 个障碍物以后离原地第 k 近障碍物距离原点的距离。如果少于 k 个障碍物results[i] -1 。 注意一开始 没有 任何障碍物。 坐标在 (x, y) 处的点距离原点的距离定义为 |x| |y| 。 示例 1 输入queries [[1,2],[3,4],[2,3],[-3,0]], k 2 输出[-1,7,5,3] 解释 最初不存在障碍物。 queries[0] 之后少于 2 个障碍物。 queries[1] 之后 两个障碍物距离原点的距离分别为 3 和 7 。 queries[2] 之后障碍物距离原点的距离分别为 3 5 和 7 。 queries[3] 之后障碍物距离原点的距离分别为 335 和 7 。 示例 2 输入queries [[5,5],[4,4],[3,3]], k 1 输出[10,8,6] 解释 queries[0] 之后只有一个障碍物距离原点距离为 10 。 queries[1] 之后障碍物距离原点距离分别为 8 和 10 。 queries[2] 之后障碍物距离原点的距离分别为 6 8 和10 。 提示 1 queries.length 2 * 105 所有 queries[i] 互不相同。 -109 queries[i][0], queries[i][1] 109 1 k 105分析使用优先队列当队列大小达到k时弹出堆顶元素。需要注意的点是维护队列的操作顺序是先加入元素再弹出多余元素最后取top值。struct my_cmp{booloperator()(constpairint,inta,constpairint,intb)const{returnabs(a.first)abs(a.second)-abs(b.first)-abs(b.second)0;}};classSolution{public:vectorintresultsArray(vectorvectorintqs,int k){priority_queuepairint,int,vectorpairint,int,my_cmpq;int nqs.size();vectorintans;for(int i0;in;i){int tabs(qs[i][0])abs(qs[i][1]);q.push({qs[i][0],qs[i][1]});if(ik-1)q.pop();if(ik-1){pairint,inttpq.top();ans.push_back(abs(tp.first)abs(tp.second));}else{ans.push_back(-1);}}returnans;}};选择矩阵中单元格的最大得分给你一个由正整数构成的二维矩阵 grid。 你需要从矩阵中选择 一个或多个 单元格选中的单元格应满足以下条件 - 所选单元格中的任意两个单元格都不会处于矩阵的 同一行。 - 所选单元格的值 互不相同。 你的得分为所选单元格值的总和。 返回你能获得的 最大 得分。 示例 1 输入 grid [[1,2,3],[4,3,2],[1,1,1]] 输出 8 解释 选择上图中用彩色标记的单元格对应的值分别为 1、3 和 4 。 示例 2 输入 grid [[8,7,6],[8,3,2]] 输出 15 解释 选择上图中用彩色标记的单元格对应的值分别为 7 和 8 。 提示 1 grid.length, grid[i].length 10 1 grid[i][j] 100我想出的答案将矩阵中所有方格每一行存放按值从大到小排列枚举每一种符合答案的方案求最大。复杂度为nnn^nnn最大复杂度为101010^101010。本题需要注意的点是g的行数和列数不一定相等。constintN15;classSolution{public:int ans0,n,sum0;int ar[N];int g[N][N];voiddfs(int x,int y){if(xn){if(anssum){anssum;for(int i0;ix;i)coutar[i] ;coutendl;}return;}for(int iy;in;i){bool flfalse;ar[x]g[x][i];for(int j0;jx;j){if(ar[j]ar[x]){fltrue;break;}}if(!fl){sumg[x][i];dfs(x1,0);sum-g[x][i];}}}intmaxScore(vectorvectorintgt){ngt.size();for(int i0;in;i){for(int j0;jn;j)g[i][j]gt[i][j];}dfs(0,0);returnans;}};标答枚举每一个数再枚举所有符合条件的答案。要使用二维数组存储中间结果否则会超时。x-x的结果取决于x的二进制表示中最低位的值。classSolution{public:int n0,m0;mapint,intmp;vectorintnums;int memo[105][110];intdfs(vectorvectorintg,int pos,int rs){if(pos0)return0;int resmemo[pos][rs];if(res!-1)returnres;resdfs(g,pos-1,rs);// 枚举每行for(int tmp[nums[pos]],lb;t;t^lb){lbt-t;if(rslb)continue;resmax(res,dfs(g,pos-1,rs|lb)nums[pos]);}memo[pos][rs]res;returnres;}intmaxScore(vectorvectorintg){ng.size(),mg[0].size();for(int i0;i105;i)memset(memo[i],-1,sizeof memo[i]);for(int i0;in;i){for(int j0;jm;j){int xg[i][j];mp[x]|1i;}}for(auto[x,_]:mp){nums.push_back(x);}returndfs(g,nums.size()-1,0);}};3277. 查询子数组最大异或值给你一个由 n 个整数组成的数组 nums以及一个大小为 q 的二维整数数组 queries其中 queries[i] [li, ri]。 对于每一个查询你需要找出 nums[li..ri] 中任意 子数组 的 最大异或值。 数组的异或值 需要对数组 a 反复执行以下操作直到只剩一个元素剩下的那个元素就是 异或值 对于除最后一个下标以外的所有下标 i同时将 a[i] 替换为 a[i] XOR a[i 1] 。 移除数组的最后一个元素。 返回一个大小为 q 的数组 answer其中 answer[i] 表示查询 i 的答案。 示例 1 输入 nums [2,8,4,32,16,1], queries [[0,2],[1,4],[0,5]] 输出 [12,60,60] 解释 在第一个查询中nums[0..2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12所有异或值中的最大值。 在第二个查询中nums[1..4] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值为 60。 在第三个查询中nums[0..5] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值为 60。 示例 2 输入 nums [0,7,3,2,8,5,1], queries [[0,3],[1,5],[2,4],[2,6],[5,6]] 输出 [7,14,11,14,5] 解释 下标 nums[li..ri] 最大异或值子数组 子数组最大异或值 0 [0, 7, 3, 2] [7] 7 1 [7, 3, 2, 8, 5] [7, 3, 2, 8] 14 2 [3, 2, 8] [3, 2, 8] 11 3 [3, 2, 8, 5, 1] [2, 8, 5, 1] 14 4 [5, 1] [5] 5 提示 1 n nums.length 2000 0 nums[i] 231 - 1 1 q queries.length 105 queries[i].length 2 queries[i] [li, ri] 0 li ri n - 1classSolution{public:vectorintmaximumSubarrayXor(vectorintns,vectorvectorintq){int nns.size(),mq.size();vectorintans;for(int i0;im;i){int lq[i][0],rq[i][1],resns[r];for(int xl;xr;x){resmax(res,ns[x]);for(int yx1;yr;y){resmax(res,ns[x]^ns[y]);}}ans.push_back(res);}returnans;}};