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：

思路

代码

在这里插入代码片

复杂度分析

时间复杂度：O()。

空间复杂度：O()。