leetcode weekly contes 371

周赛题目还算不算，虽然晚了半个小时，还好都 AK 了。T4也算是经典的题目了，基本上看到就被秒杀的题目。

100120. 找出强数对的最大异或值 I

给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：

• |x - y| <= min(x, y)

你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。

返回数组 nums 所有可能的强数对中的 最大 异或值。

注意，你可以选择同一个整数两次来形成一个强数对。

示例 1：

输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。

示例 2：

输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。

示例 3：

输入：nums = [5,6,25,30]
输出：7
解释：数组 nums 中有 6 个强数对：(5, 5), (5, 6), (6, 6), (25, 25), (25, 30) 和 (30, 30) 。
这些强数对中的最大异或值是 25 XOR 30 = 7 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 5 XOR 6 = 3 。

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 100

地址

https://leetcode.cn/contest/weekly-contest-371/problems/maximum-strong-pair-xor-i/

题意

枚举

思路

1. 直接枚举所有的数对 $x,y$, 找到最大的 $x \oplus y$ 的最大值。
2. 复杂度分析：

• 时间复杂度：$O(n^2)$，其中 $n$ 表示给定的数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        res = 0
        for x in nums:
            for y in nums:
                if abs(x - y) <= min(x, y):
                    res = max(res, x ^ y)     
        return res

100128. 高访问员工

给你一个长度为 n 、下标从 0 开始的二维字符串数组 access_times 。对于每个 i（0 <= i <= n - 1 ），access_times[i][0] 表示某位员工的姓名，access_times[i][1] 表示该员工的访问时间。access_times 中的所有条目都发生在同一天内。

访问时间用 四位 数字表示， 符合 24 小时制 ，例如 "0800" 或 "2250" 。

如果员工在 同一小时内 访问系统 三次或更多 ，则称其为 高访问 员工。

时间间隔正好相差一小时的时间 不 被视为同一小时内。例如，"0815" 和 "0915" 不属于同一小时内。

一天开始和结束时的访问时间不被计算为同一小时内。例如，"0005" 和 "2350" 不属于同一小时内。

以列表形式，按任意顺序，返回所有 高访问 员工的姓名。

示例 1：

输入：access_times = [["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]
输出：["a"]
解释："a" 在时间段 [05:32, 06:31] 内有三条访问记录，时间分别为 05:32 、05:49 和 06:21 。
但是 "b" 的访问记录只有两条。
因此，答案是 ["a"] 。

示例 2：

输入：access_times = [["d","0002"],["c","0808"],["c","0829"],["e","0215"],["d","1508"],["d","1444"],["d","1410"],["c","0809"]]
输出：["c","d"]
解释："c" 在时间段 [08:08, 09:07] 内有三条访问记录，时间分别为 08:08 、08:09 和 08:29 。
"d" 在时间段 [14:10, 15:09] 内有三条访问记录，时间分别为 14:10 、14:44 和 15:08 。
然而，"e" 只有一条访问记录，因此不能包含在答案中，最终答案是 ["c","d"] 。

示例 3：

输入：access_times = [["cd","1025"],["ab","1025"],["cd","1046"],["cd","1055"],["ab","1124"],["ab","1120"]]
输出：["ab","cd"]
解释："ab"在时间段 [10:25, 11:24] 内有三条访问记录，时间分别为 10:25 、11:20 和 11:24 。
"cd" 在时间段 [10:25, 11:24] 内有三条访问记录，时间分别为 10:25 、10:46 和 10:55 。
因此，答案是 ["ab","cd"] 。

提示：

• 1 <= access_times.length <= 100
• access_times[i].length == 2
• 1 <= access_times[i][0].length <= 10
• access_times[i][0] 仅由小写英文字母组成。
• access_times[i][1].length == 4
• access_times[i][1] 采用24小时制表示时间。
• access_times[i][1] 仅由数字 '0' 到 '9' 组成。

地址

https://leetcode.cn/contest/weekly-contest-371/problems/high-access-employees/

题意

枚举

思路

1. 题目要求找到不超过存在在不到一时间内访问超过三次的员工，首先我们需要处理的是将 $24$ 小时时间转化为分钟，然后将每个员工的访问时间按照从小到到大进行排序，如果出现连续三次的间隔小于 $60$，则该员工符合题目要求。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。

代码

class Solution:
    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
        cnt = defaultdict(list)
        for name, time in access_times:
            cnt[name].append(int(time[:2]) * 60 + int(time[2:]))
        
        ans = []
        for k, v in cnt.items():
            v.sort()
            if any(v[i] - v[i - 2] < 60 for i in range(2, len(v))):
                ans.append(k)
        return ans

2934. 最大化数组末位元素的最少操作次数

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，这两个数组的长度都是 n 。

你可以执行一系列 操作（可能不执行）。

在每次操作中，你可以选择一个在范围 [0, n - 1] 内的下标 i ，并交换 nums1[i] 和 nums2[i] 的值。

你的任务是找到满足以下条件所需的 最小 操作次数：

• nums1[n - 1] 等于 nums1 中所有元素的 最大值 ，即 nums1[n - 1] = max(nums1[0], nums1[1], ..., nums1[n - 1]) 。
• nums2[n - 1] 等于 nums2 中所有元素的 最大值 ，即 nums2[n - 1] = max(nums2[0], nums2[1], ..., nums2[n - 1]) 。

以整数形式，表示并返回满足上述 全部 条件所需的 最小 操作次数，如果无法同时满足两个条件，则返回 -1 。

示例 1：

输入：nums1 = [1,2,7]，nums2 = [4,5,3]
输出：1
解释：在这个示例中，可以选择下标 i = 2 执行一次操作。
交换 nums1[2] 和 nums2[2] 的值，nums1 变为 [1,2,3] ，nums2 变为 [4,5,7] 。
同时满足两个条件。
可以证明，需要执行的最小操作次数为 1 。
因此，答案是 1 。

示例 2：

输入：nums1 = [2,3,4,5,9]，nums2 = [8,8,4,4,4]
输出：2
解释：在这个示例中，可以执行以下操作：
首先，选择下标 i = 4 执行操作。
交换 nums1[4] 和 nums2[4] 的值，nums1 变为 [2,3,4,5,4] ，nums2 变为 [8,8,4,4,9] 。
然后，选择下标 i = 3 执行操作。
交换 nums1[3] 和 nums2[3] 的值，nums1 变为 [2,3,4,4,4] ，nums2 变为 [8,8,4,5,9] 。
同时满足两个条件。 
可以证明，需要执行的最小操作次数为 2 。 
因此，答案是 2 。

示例 3：

输入：nums1 = [1,5,4]，nums2 = [2,5,3]
输出：-1
解释：在这个示例中，无法同时满足两个条件。
因此，答案是 -1 。

提示：

• 1 <= n == nums1.length == nums2.length <= 1000
• 1 <= nums1[i] <= 109
• 1 <= nums2[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-371/problems/minimum-operations-to-maximize-last-elements-in-arrays/

题意

模拟

思路

1. 题目看齐来很长，但实际该题目很简单，无论如何交换，最末位数只有两种情况，数组的最后两个元素要么不交换，在这两种情况下分别计算前 $n-1$ 个元素都小于最大元素所需的最少交换次数即可。

• 时间复杂度：$O(n)$，其中$n$ 表示数组的长度；
• 空间复杂度：$O(1)$；

代码

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        def calc(val1, val2):
            res = 0
            for x, y in zip(nums1, nums2):
                if x > val1 or y > val2:
                    if y > val1 or x > val2:
                        return inf
                    res += 1
            return res
        
        ans = min(calc(nums1[-1], nums2[-1]), calc(nums2[-1], nums1[-1]))
        return ans if ans < inf else -1

2935. 找出强数对的最大异或值 II

给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：

• |x - y| <= min(x, y)

你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。

返回数组 nums 所有可能的强数对中的 最大 异或值。

注意，你可以选择同一个整数两次来形成一个强数对。

示例 1：

输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。

示例 2：

输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。

示例 3：

输入：nums = [500,520,2500,3000]
输出：1020
解释：数组 nums 中有 6 个强数对：(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。
这些强数对中的最大异或值是 500 XOR 520 = 1020 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 2500 XOR 3000 = 636 。

提示：

• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 220 - 1

地址

https://leetcode.cn/contest/weekly-contest-371/problems/maximum-strong-pair-xor-ii/

题意

trie树

思路

1. 看到本题就想到力扣中的某个原题，因为要求最大的异或值，此时我们自然想到了使用 trie 树，尽量从高位低位找到数组中与当前元素，实际可以参考421. 数组中两个数的最大异或值 几乎是一样的题目，不过这里加了一个双指针与滑动窗口的问题，因此题目就变的非常简单了，题目的关键在于 $|x-y| \le min(x, y)$，即等价于 $2 * \min(x, y) >= \max(x,y)$，我们将数组按照从小到大进行排序，及遍历到当前元素 $nums[i]$ 时，找到范围处在 $nums[j] \in [\dfrac{nums[i]}{2}, nums[i]]$ 之间的元素 $nums[j]$ 即可，并将这些元素插入到字典树中，所有小于 $\dfrac{nums[i]}{2}$ 的元素则从字典树中删除，然后从字典树中查找与 $nums[i]$ 异或的最大值的元素。
2. 复杂度分析：

• 时间复杂度：$O(n \log U)$，其中 $n$ 表示数组的长度，$U$ 表示数组中的最大长度，我们分别存储
• 空间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度，$U$ 表示数组中的最大长度;

代码

class TrieNode:
    def __init__(self):
        self.cnt = 0
        self.next = [None] * 2

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insertTrie(self, val):
        node = self.root
        for i in range(19, -1, -1):
            x = (val >> i) & 1
            if node.next[x] is None:
                node.next[x] = TrieNode()
            node = node.next[x]
            node.cnt += 1
        return True

    def eraseTrie(self, val):
        node = self.root
        for i in range(19, -1, -1):
            x = (val >> i) & 1
            if node.next[x] is None:
                return false
            node = node.next[x]
            node.cnt -= 1
        return True
    
    def searchTrie(self, val):
        node = self.root
        res = 0
        for i in range(19, -1, -1):
            x = (val >> i) & 1
            y = x ^ 1
            if node.next[y] is not None and node.next[y].cnt > 0:
                res |= 1 << i
                node = node.next[y]
            elif node.next[x] is not None and node.next[x].cnt > 0:
                node = node.next[x]
        return res

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        trie = Trie()
        res, j = 0, 0
        for i in range(n):
            trie.insertTrie(nums[i])
            while j < i and 2 * nums[j] < nums[i]:
                trie.eraseTrie(nums[j])
                j += 1
            res = max(res, trie.searchTrie(nums[i]))
        return res

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿