[LeetCode周赛复盘] 第 371 场周赛20231112
- 一、本周周赛总结
- 100120. 找出强数对的最大异或值 I
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 100128. 高访问员工
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 100117. 最大化数组末位元素的最少操作次数
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 100124. 找出强数对的最大异或值 II
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 参考链接
一、本周周赛总结
- T1 模拟。
- T2 模拟。
- T3 模拟贪心。
- T4 带删除的异或字典树+滑窗。
100120. 找出强数对的最大异或值 I
100120. 找出强数对的最大异或值 I
1. 题目描述
和T4相同,略。
2. 思路分析
看T4。
3. 代码实现
略。
100128. 高访问员工
100128. 高访问员工
1. 题目描述
2. 思路分析
- 把时间转化成分钟数,看a[i]-a[i-2]<60即可。
3. 代码实现
class Solution:def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:g = defaultdict(list)for x,y in access_times:g[x].append(y)ans = []def f(x):return int(x[:2])*60 + int(x[2:])for p, a in g.items():a = sorted(f(x) for x in a)for i in range(2,len(a)):if a[i] - a[i-2] < 60:ans.append(p)breakreturn ans
100117. 最大化数组末位元素的最少操作次数
100117. 最大化数组末位元素的最少操作次数
1. 题目描述
2. 思路分析
- 由于每次操作只能交换同位置的数,那我们尝试末尾是否交换,然后枚举每个位置是否交换即可。
3. 代码实现
class Solution:def minOperations(self, nums1: List[int], nums2: List[int]) -> int:n = len(nums1)def f(e1,e2):ans = 0if not (e1 == nums1[-1] and e2 == nums2[-1]):ans = 1 for x,y in zip(nums1[:-1], nums2[:-1]):if x <= e1 and y <= e2:continuex,y = y,x if x <= e1 and y <= e2:ans += 1else:return inf return ans ans = min(f(nums1[-1],nums2[-1]),f(nums2[-1],nums1[-1]))if ans == inf:return -1 return ans
100124. 找出强数对的最大异或值 II
100124. 找出强数对的最大异或值 II
1. 题目描述
2. 思路分析
T1的数据强化版。
- 公式可以转化,令x>=y,则|x-y|<=min(x,y)等价于
x-y <= y
,即x<=2y
- 我们把数组排序,然后滑窗处理,对于每个入窗的x,队头<x/2的数据都移除,那么窗口内的数据都是合法的y。
- 如何对窗口内的数据全部异或x去最大值呢?这可以用TrieXOR来处理复杂度lg(U)。
- 注意由于要出窗,字典树要支持删除。
3. 代码实现
class Solution:def maximumStrongPairXor(self, nums: List[int]) -> int:nums.sort()trie = {}def insert(v):cur = triefor i in range(20,-1,-1):p = v >> i & 1if p not in cur:cur[p] = {}cur = cur[p]cur[3] = cur.get(3,0) + 1def remove(v):cur = trie for i in range(20,-1,-1):p = v >> i & 1cur[p][3] -= 1if not cur[p][3]:del cur[p]breakcur = cur[p]def find(v):cur = trie ans = 0 for i in range(20,-1,-1):p = v>>i&1if p ^ 1 in cur:cur = cur[p^1]ans = ans << 1 | 1else:cur = cur[p]ans <<= 1return ansq = deque()ans = 0for v in nums:q.append(v)insert(v)while q[0]*2 < v: remove(q.popleft())ans = max(ans, find(v))return ans