本文主要是介绍Leetcode 第 379 场周赛题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Leetcode 第 379 场周赛题解
- Leetcode 第 379 场周赛题解
- 题目1:10035. 对角线最长的矩形的面积
- 思路
- 代码
- 复杂度分析
- 题目2:10036. 捕获黑皇后需要的最少移动次数
- 思路
- 代码
- 复杂度分析
- 题目3:10037. 移除后集合的最多元素数
- 思路
- 代码
- 复杂度分析
- 题目4:10038. 执行操作后的最大分割数量
- 思路
- 代码
- 复杂度分析
Leetcode 第 379 场周赛题解
题目1:10035. 对角线最长的矩形的面积
思路
模拟。
代码
/** @lc app=leetcode.cn id=10035 lang=cpp** [10035] 对角线最长的矩形的面积*/// @lc code=start
class Solution
{
public:int areaOfMaxDiagonal(vector<vector<int>> &dimensions){// 特判if (dimensions.empty())return 0;double maxDiagonal = 0.0;int maxArea = 0;for (vector<int> &dimension : dimensions){int length = dimension[0], width = dimension[1];if (sqrt(length * length + width * width) > maxDiagonal){maxDiagonal = sqrt(length * length + width * width);maxArea = length * width;}else if (sqrt(length * length + width * width) == maxDiagonal)maxArea = max(maxArea, length * width);}return maxArea;}
};
// @lc code=end
复杂度分析
时间复杂度:O(n),其中 n 是数组 dimensions 的长度。
空间复杂度:O(1)。
题目2:10036. 捕获黑皇后需要的最少移动次数
思路
分类讨论:
- 如果车能直接攻击到皇后,答案是 1。
- 如果象能直接攻击到皇后,答案是 1。
- 如果车被象挡住,那么移走象,车就可以攻击到皇后,答案是 2。
- 如果象被车挡住,那么移走车,象就可以攻击到皇后,答案是 2。
- 如果车不能直接攻击到皇后,那么车可以水平移动或者垂直移动,其中一种方式必定不会被象挡住,可以攻击到皇后,答案是 2。
对于车,如果和皇后在同一水平线或者同一竖直线,且中间没有象,那么就可以直接攻击到皇后。
对于象,如果和皇后在同一斜线,且中间没有车,那么就可以直接攻击到皇后。
代码
/** @lc app=leetcode.cn id=10036 lang=cpp** [10036] 捕获黑皇后需要的最少移动次数*/// @lc code=start
class Solution
{
public:int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f){// 车和皇后在一条横线上,且它们之间没有象if (a == e && !(a == c && d > min(b, f) && d < max(b, f)))return 1;// 车和皇后在一条竖线上,且它们之间没有象if (b == f && !(b == d && c > min(a, e) && c < max(a, e)))return 1;// 象和皇后在一条斜线上,且它们之间没有车if ((c + d == e + f && !(a + b == e + f && a > min(c, e) && a < max(c, e))) ||(c - d == e - f && !(a - b == e - f && a > min(c, e) && a < max(c, e))))return 1;return 2;}
};
// @lc code=end
复杂度分析
时间复杂度:O(1)。
空间复杂度:O(1)。
题目3:10037. 移除后集合的最多元素数
思路
贪心。
可以将数组去重后分为三个部分:nums1 独有的,nums2 独有的,nums1 与 nums2 共有的。
求集合 S 时:
- 先选择两个数组独有的。
- 对于共有的,两个数组尽量选不一样的。
代码
/** @lc app=leetcode.cn id=10037 lang=cpp** [10037] 移除后集合的最多元素数*/// @lc code=start
class Solution
{
public:int maximumSetSize(vector<int> &nums1, vector<int> &nums2){int n = nums1.size();unordered_set<int> set1, set2;for (int &x : nums1)set1.insert(x);for (int &x : nums2)set2.insert(x);int common = 0; // 两个数组共有的元素个数for (int x : set1)if (set2.count(x))common++;// count1 和 count2 分别为数组 nums1 和 nums2 独有元素的个数int count1 = set1.size() - common, count2 = set2.size() - common;// 贪心策略:先选二者独有的,没得选才选二者共有的int s1 = min(count1, n / 2), s2 = min(count2, n / 2);return s1 + s2 + min(n - s1 - s2, common);}
};
// @lc code=end
复杂度分析
时间复杂度:O(n),其中 n 是数组 nums1/nums2 的长度。
空间复杂度:O(n),其中 n 是数组 nums1/nums2 的长度。
题目4:10038. 执行操作后的最大分割数量
思路
题解:两种方法:记忆化搜索/O(n)前后缀分解(Python/Java/C++/Go)
代码
/** @lc app=leetcode.cn id=10038 lang=cpp** [10038] 执行操作后的最大分割数量*/// @lc code=start// 记忆化搜索+记录字符集合class Solution
{
public:int maxPartitionsAfterOperations(string s, int k){unordered_map<long long, int> memo;function<int(int, int, bool)> dfs = [&](int i, int mask, bool changed) -> int{if (i == s.length()){return 1;}long long args_mask = (long long)i << 32 | mask << 1 | changed;auto it = memo.find(args_mask);if (it != memo.end()){ // 之前计算过return it->second;}int res;// 不改 s[i]int bit = 1 << (s[i] - 'a');int new_mask = mask | bit;if (__builtin_popcount(new_mask) > k){// 分割出一个子串,这个子串的最后一个字母在 i-1// s[i] 作为下一段的第一个字母,也就是 bit 作为下一段的 mask 的初始值res = dfs(i + 1, bit, changed) + 1;}else{ // 不分割res = dfs(i + 1, new_mask, changed);}if (!changed){// 枚举把 s[i] 改成 a,b,c,...,zfor (int j = 0; j < 26; j++){new_mask = mask | (1 << j);if (__builtin_popcount(new_mask) > k){// 分割出一个子串,这个子串的最后一个字母在 i-1// j 作为下一段的第一个字母,也就是 1<<j 作为下一段的 mask 的初始值res = max(res, dfs(i + 1, 1 << j, true) + 1);}else{ // 不分割res = max(res, dfs(i + 1, new_mask, true));}}}return memo[args_mask] = res; // 记忆化};return dfs(0, 0, false);}
};
// @lc code=end
复杂度分析
这篇关于Leetcode 第 379 场周赛题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!