Leetcode 第 371 场周赛题解

Leetcode 第 371 场周赛题解

题目1：100120. 找出强数对的最大异或值 I

思路

模拟。

枚举 2 遍数组 nums 的元素，更新最大异或值。

代码

/** @lc app=leetcode.cn id=100120 lang=cpp** [100120] 找出强数对的最大异或值 I*/// @lc code=start
class Solution
{
public:int maximumStrongPairXor(vector<int> &nums){int ans = INT_MIN;for (const int &x : nums)for (const int &y : nums){if (abs(x - y) <= min(x, y))ans = max(ans, x ^ y);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n²)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

题目2：100128. 高访问员工

思路

模拟。

把名字相同的员工对应的访问时间（转成分钟数）分到同一组中。

对于每一组的访问时间 accessTime，排序后，判断是否有 accessTime[i] - accessTime[i - 2] < 60，如果有，那么把这一组的员工名字加到答案中。

代码

/** @lc app=leetcode.cn id=100128 lang=cpp** [100128] 高访问员工*/// @lc code=start
class Solution
{
private:static const int MINUTE = 60;public:vector<string> findHighAccessEmployees(vector<vector<string>> &access_times){map<string, vector<int>> employees;for (const vector<string> &access_time : access_times){string name = access_time[0];string time = access_time[1];int accessTime = MINUTE * stoi(time.substr(0, 2)) + stoi(time.substr(2));employees[name].push_back(accessTime);}vector<string> highAccessEmployees;for (auto &[name, accessTime] : employees){sort(accessTime.begin(), accessTime.end());for (int i = 2; i < accessTime.size(); i++)if (accessTime[i] - accessTime[i - 2] < 60){highAccessEmployees.push_back(name);break;}}return highAccessEmployees;}
};
// @lc code=end

复杂度分析

时间复杂度：O(Lnlogn)，其中 n 为数组 access_times 的长度，L 为员工姓名的最大长度，本题不超过 10。

空间复杂度：O(Ln)，其中 n 为数组 access_times 的长度，L 为员工姓名的最大长度，本题不超过 10。

题目3：100117. 最大化数组末位元素的最少操作次数

思路

总共就两种情况：

1. 不交换 nums1[n-1] 和 nums[n-1]。
2. 交换 nums1[n-1] 和 nums[n-1]。

设计一个函数 getOps：

设 n = nums1.size()，last1 = nums1.back()，last2 = nums2.back()，ops 为交换操作次数。对于每种情况，枚举下标 i=0 到 i = n-2，设 x = nums1[i]，y = nums2[i]，一旦发现 x > last1 || y > last2，就必须执行交换操作。如果操作后仍然满足 y > last1 || x > last2，说明这种情况无法满足要求，返回 INF；否则，说明交换 x 和 y 能满足要求，ops++。

ans = min(getOps(nums1.back(), nums2.back()), getOps(nums2.back(), nums1.back()) + 1)

如果两种情况都无法满足要求，返回 -1。

代码

/** @lc app=leetcode.cn id=100117 lang=cpp** [100117] 最大化数组末位元素的最少操作次数*/// @lc code=start
class Solution
{
private:const int INF = 0x3f3f3f3f;public:int minOperations(vector<int> &nums1, vector<int> &nums2){int n = nums1.size();function<int(int, int)> getOps = [&](int last1, int last2) -> int{int ops = 0;for (int i = 0; i < n - 1; i++){int x = nums1[i], y = nums2[i];if (x > last1 || y > last2){if (y > last1 || x > last2)return INF;elseops++;}}return ops;};int ans = getOps(nums1.back(), nums2.back());ans = min(ans, getOps(nums2.back(), nums1.back()) + 1);return ans >= INF ? -1 : ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums1、nums2 的长度。

空间复杂度：O(1)。

题目4：100124. 找出强数对的最大异或值 II

思路

由于答案和数组 nums 的元素顺序无关，先排序。

排序后设 x ≤ y，那么 ∣x−y∣≤ min⁡(x, y) 可以化简为 2x ≥ y。

这意味着对于每个 y = nums[i]，我们需要选择 y 及其左边的满足 2x ≥ y 的 x，与 y 异或，求最大异或和。

与 Leetcode421. 数组中两个数的最大异或值 类似，把 hashset 改成 hashmap，一边遍历数组，一边记录每个 key 对应的最大的 nums[i]。

由于数组已经排好序，所以每个 key 对应的 x=nums[i] 一定是当前最大的，只要 2x ≥ y，就说明这个比特位可以是 1。

代码

/** @lc app=leetcode.cn id=100124 lang=cpp** [100124] 找出强数对的最大异或值 II*/// @lc code=start
class Solution
{
public:int maximumStrongPairXor(vector<int> &nums){sort(nums.begin(), nums.end());int high_bit = 31 - __builtin_clz(nums.back());int ans = 0, mask = 0;unordered_map<int, int> mp;// 从最高位开始枚举for (int i = high_bit; i >= 0; i--){mp.clear();mask |= 1 << i;int new_ans = ans | (1 << i); // 这个比特位可以是 1 吗？for (int y : nums){int mask_y = y & mask; // 低于 i 的比特位置为 0auto it = mp.find(new_ans ^ mask_y);if (it != mp.end() && it->second * 2 >= y){ans = new_ans; // 这个比特位可以是 1break;}mp[mask_y] = y;}}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogn+nlog⁡U)，其中 n 为 nums 的长度，U=max⁡(nums)。排序的时间复杂度为 O(nlogn)，外层循环需要循环 O(logU) 次。

空间复杂度：O(n)。哈希表中至多有 n 个数。