Leetcode 第 386 场周赛题解

本文主要是介绍Leetcode 第 386 场周赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 第 386 场周赛题解

题目1：3046. 分割数组

思路

哈希。

用一个哈希表统计数组 nums 中元素的出现次数，若有出现次数大于 2 的元素，则不能分割。

代码

/** @lc app=leetcode.cn id=3046 lang=cpp** [3046] 分割数组*/// @lc code=start
class Solution
{
public:bool isPossibleToSplit(vector<int> &nums){unordered_map<int, int> cnt;for (int &x : nums)cnt[x]++;for (auto &[x, count] : cnt)if (count > 2)return false;return true;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的元素个数。

空间复杂度：O(n)，其中 n 是数组 nums 的元素个数。

题目2：3047. 求交集区域内的最大正方形面积

思路

枚举两个矩形。

如果矩形有交集，那么交集一定是矩形。求出这个交集矩形的左下角和右上角。

• 左下角横坐标：两个矩形左下角横坐标的最大值。
• 左下角纵坐标：两个矩形左下角纵坐标的最大值。
• 右上角横坐标：两个矩形右上角横坐标的最小值。
• 右上角纵坐标：两个矩形右上角纵坐标的最小值。

知道坐标就可以算出矩形的长和宽，取二者最小值作为正方形的边长。

如果矩形没有交集，那么长和宽是负数，在计算面积前判断。

代码

/** @lc app=leetcode.cn id=3047 lang=cpp** [3047] 求交集区域内的最大正方形面积*/// @lc code=start
class Solution
{
public:long long largestSquareArea(vector<vector<int>> &bottomLeft, vector<vector<int>> &topRight){int n = bottomLeft.size();long long ans = 0LL;for (int i = 0; i < n - 1; i++){auto &b1 = bottomLeft[i];auto &t1 = topRight[i];for (int j = i + 1; j < n; j++){auto &b2 = bottomLeft[j];auto &t2 = topRight[j];int w = min(t1[0], t2[0]) - max(b1[0], b2[0]);int h = min(t1[1], t2[1]) - max(b1[1], b2[1]);int size = min(w, h);if (size > 0)ans = max(ans, (long long)size * size);}}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n²)，其中 n 是数组 bottomLeft 的元素个数。

空间复杂度：O(1)。

题目3：3048. 标记所有下标的最早秒数 I

思路

题意有点抽象，形象地解释一下：

你有 n 门课程需要考试，第 i 门课程需要用 nums[i] 天复习。同一天只能复习一门课程。

在第 i 天，你可以选择参加第 changeIndices[i] 门课程的考试。考试这一天不能复习。

搞定所有课程的复习+考试，至少要多少天？

二分答案。

答案越大，越能够搞定所有课程，反之越不能。

有单调性，可以二分答案。

代码

/** @lc app=leetcode.cn id=3048 lang=cpp** [3048] 标记所有下标的最早秒数 I*/// @lc code=start
class Solution
{
public:int earliestSecondToMarkIndices(vector<int> &nums, vector<int> &changeIndices){int n = nums.size(), m = changeIndices.size();if (n > m)return -1;vector<int> last_t(n);auto check = [&](int mx) -> bool{ranges::fill(last_t, -1);for (int t = 0; t < mx; t++){last_t[changeIndices[t] - 1] = t;}if (ranges::find(last_t, -1) != last_t.end()){ // 有课程没有考试时间return false;}int cnt = 0;for (int i = 0; i < mx; i++){int idx = changeIndices[i] - 1;if (i == last_t[idx]){ // 考试if (nums[idx] > cnt){ // 没时间复习return false;}cnt -= nums[idx]; // 复习这门课程}else{ // 留着后面用cnt++;}}return true;};int left = n - 1, right = m + 1;while (left + 1 < right){int mid = (left + right) / 2;if (check(mid))right = mid;elseleft = mid;}return right > m ? -1 : right;}
};
// @lc code=end

复杂度分析

时间复杂度：O(mlogm)，其中 m 为数组 changeIndices 的长度。二分的时候保证 n≤m，时间复杂度以 m 为主。

空间复杂度：O(n)，其中 n 为数组 nums 的长度。

题目4：3049. 标记所有下标的最早秒数 II

思路

题解：二分答案+反悔贪心（Python/Java/C++/Go）

这篇关于Leetcode 第 386 场周赛题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---