大连科技学院官方网站的建设与放最近军事新闻

一、本周周赛总结

• 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 

参考链接