关注、星标下方公众号，和你一起成长

作者 | 梁唐

(资料图片仅供参考)

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是老梁。

封面是我用Ai生成的，这样没有版权问题，感兴趣的同学可以关注下星球，之后会在星球里分享操作方法。

我们照惯例来看昨天的LeetCode周赛，这一场是LeetCode第337场，还是由LeetCode官方自己赞助自己举办。

排名前10的同学可以获得棒球帽，幸运排名的同学可以获得LeetCode扑克。

这一场比赛总体难度不大，主要的吐槽集中在第二三两题。

奇偶位数

给你一个 正整数 n。

用 even表示在 n的二进制形式（下标从 0开始）中值为 1的偶数下标的个数。

用 odd表示在 n的二进制形式（下标从 0开始）中值为 1的奇数下标的个数。

返回整数数组 answer，其中 answer = [even, odd]。

题解

签到题，考察二进制的基本用法。

classSolution{public:vectorevenOddBit(intn){vectorret(2,0);for(inti=0;i<10;i++){if(n&(1<

检查骑士巡视方案

骑士在一张 n x n的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角出发，并且访问棋盘上的每个格子 恰好一次。

给你一个 n x n的整数矩阵 grid，由范围 [0, n * n - 1]内的不同整数组成，其中 grid[row][col]表示单元格 (row, col)是骑士访问的第 grid[row][col]个单元格。骑士的行动是从下标 0开始的。

如果 grid表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

题解

这道题有两种做法，一种做法是记录下每一步的位置，然后比较相邻两步的间隔是否符合马的规则。如果存在两步之间的间距过大或过小，那么说明不合法。

很多人wa在了这题，因为没有注意到题目中说固定从左上角出发的条件。

老梁用的是第二种做法，从左上角出发，沿用跳马的规则，判断八个方向的坐标是否存在下一个下标。如果骑士能够有效巡视，那么一共要跳 次。只要中间有一次跳不成，则返回false。

这种做法需要我们使用一个数组记录跳马的八个方向，这个技巧我们之前多次在走迷宫等类似问题当中遇见过，就不过多说明了。更多细节可以参考代码。

classSolution{public:boolcheckValidGrid(vector>&grid){intn=grid.size();//跳马的八个方向intdir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,2},{1,-2},{2,-1},{2,1}};//从左上角出发intx=0,y=0;//当前下标为0intcur=0;for(inti=0;i=n||yy<0||yy>=n)continue;//如果刚好是下一个下标，则跳过去if(grid[xx][yy]==cur+1){flag=true;cur++;x=xx,y=yy;break;}}if(!flag)returnfalse;}returntrue;}};

美丽子集的数目

给你一个由正整数组成的数组 nums和一个 正整数 k。

如果 nums的子集中，任意两个整数的绝对差均不等于 k，则认为该子数组是一个 美丽子集。

返回数组 nums中 非空且 美丽的子集数目。

nums的子集定义为：可以经由 nums删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

题解

这道题我们观察一下数据范围会发现，nums数组当中最多20个元素。那么根据排列组合，我们可以知道子集的数量最多是 ，即 ，约等于一百万种。这个数据量不是很大，完全是可以枚举的。

比较简单粗暴的方式是通过二进制枚举，但这样的复杂度是 ，由于还多了一个 ，我们还要再乘上20，极端情况下的运算次数约为两千万次，差不多刚好是超时的边界。国际服的大佬就是用的这种方式通过的，然而当有些同学发现同样的代码，在国内服却无法通过，引来了大家的吐槽。

如果我们可以去掉一层枚举的复杂度，将复杂度降低到 ，那么就不会超时了。做到这点也很简单，二进制枚举的方法中枚举状态和遍历容器是分开的。如果我们可以在枚举状态的同时就判断状态是否合法， 那么就可以将复杂度降低到 了。简单来说，假设当前的子集是一个美丽子集，那么当我们遇到一个新的元素时，会有两种选择，一种是不加入集合，一种是加入集合。如果能够加入集合，我们就得到了一个新的子集，如果不加入则直接判断下一个元素。这是一个经典的搜索问题，我们可以用回溯法来解决。

由于每个元素的范围很小，最多只有1000，我们可以直接用一个长度为1000的数组来标记每个元素是否在子集当中出现过。这样可以进一步降低复杂度，不知道为啥，我用unordered_set也会超时，可能被卡常数了。

classSolution{public:intret=0;voiddfs(vector&nums,intn,intk,vector&st){if(n>=nums.size())return;intcur=nums[n];//如果cur-k没有在集合中出现过if(cur-k<0||!st[cur-k]){//标记出现，完美子集数量+1st[cur]=1;ret++;//递归dfs(nums,n+1,k,st);//回溯，清除标记st[cur]=0;}dfs(nums,n+1,k,st);}intbeautifulSubsets(vector&nums,intk){//排序之后，判断时只需要判断-k的元素是否存在即可，不排序也可以，就要判断-k和+ksort(nums.begin(),nums.end());vectorst(1010,0);dfs(nums,0,k,st);returnret;}};

执行操作后的最大 MEX

给你一个下标从 0开始的整数数组 nums和一个整数 value。

在一步操作中，你可以对 nums中的任一元素加上或减去 value。

classSolution{public:intfindSmallestInteger(vector&nums,intv){intn=nums.size();intcnt[v+5];//统计余数出现的次数memset(cnt,0,sizeofcnt);for(inti=0;i