[LeetCode周赛复盘] 第 337 场周赛20230319

• • 一、本周周赛总结
  • 二、 [Easy] 6319. 奇偶位数
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 三、[Medium] 6322. 检查骑士巡视方案
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 四、[Medium] 6352. 美丽子集的数目
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 五、[Hard] 6321. 执行操作后的最大 MEX
  • • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 六、参考链接

一、本周周赛总结

• 这周好可惜啊，T3有被恶心到，2e7如果能过我就第一页了。
• T1 模拟。
• T2 排序模拟。
• T3 dfs-注意状压有个拆位判断的常数n，2e7在力扣过不了。
• T4 计数模拟。
  

二、 [Easy] 6319. 奇偶位数

链接: 6319. 奇偶位数

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:def evenOddBit(self, n: int) -> List[int]:e = o = 0for i in range(11):if (n>>i) & 1:if i&1:o += 1else:e += 1return [e,o]

三、[Medium] 6322. 检查骑士巡视方案

链接: 6322. 检查骑士巡视方案

1. 题目描述

2. 思路分析

• 输入保证步数不重复，因此直接按步数排序，判断相邻的步数是可以走到的即可。
• 注意要求骑士从0开始，注意判断。

3. 代码实现

class Solution:def checkValidGrid(self, grid: List[List[int]]) -> bool:n = len(grid)a = []for i,row in enumerate(grid):for j,v in enumerate(row):a.append((v,i,j))a.sort()if a[0] != (0,0,0):return Falsedef ok(x,y,j,k):if abs(x-j) == 1 and abs(y-k) == 2:return Trueif abs(x-j) == 2 and abs(y-k) == 1:return Truereturn Falsefor (_,x,y),(_,j,k) in pairwise(a):if not ok(x,y,j,k):return Falsereturn True

四、[Medium] 6352. 美丽子集的数目

链接: 6352. 美丽子集的数目

1. 题目描述

2. 思路分析

• dfs.
• 看到数据量，算了一下状压是2e7以为能过，没想到lc的评测机这么垃圾。
• 这里注意，dfs虽然极限数据剪枝失败，但是由于可以继承之前的状态Counter()，不需要每个状态都拆位一次判断，因此可以省掉一层n，复杂度在1e6。

3. 代码实现

class Solution:def beautifulSubsets(self, nums: List[int], k: int) -> int:nums.sort()n = len(nums)ans = 0s = Counter()def dfs(i):if i == n:nonlocal ansans += 1return v = nums[i]if s[v-k] == 0 and s[v+k] == 0:s[v] += 1dfs(i+1)s[v] -= 1dfs(i+1)dfs(0)return ans - 1

五、[Hard] 6321. 执行操作后的最大 MEX

链接: 6321. 执行操作后的最大 MEX

1. 题目描述

2. 思路分析

• 在可以任意次数加减value的情况下，每个数x都可以变成 x+y*value，value相当于一个模数。
• 那么从0开始向大遍历，看看这个数能否从已知里来，显然需要同余的数里来。
• 把所有同余的数Counter到一起即可。

3. 代码实现

class Solution:def findSmallestInteger(self, nums: List[int], value: int) -> int:n = len(nums)cnt = Counter()for v in nums:cnt[v%value] += 1ans = 0 while cnt[ans%value]> 0:cnt[ans%value]-=1ans += 1return ans       

六、参考链接