百宝图建设工程电子网站,多种大连网站建设,wordpress屏蔽功能org,用django做的网站Leetcode 第 371 场周赛题解 Leetcode 第 371 场周赛题解题目1#xff1a;100120. 找出强数对的最大异或值 I思路代码复杂度分析 题目2#xff1a;100128. 高访问员工思路代码复杂度分析 题目3#xff1a;100117. 最大化数组末位元素的最少操作次数思路代码复杂度分析 题目4… Leetcode 第 371 场周赛题解 Leetcode 第 371 场周赛题解题目1100120. 找出强数对的最大异或值 I思路代码复杂度分析 题目2100128. 高访问员工思路代码复杂度分析 题目3100117. 最大化数组末位元素的最少操作次数思路代码复杂度分析 题目4100124. 找出强数对的最大异或值 II思路代码复杂度分析 Leetcode 第 371 场周赛题解
题目1100120. 找出强数对的最大异或值 I
思路
模拟。
枚举 2 遍数组 nums 的元素更新最大异或值。
代码
/** lc appleetcode.cn id100120 langcpp** [100120] 找出强数对的最大异或值 I*/// lc codestart
class Solution
{
public:int maximumStrongPairXor(vectorint 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 codeend
复杂度分析
时间复杂度O(n2)其中 n 是数组 nums 的长度。
空间复杂度O(1)。
题目2100128. 高访问员工
思路
模拟。
把名字相同的员工对应的访问时间转成分钟数分到同一组中。
对于每一组的访问时间 accessTime排序后判断是否有 accessTime[i] - accessTime[i - 2] 60如果有那么把这一组的员工名字加到答案中。
代码
/** lc appleetcode.cn id100128 langcpp** [100128] 高访问员工*/// lc codestart
class Solution
{
private:static const int MINUTE 60;public:vectorstring findHighAccessEmployees(vectorvectorstring access_times){mapstring, vectorint employees;for (const vectorstring 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);}vectorstring 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 codeend复杂度分析
时间复杂度O(Lnlogn)其中 n 为数组 access_times 的长度L 为员工姓名的最大长度本题不超过 10。
空间复杂度O(Ln)其中 n 为数组 access_times 的长度L 为员工姓名的最大长度本题不超过 10。
题目3100117. 最大化数组末位元素的最少操作次数
思路
总共就两种情况
不交换 nums1[n-1] 和 nums[n-1]。交换 nums1[n-1] 和 nums[n-1]。
设计一个函数 getOps
设 n nums1.size()last1 nums1.back()last2 nums2.back()ops 为交换操作次数。对于每种情况枚举下标 i0 到 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 appleetcode.cn id100117 langcpp** [100117] 最大化数组末位元素的最少操作次数*/// lc codestart
class Solution
{
private:const int INF 0x3f3f3f3f;public:int minOperations(vectorint nums1, vectorint nums2){int n nums1.size();functionint(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 codeend复杂度分析
时间复杂度O(n)其中 n 是数组 nums1、nums2 的长度。
空间复杂度O(1)。
题目4100124. 找出强数对的最大异或值 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 对应的 xnums[i] 一定是当前最大的只要 2x ≥ y就说明这个比特位可以是 1。
代码
/** lc appleetcode.cn id100124 langcpp** [100124] 找出强数对的最大异或值 II*/// lc codestart
class Solution
{
public:int maximumStrongPairXor(vectorint nums){sort(nums.begin(), nums.end());int high_bit 31 - __builtin_clz(nums.back());int ans 0, mask 0;unordered_mapint, 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 codeend复杂度分析
时间复杂度O(nlognnlogU)其中 n 为 nums 的长度Umax(nums)。排序的时间复杂度为 O(nlogn)外层循环需要循环 O(logU) 次。
空间复杂度O(n)。哈希表中至多有 n 个数。
